python实现邻接表转邻接矩阵_开发_开发者

开发者 https://www.devze.com 2022-12-17 09:28 出处：网络作者： Ming_Che

目录python邻接表转邻接矩阵图的存储—邻接矩阵与邻接表邻接矩阵邻接表入度与出度书面练习编程练习总结python邻接表转邻接矩阵

python邻接表转邻接矩阵

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

_python 2.7 _
包：networkX,numpy

# coding:utf-8
#将一个图，network转换为邻接矩阵
import netwjsorkx 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然后按照空格分列就可以了。

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

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

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

python实现邻接表转邻接矩阵

邻接矩阵

假如有向图中有n个顶点，邻接矩阵是一个n*n的矩阵A，其元素A[i][j]的值为

python实现邻接表转邻接矩阵

上面例子的图的邻近矩阵如下：

	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

入度与出度

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

书面练习

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

python实现邻接表转邻接矩阵

编程练习

题目描述

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

输入格式

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

第二行开始，往后 m 行，每行输入两个以空格隔开的正整数 u,v，表示从u出发有一条边直FZwLRgerUt接到达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>> bu开发者_JS培训ildAdjacentList(int n, List<int[]> edges) {
        List<List<Integephpr>> 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,http://www.devze.com 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();
        }
    }
}