快捷導(dǎo)航

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 能夠方便讀寫(xiě)網(wǎng)絡(luò)，并且寫(xiě)成我們需要的各種格式。

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

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

有向圖最常見(jiàn)的存儲(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}$

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

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

鄰接表

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

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

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

入度與出度

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

書(shū)面練習(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。

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

輸出格式

首先輸出 n 行 n 列的矩陣，以空格隔開(kāi)每一行之間的數(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)先嘗試自主編寫(xiě)，再閱讀下面示例代碼

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();
        }
    }
}