邻接矩阵是图论中非常重要的概念。邻接矩阵使用矩阵以数学格式表示图。假设该图有“V”个顶点。邻接矩阵是维度为 V*V 的方阵。它代表图的边。
让我们了解如何使用这个公式创建邻接矩阵，
AdjM={ A[i][j]=0 if [i,j] is not an edge in the Graph A[i][j]=1 if [i,j] is an edge in the Graphwhere i,j <V} |
一个例子将阐明上面的邻接矩阵公式。图表如下所示：
第二张图显示了示例图的邻接矩阵。需要注意的是，由于图是无向的，因此邻接矩阵中位置 [i,j] 和 [j,i] 的元素均为 1，其中 [i,j] 是图中的边。由于图中顶点 2 和 0 之间有一条边，因此邻接矩阵中位置 (2,0) 和 (0,2) 的值为 1。对于其他边也可以看到。由于图中顶点 4 和 1 之间没有边，因此位置 (4,1) 和 (1,4) 处的值为 0。对于其他顶点也可以看到，它们之间也没有边。
欲了解更多信息：在 Python 中实现图
如何在Python中创建邻接矩阵？
Python的networkx模块帮助用户进行图形可视化。它将用于解释所形成的图和邻接矩阵。可以在 Command Shell 中使用以下命令来安装它：
>>> pip install networkx |
本文将介绍两种不同的方法。第一种方法是从作为输入提供的顶点和边列表创建邻接矩阵。第二种方法是从作为输入给出的邻接矩阵创建一个图（顶点和边的集合）。整篇文章仅关注无向图。
从图的顶点和边创建邻接矩阵
该函数有两个输入：顶点和边的列表。边将作为列表的列表给出。每个内部列表由两个元素组成：第一个元素是边的起始顶点，第二个元素是边的结束顶点。它返回一个邻接矩阵作为其输出，并在函数中绘制相应的图形。下面的代码演示了这一点：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 号
18
19
20
21
|
def createAdjacencyMatrix(vertices,edges): noofvertices=len(vertices) adjM=[] while(len(adjM)<noofvertices): temp=[] for i in range(noofvertices): temp.append(0) adjM.append(temp) for edge in edges: i=edge[0] j=edge[1] if i>=noofvertices or j>=noofvertices or i<0 or j<0: print(f"Not a Proper Input in Edge {i},{j}") else: adjM[i][j]=1 adjM[j][i]=1 G=nx.Graph() G.add_edges_from(edges) nx.draw_networkx(G) plt.show() return adjM |
上面的代码片段创建了一个存储在名为 adjM 的变量中的邻接矩阵。它的行维和列维与图中的顶点数相同。初始化邻接矩阵，所有初始值为0。遍历边列表的所有内层列表，将第一个元素指定为起始节点，将第二个元素指定为结束节点。还可以在第 12 行看到检查条件也已实现。对于超出范围的顶点值，程序将打印一条错误消息。超出范围被定义为值大于最大顶点数或值小于 0 的顶点。之后，在位置 [i,j] 和 [j,i] 处的值邻接矩阵转换为1。
该函数的另一部分根据给定的输入绘制图表。该函数返回创建的邻接矩阵。networkx 模块的功能在下面提供的文章中得到了很好的定义：
执行时，该函数将产生一个邻接矩阵并绘制相应的图形。输入图的顶点和边如下所示：
vertices=[0,1,2,3,4,5]edges=[[1,2],[2,4],[1,5],[3,5],[4,5],[1,3],[0,3],[0,2],[5,3],[5,1]] |
当上面给出的值作为函数 createAdjacencyMatrix() 的输入时，它会产生以下输出：
[[0, 0, 1, 1, 0, 0], [0, 0, 1, 1, 0, 1], [1, 1, 0, 0, 1, 0], [1, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1], [0, 1, 0, 1, 1, 0]] |
第二个函数从邻接矩阵创建一个图。它将输入作为邻接矩阵，并提供输出作为顶点和边的集合。
从邻接矩阵创建图
在第二个函数中，提供邻接矩阵作为输入。它还会将图形可视化，返回值将是顶点和边。邻接矩阵是列表的列表，其中每个内部列表的长度与整个外部列表的长度相同。这确保提供方阵作为输入。下面的代码演示了这一点：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 号
18
19
|
def createGraph(adjM): edges=[] noofvertices=len(adjM) for mat in adjM: if len(mat)>noofvertices or len(mat)<noofvertices: print("False Adjacency Matrix") return 0 for i in range(len(adjM)): mat=adjM[i] for j in range(len(mat)): if mat[j]==1: temp=[i,j] edges.append(temp) G=nx.Graph() G.add_edges_from(edges) nx.draw_networkx(G) plt.show() vertices=[i for i in range(len(adjM))] return vertices,edges |
上面代码的主要功能是创建列表边。边被创建为列表的列表，每个内部列表都有两个元素：边的起始顶点和结束顶点。该代码遍历邻接矩阵的长度，对于矩阵中的每个元素（即 1），将行号和列号存储为边。该代码还检查条件以确保已提供方阵作为输入。如果维度不满足条件，该函数将提前退出。networkx 的 Graph() 对象使用创建的边列表来可视化图形。顶点是图中所有顶点的列表。它只是通过枚举邻接矩阵的长度来实现，如第 18 行所示。边和顶点的集合作为输出返回。
以下 5 个顶点的邻接矩阵用作函数 createGraph() 的检查输入：
adjM=[[1,0,1,0,1],[0,0,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,1,0]] |
它生成一个无向图作为其输出。应该注意的是，(0,0) 处的元素保持为 1，这意味着顶点 0 处有一条循环边。邻接矩阵作为输入提供时，会产生以下输出
([0, 1, 2, 3, 4], [[0, 0], [0, 2], [0, 4], [1, 2], [1, 3], [2, 0], [2, 1], [2, 3], [3, 0], [3, 1], [4, 3]]) |
输出中的第一个元素是顶点列表，第一个顶点为索引 0。第二个输出是显示图的边的列表列表。
源代码
我在 Google Colaboratory 中开发了完整的代码，用于演示给定的函数并生成输出。任何人都可以访问它的源代码。
结论
邻接矩阵是表示图的一种重要方式。在本文中，我们了解了如何使用 Python 轻松创建和操作邻接矩阵。它是一个方阵，其维度为图上的边数。可以从图输入轻松创建邻接矩阵，反之亦然。从邻接矩阵实现图同样容易。创建邻接矩阵的时间复杂度为 O(n2)，其中 n 是图中的顶点数。