欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python實(shí)現(xiàn)鄰接表轉(zhuǎn)鄰接矩陣

 更新時(shí)間:2022年12月16日 10:41:00   作者:Ming_Che  
這篇文章主要介紹了python實(shí)現(xiàn)鄰接表轉(zhuǎn)鄰接矩陣,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教

python鄰接表轉(zhuǎn)鄰接矩陣

閑話少說(shuō),前段時(shí)間看到有同學(xué)問(wèn)怎么把鄰接表轉(zhuǎn)成鄰接矩陣,想了想做了一下,僅供參考。= =

  • _python 2.7 _
  • 包:networkX,numpy
# coding:utf-8
#將一個(gè)圖,network轉(zhuǎn)換為鄰接矩陣
import networkx ?as nx
import numpy as np
G = nx.read_weighted_edgelist("xx/xx.edgelist")
A = nx.to_numpy_matrix(G)

def savetxt(filename,x):
? ? np.savetxt(filename,x,fmt='%s',newline='\n')
savetxt("xx",A)

主要就是利用 networkx 能夠方便讀寫網(wǎng)絡(luò),并且寫成我們需要的各種格式。

最后生成的結(jié)果為 txt 格式,手動(dòng)導(dǎo)入excel然后按照空格分列就可以了。

圖的存儲(chǔ)—鄰接矩陣與鄰接表

有向圖最常見的存儲(chǔ)方式有兩種:鄰接矩陣和鄰接表。

我們以這樣一個(gè)圖為例子演示這兩種存儲(chǔ)方式。

鄰接矩陣

 假如有向圖中有n個(gè)頂點(diǎn),鄰接矩陣是一個(gè)n*n的矩陣A,其元素A[i][j]的值為

 A[i][j]=\begin{cases} 1 & \text{ if there is an edge from i to j } \\ 0 & \text{ if there is no edge from i to j } \end{cases}

上面例子的圖的鄰近矩陣如下:

01234
001100
100010
200010
300001
400000

鄰接表

假如有向圖中有n個(gè)頂點(diǎn),鄰接表是一個(gè)長(zhǎng)度為n的數(shù)組,其索引為i的元素保存的是從頂點(diǎn)i可直接到達(dá)的頂點(diǎn)的列表

上面例子的圖的鄰接表如下:

0:12
1:3
2:3
3:4
4:

入度與出度

到達(dá)圖中某個(gè)頂點(diǎn)的邊的條數(shù)稱為這個(gè)圖的入度,從某個(gè)頂點(diǎn)出發(fā)的邊的條數(shù)稱為這個(gè)圖的出度

書面練習(xí)

請(qǐng)給出以下幾例圖的鄰接矩陣和鄰接表。

 

編程練習(xí)

題目描述

給定一個(gè) n個(gè)頂點(diǎn) m 條邊的有向圖。請(qǐng)以鄰接矩陣和鄰接表的形式輸出這一張圖。

輸入格式

第一行輸入兩個(gè)正整數(shù) n 和 m,表示圖的頂點(diǎn)數(shù)和邊數(shù)。頂點(diǎn)的編號(hào)為0 ~ n-1。

第二行開始,往后 m 行,每行輸入兩個(gè)以空格隔開的正整數(shù) u,v,表示從u出發(fā)有一條邊直接到達(dá)v。

輸出格式

首先輸出 n 行 n 列的矩陣,以空格隔開每一行之間的數(shù)表示鄰接矩陣。第 i 行第 j 列的數(shù)為 1 則表示從頂點(diǎn) i 出發(fā)有一條邊直接到達(dá) j ;若為 0 則表示沒(méi)有直接到達(dá)的邊。

然后空一行。

再往后輸出 n 行,按頂點(diǎn)編號(hào)從小到大順序。每一行首先先輸出一個(gè)整數(shù) d?,表示這個(gè)頂點(diǎn)的出度,再按照從小到大的順序,依次輸出從該頂點(diǎn)出發(fā)可直接到達(dá)的所有頂點(diǎn)。

輸入輸出樣例

輸入#1

5 5
0 1
1 2
2 4
0 2
2 3

輸出#1

0 1 1 0 0
0 0 1 0 0
0 0 0 1 1
0 0 0 0 0
0 0 0 0 0
 
2 1 2
1 2
2 3 4
0
0

