python实现邻接表转邻接矩阵

2022-12-16 12:00

短信预约 -IT技能 免费直播动态提醒

python邻接表转邻接矩阵

闲话少说，前段时间看到有同学问怎么把邻接表转成邻接矩阵，想了想做了一下，仅供参考。= =

_python 2.7 _
包：networkX,numpy

# coding:utf-8
#将一个图，network转换为邻接矩阵
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 能够方便读写网络，并且写成我们需要的各种格式。

最后生成的结果为 txt 格式，手动导入excel然后按照空格分列就可以了。

图的存储—邻接矩阵与邻接表

有向图最常见的存储方式有两种：邻接矩阵和邻接表。

我们以这样一个图为例子演示这两种存储方式。

邻接矩阵

假如有向图中有n个顶点，邻接矩阵是一个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个顶点，邻接表是一个长度为n的数组，其索引为i的元素保存的是从顶点i可直接到达的顶点的列表

上面例子的图的邻接表如下：

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

入度与出度

到达图中某个顶点的边的条数称为这个图的入度，从某个顶点出发的边的条数称为这个图的出度

书面练习

请给出以下几例图的邻接矩阵和邻接表。

编程练习

题目描述

给定一个 n个顶点 m 条边的有向图。请以邻接矩阵和邻接表的形式输出这一张图。

输入格式

第一行输入两个正整数 n 和 m，表示图的顶点数和边数。顶点的编号为0 ~ n-1。

第二行开始，往后 m 行，每行输入两个以空格隔开的正整数 u,v，表示从u出发有一条边直接到达v。

输出格式

首先输出 n 行 n 列的矩阵，以空格隔开每一行之间的数表示邻接矩阵。第 i 行第 j 列的数为 1 则表示从顶点 i 出发有一条边直接到达 j ；若为 0 则表示没有直接到达的边。

然后空一行。

再往后输出 n 行，按顶点编号从小到大顺序。每一行首先先输出一个整数 d，表示这个顶点的出度，再按照从小到大的顺序，依次输出从该顶点出发可直接到达的所有顶点。

输入输出样例

输入#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

请先尝试自主编写，再阅读下面示例代码

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