目录
- 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然后按照空格分列就可以了。
图的存储—邻接矩阵与邻接表
有向图最常见的存储方式有两种:邻接矩阵和邻接表。
我们以这样一个图为例子演示这两种存储方式。
邻接矩阵
假如有向图中有n个顶点,邻接矩阵是一个n*n的矩阵A,其元素A[i][j]的值为
上面例子的图的邻近矩阵如下:
0 | 1 | 2 | 3 | 4 | |
---|---|---|---|---|---|
0 | 0 | 1 | 1 | 0 | 0 |
1 | 0 | 0 | 0 | 1 | 0 |
2 | 0 | 0 | 0 | 1 | 0 |
3 | 0 | 0 | 0 | 0 | 1 |
4 | 0 | 0 | 0 | 0 | 0 |
邻接表
假如有向图中有n个顶点,邻接表是一个长度为n的数组,其索引为i的元素保存的是从顶点i可直接到达的顶点的列表
上面例子的图的邻接表如下:
0: | 1 | 2 |
---|---|---|
1: | 3 | |
2: | 3 | |
3: | 4 | |
4: |
入度与出度
到达图中某个顶点的边的条数称为这个图的入度,从某个顶点出发的边的条数称为这个图的出度
书面练习
请给出以下几例图的邻接矩阵和邻接表。
编程练习
题目描述
给定一个 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 11 22 40 22 3
输出#1
0 1 1 0 0
0 0 1 0 00 0 0 1 10 0 0 0 00 0 0 0 0 2 1 21 22 3 400
请先尝试自主编写,再阅读下面示例代码
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(); } } }
总结
以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。
精彩评论