图论中的邻接矩阵及其实现方法

2.7.2 邻接矩阵

如图2-7-4所示，图中有A、B、C、D、E这5个节点，每两个结点之间，有的没有连接，比如A、C。对于有连接的结点之间，用箭头标示，箭头的方向表示连接方向。例如A和B之间，表示可以从A到B，但不能从B到A；B和C之间，则用双向箭头标示，既能从B到C，又能从C到A。

图 2-7-4

像这样的图，在很多业务中都可能存在，比如交通、通讯、网络等，根据2.7.1节的概念，我们知道它属于有向图。

继续观察图2-7-4，任何两个结点之间的关系，可以用下面的形式表示：

a_{ij}=begin{cases}1,能从P_i点连接到P_j点\0, 不能从P_i点连接到P_j点\0, 若i=jend{cases}

根据上式，例如：

从A到C，即为

；

从B到C，即为

；

从E到B，即为

；

从D到D，即为

。

为了能够将任意两个点之间的关系一目了然表示出来，可以绘制如下表格：

	B	C	D	E
A	1	0	0	0
B	0	1	1	1
C	1	0	0	1
D	1	0	0	0
E	1	0	1	0

表中数字是根据从左侧每个结点到顶部每个结点，根据前述定义所得结果。如果把表格中的数字写成矩阵，则为：

pmb{P} = begin{bmatrix}0&1&0&0&0\0&0&1&1&1\0&1&0&0&1\0&1&0&0&0\0&1&0&1&0end{bmatrix}

例如（对照表格），

P_{12}=1

，表示结点A可以连接到结点B；

P_{53}=0

，表示结点E不能连接到结点C。

至此，用矩阵

pmb{P}

表示了图2-7-4所示的有向图，这个矩阵我们称之为邻接矩阵（adjacency matrix，或：connection matrix），显然矩阵

pmb{P}

也是稀疏矩阵。

在上述的有向图中，没有涉及连接结点之间的权重，或者说是平权的。关于权重、距离等更多图相关的知识，读者可以自行参考有关资料。

如果用程序实现图和邻接矩阵，可以使用NexworkX（https://networkx.github.io/），这是一个 Python 语言的第三方包，它能够实现各种图。例如创建图2-7-4所示有向图：

代码语言：javascript复制

import networkx as nx
G = nx.DiGraph()
G.add_edges_from([('A','B'),('B','C'),('B','D'),('B','E'),('C','B'),('C','E'),('D','B'),('E','B'),('E','D')])

这样就创建了有向图对象（用变量G引用），还可以使用内置的方法绘制展现各个结点关系的图。

代码语言：javascript复制

%matplotlib inline
import matplotlib.pyplot as plt
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, cmap=plt.get_cmap('jet'), node_size = 500)
nx.draw_networkx_labels(G, pos)
nx.draw_networkx_edges(G, pos,arrows=True)

输出图像：

将此图与2-7-4相比，除了各结点的位置有所不同之外，它们的相关系是一样的，并且，在视觉上更反映了“聚焦”的结点。

利用NexworkX中的函数adjacency_matrix()可以得到图G的邻接矩阵。

代码语言：javascript复制

G_A = nx.adjacency_matrix(G)
G_A

# 输出
<5x5 sparse matrix of type '<class 'numpy.longlong'>'
           with 9 stored elements in Compressed Sparse Row format>

显然，邻接矩阵是稀疏矩阵，此处所得到的G_A即为稀疏矩阵的压缩格式。

前面从柯尼斯堡七桥问题所抽象出来的图是一个无向图（如图2-7-5所示）。对于无向图，也可以创建邻接矩阵，只不过节点没有方向（或者说是对称的），其规则是：

a_{ij}=begin{cases}1,P_i点与P_j点连接\0, 若i=jend{cases}

图 2-7-5

故可得图2-7-5所示的无向图的邻接矩阵：

pmb{P}=begin{bmatrix}0&1&1&1\1&0&0&0\1&0&0&1\1&1&1&0end{bmatrix}

显然无向图的邻接矩阵是对称矩阵。

再观察图2-7-4和图2-7-5，不难发现，并非所有节点之间都有边直接连接，有的节点之间是一条边连接（如图2-7-5中

A to B

），有的节点之间则是多条边连接（如图2-7-5中

A to B to C

或

Ato D to C

），为了描述像这种从一个节点与另外一个节点的链接关系，引入了连通和路径两个概念。

假设一个有向图，从一个节点

v_0

开始，按照如下的路径，可以达到另外一个节点

v_l

：

v_0 to v_1 to cdots v_l

则称这两个节点是连通的（connected）。若连通的节点之间没有重复节点，那么就称之为一条路径（path）。如图2-7-6所示，从节点A到节点C是连通的，其路径包括：

路径1：

A to B to C

；

路径2：

A to E to D to C

；

路径3：

A to D to C

；

路径4：

A to D to B to C

；

路径5：

A to E to D to B to C

。

路径1中有两条边，路径2中有三条边，我们将路径中边的条数称为路径的长度，两个节点之间的最短长度称为距离，记作

d(v_i, v_j)

，

v_i

和

v_j

分别表示两个节点。仍以图2-7-6中的节点A到节点C为例，显然

d(A, C) =2

；从节点C到节点E（注意方向）是不连通的，则令其距离为

d(C,E)=infty

。

图 2-7-6

由图2-7-6所得到的邻接矩阵为：

代码语言：javascript复制

import numpy as np
A = np.mat("0 1 0 1 1; 0 0 1 0 0; 0 0 0 0 0; 0 1 1 0 0; 0 0 0 1 0")
A

# 输出
matrix([[0, 1, 0, 1, 1],
        [0, 0, 1, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 0, 1, 0]])

通过这个邻接矩阵，不仅可以显示了任意两个节点之间的关系，而且可以知道两个节点之间长度为

路径数量，比如第1行第2列的元素

，即

a_{12}=1

，表示节点A到节点B长度为

的路径数是

；

a_{13}=0

表示节点A到节点C长度为

的路径数是

。对照图2-7-6检查，的确如此。

代码语言：javascript复制

A * A

# 输出
matrix([[0, 1, 2, 1, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 1, 0, 0],
        [0, 1, 1, 0, 0]])

这里计算的是

pmb{A}^2

，所得矩阵的元素表示节点之间长度为

的路径数，比如第1行第3列的元素

，即

a_{13}=2

，表示节点A到节点C长度为

的路径数是

。对照图2-7-6，前面列出的“路径1”和“路径3”是

A to C

中长度为

的路径。

代码语言：javascript复制

A * A * A

# 输出
matrix([[0, 1, 2, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 1, 0, 0]])

pmb{A}^3

中的元素表示节点之间长度为

的路径数量，

a_{13} =2

表示节点

A to C

长度为

的路径数是2，即前述“路径2”和“路径4”。

代码语言：javascript复制

A * A * A * A

# 输出
matrix([[0, 0, 1, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0]])

pmb{A}^4

中只有

a_{13}=1

，其余元素都是

，即节点

A to C

长度为

的路径只有

个，恰为前述“路径5”。

代码语言：javascript复制

A * A * A * A * A

# 输出
matrix([[0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0]])

按照前面的逻辑，

pmb{A}^5

中的元素都为

就比较容易理解了。

归纳以上可知，邻接矩阵的幂矩阵

pmb{A}^l

中的第

行第

列元素（用

(pmb{A}^l)_{ij}

表示），即为节点

v_i

至节点

v_j

且长度为

的路径数量。

python connection matrix path

0 人点赞