Python中的邻接矩阵

Python 6月前 177

在Python中，图数据结构被用来表示各种现实生活中的对象，如网络和地图。我们可以用一个邻接矩阵来表示一个图。

本文将讨论在Python中实现邻接矩阵的不同方法。

创建一个邻接矩阵

考虑下面这个图。

在该图中，有6个节点，编号从1到6。图中有7条连接节点的边；一条边_eij连接了节点i 和节点j 。

为了表示该图，我们使用一个邻接矩阵。

一个邻接矩阵由一个二维网格组成。
网格中的每一行或每一列代表一个节点。
对于一个非加权图，如上图所示，如果在网格中(i,j) 的位置的值是1，这意味着节点i 和节点j 是相连的。
如果位置(i,j) 的值是0，则节点i 和节点j 没有连接。

如果你想为上图中的图形创建一个邻接矩阵，它将看起来如下。

| 0    | 1    | 0    | 0    | 0    | 0    |
| 1    | 0    | 1    | 1    | 0    | 0    |
| 0    | 1    | 0    | 1    | 0    | 1    |
| 0    | 1    | 1    | 0    | 1    | 0    |
| 0    | 0    | 0    | 1    | 0    | 1    |
| 0    | 0    | 1    | 0    | 1    | 0    |

上表显示，位置(i,j) 的值也出现在位置(j,i) 。这是由于边_eij与边_eji相同的原因。

这也导致了一个沿对角线对称的邻接矩阵。

在一个非加权图中，边没有权重。换句话说，所有的边都有相等的权重。

由于这个原因，邻接矩阵只包含0和1的值。

现在，考虑以下加权图。

对于一个加权图来说，除了边的权重之外，一切都没有变化。你可以看到，每条边在图像中都被分配了一个值。

因此，在邻接矩阵中，位置(i,j) 的值是图中边_eij的权重。

上述图像的邻接矩阵看起来如下。

| 0    | 5    | 0    | 0    | 0    | 0    |
| 5    | 0    | 1    | 12   | 0    | 0    |
| 0    | 1    | 0    | 8    | 0    | 4    |
| 0    | 12   | 8    | 0    | 7    | 0    |
| 0    | 0    | 0    | 7    | 0    | 2    |
| 0    | 0    | 4    | 0    | 2    | 0    |

同样，你可以观察到，矩阵中位置(i,j) 的值也出现在位置(j,i) 。这是由于边_eij与边_eji相同的原因。

同样，这导致了一个沿对角线对称的邻接矩阵。

使用二维列表在Python中创建一个邻接矩阵

为了创建一个具有n 节点的非加权图的邻接矩阵，我们将首先创建一个包含n 内列表的二维列表。此外，每个内列表包含n 零。

在创建一个包含零的二维列表后，我们将把1分配给图中存在边_eij的位置(i,j) 。对于这项任务，我们将使用以下步骤。

首先，我们将创建一个名为adjacency_matrix 的空列表。之后，我们将使用for 循环和append() 方法将其转换为一个二维列表。
在for 循环中，我们将创建一个名为row 的空列表。然后，我们将使用另一个for 循环用零填充空列表，最后，我们将把row 附加到adjacency_matrix 。
在代码中，我们用一个图元的列表来表示边的集合。每个元组包含2个值，代表图形的连接节点。
在定义了边之后，我们将使用for 循环为图中存在边的位置赋值为1。

代码：

import pprint
row_num = 6
col_num = 6
adjacency_matrix = []
for i in range(row_num):
    row = []
    for j in range(col_num):
        row.append(0)
    adjacency_matrix.append(row)