請(qǐng)先嘗試自主編寫,再閱讀下面示例代碼

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class BuildGraph {
     static List<List<Integer>> buildAdjacentList(int n, List<int[]> edges) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i=0; i<n; ++i) {
            res.add(new ArrayList<>());
        }
 
        for (int[] edge: edges) {
            res.get(edge[0]).add(edge[1]);
        }
        return res;
    }
 
    static int[][] buildAdjacentMatrix(int n, List<int[]> edges) {
        int[][] res = new int[n][n];
        for (int[] edge: edges) {
            res[edge[0]][edge[1]] = 1;
        }
        return res;
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int n = scanner.nextInt(), m = scanner.nextInt();
 
        List<int[]> edges = new ArrayList<>();
        for (int i=0; i<m; ++i) {
            int u = scanner.nextInt(), v = scanner.nextInt();
            edges.add(new int[]{u, v});
        }
 
        int[][] adjMatrix = buildAdjacentMatrix(n, edges);
        for (int i=0; i<n; ++i) {
            for (int j=0; j<n; ++j) {
                if (j != 0) {
                    System.out.print(' ');
                }
                System.out.print(adjMatrix[i][j]);
            }
            System.out.println();
        }
 
        System.out.println();
 
        List<List<Integer>> adjList = buildAdjacentList(n, edges);
        for (List<Integer> list: adjList) {
            System.out.print(list.size(
 
            Collections.sort(list);
            for (int e: list) {
                System.out.print(" " + e);
            }
 
            System.out.println();
        }
    }
}

總結(jié)

以上為個(gè)人經(jīng)驗(yàn),希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。

相關(guān)文章

  • python處理圓角圖片、圓形圖片的例子

    python處理圓角圖片、圓形圖片的例子

    最近因?yàn)楣ぷ餍枰?,需要處理圖片,一種是頭像的方形圖片處理成圓行的,一種是方形圖片的4角變得橢圓點(diǎn)
    2014-04-04
  • Python中關(guān)于property使用的小技巧

    Python中關(guān)于property使用的小技巧

    俗話說(shuō)條條大路通羅馬,同樣是完成一件事,Python 其實(shí)提供了好幾個(gè)方式供你選擇。property() 是一個(gè)比較奇葩的BIF,它的作用把方法當(dāng)作屬性來(lái)訪問(wèn),從而提供更加友好訪問(wèn)方式
    2021-09-09
  • 淺談python新式類和舊式類區(qū)別

    淺談python新式類和舊式類區(qū)別

    python的新式類是2.2版本引進(jìn)來(lái)的,我們可以將之前的類叫做經(jīng)典類或者舊式類。這篇文章主要介紹了淺談python新式類和舊式類區(qū)別,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-04-04
  • Python?tkinter庫(kù)繪圖實(shí)例分享

    Python?tkinter庫(kù)繪圖實(shí)例分享

    這篇文章主要給大家分享了Python?tkinter庫(kù)繪圖實(shí)例,主要分享實(shí)例有小房子繪制、彩色氣泡動(dòng)畫繪制內(nèi)容,需要的小伙伴可以參考一下,希望對(duì)你的學(xué)習(xí)有所幫助
    2022-04-04
  • python3實(shí)現(xiàn)字符串的全排列的方法(無(wú)重復(fù)字符)

    python3實(shí)現(xiàn)字符串的全排列的方法(無(wú)重復(fù)字符)

    這篇文章主要介紹了python3實(shí)現(xiàn)字符串的全排列的方法(無(wú)重復(fù)字符),小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2018-07-07
  • Python實(shí)現(xiàn)制作透明背景的電子印章

    Python實(shí)現(xiàn)制作透明背景的電子印章

    這篇文章主要為大家詳細(xì)介紹了如何利用Python語(yǔ)言實(shí)現(xiàn)制作透明背景的電子印章,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以嘗試一下
    2022-09-09
  • python中session的使用案例詳解

    python中session的使用案例詳解

    這篇文章主要介紹了python?session使用,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2023-05-05
  • 淺析Django 接收所有文件,前端展示文件(包括視頻,文件,圖片)ajax請(qǐng)求

    淺析Django 接收所有文件,前端展示文件(包括視頻,文件,圖片)ajax請(qǐng)求

    這篇文章主要介紹了Django 接收所有文件,前端展示文件(包括視頻,文件,圖片)ajax請(qǐng)求,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下
    2020-03-03
  • Python中非常好用的內(nèi)置函數(shù)詳解

    Python中非常好用的內(nèi)置函數(shù)詳解

    這篇文章主要為大家介紹了Python中非常好用的內(nèi)置函數(shù),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助
    2021-12-12
  • 使用Python實(shí)現(xiàn)tail的示例代碼

    使用Python實(shí)現(xiàn)tail的示例代碼

    tail是一個(gè)常用的Linux命令, 它可以打印文件的后面n行數(shù)據(jù), 也能實(shí)時(shí)輸出文件的追加數(shù)據(jù)。本文就來(lái)用Python實(shí)現(xiàn)tail,感興趣的可以了解一下
    2023-03-03

最新評(píng)論