edges = [(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
for edge in edges:
    row = edge[0]
    col = edge[1]
    adjacency_matrix[row - 1][col - 1] = 1
    adjacency_matrix[col - 1][row - 1] = 1
print("The edges in the graph are:")
print(edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)

输出：

The edges in the graph are:
[(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
The adjacency matrix is:
[[0, 1, 0, 0, 0, 0],
 [1, 0, 1, 1, 0, 0],
 [0, 1, 0, 1, 0, 1],
 [0, 1, 1, 0, 1, 0],
 [0, 0, 0, 1, 0, 1],
 [0, 0, 1, 0, 1, 0]]

在代码中，你可以看到我们有基于0的索引。由于这个原因，每个节点(i,j) ，在邻接矩阵中由位置(i-1,j-1) 。

为了创建一个加权图的邻接矩阵，我们将首先创建一个有0的n x n 2维列表。之后，我们将在矩阵中的位置(i,j) ，分配边_eij的权重。

你可以在下面的例子中观察到这一点。

import pprint
row_num = 6
col_num = 6
adjacency_matrix = []
for i in range(row_num):
    row = []
    for j in range(col_num):
        row.append(0)
    adjacency_matrix.append(row)
weighted_edges = [(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
for edge in weighted_edges:
    row = edge[0]
    col = edge[1]
    weight = edge[2]
    adjacency_matrix[row - 1][col - 1] = weight
    adjacency_matrix[col - 1][row - 1] = weight
print("The edges in the graph are:")
print(weighted_edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)

输出：

The edges in the graph are:
[(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
The adjacency matrix is:
[[0, 5, 0, 0, 0, 0],
 [5, 0, 1, 12, 0, 0],
 [0, 1, 0, 8, 0, 4],
 [0, 12, 8, 0, 7, 0],
 [0, 0, 0, 7, 0, 2],
 [0, 0, 4, 0, 2, 0]]

在上面的代码中，边已经用三组数字表示。前两个数字代表图中由边连接的节点。

第三个数字代表该边缘的权重。

使用NumPy模块在Python中创建一个邻接矩阵

要使用NumPy模块为一个图制作一个邻接矩阵，我们可以使用np.zeros() 方法。

np.zeros() 方法将一个形式为(row_num,col_num) 的元组作为其输入参数，并返回一个形状为row_num x col_num 的二维矩阵。这里，row_num 和col_num 是矩阵的行和列的数量。

我们将使用以下步骤来创建一个使用np.zeros() 方法的邻接矩阵。

首先，我们将通过向zeros() 方法传递一个元组(n,n) 来创建一个大小为n x n 的矩阵。
然后，我们将在图中每条边_eij的位置(i-1,j-1) ，将数值更新为1；这里，我们使用基于0的索引。由于这个原因，节点(i,j) 在代码中被表示为位置(i-1,j-1) 。

执行上述步骤后，我们将得到邻接矩阵，如下面的例子所示。

import pprint
import numpy as np
row_num = 6
col_num = 6
adjacency_matrix = np.zeros((row_num, col_num),dtype=int)
edges = [(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
for edge in edges:
    row = edge[0]
    col = edge[1]
    adjacency_matrix[row - 1][col - 1] = 1
    adjacency_matrix[col - 1][row - 1] = 1
print("The edges in the graph are:")
print(edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)

输出：

The edges in the graph are:
[(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
The adjacency matrix is:
array([[0, 1, 0, 0, 0, 0],
       [1, 0, 1, 1, 0, 0],
       [0, 1, 0, 1, 0, 1],
       [0, 1, 1, 0, 1, 0],
       [0, 0, 0, 1, 0, 1],
       [0, 0, 1, 0, 1, 0]])

为了创建加权图的邻接矩阵，我们将把位置(i,j) 的值更新为边_eij的权重，如下图所示。

import pprint
import numpy as np
row_num = 6
col_num = 6
adjacency_matrix = np.zeros((row_num, col_num), dtype=int)
weighted_edges = [(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
for edge in weighted_edges:
    row = edge[0]
    col = edge[1]
    weight = edge[2]
    adjacency_matrix[row - 1][col - 1] = weight
    adjacency_matrix[col - 1][row - 1] = weight
print("The edges in the graph are:")
print(weighted_edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)

输出：

The edges in the graph are:
[(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
The adjacency matrix is:
array([[ 0,  5,  0,  0,  0,  0],
       [ 5,  0,  1, 12,  0,  0],
       [ 0,  1,  0,  8,  0,  4],
       [ 0, 12,  8,  0,  7,  0],
       [ 0,  0,  0,  7,  0,  2],
       [ 0,  0,  4,  0,  2,  0]])