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

老齐

发布于 2021-12-27 14:32:06

2.8K0

发布于 2021-12-27 14:32:06

文章被收录于专栏：老齐教室

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=j\end{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&0\end{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所示有向图：

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引用），还可以使用内置的方法绘制展现各个结点关系的图。

%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的邻接矩阵。

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=j\end{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&0\end{bmatrix}

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

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

A \to B

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

A \to B \to C

或

A\to 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所得到的邻接矩阵为：

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检查，的确如此。

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

中长度为

的路径。

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”。

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”。

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

且长度为

的路径数量。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-12-22，如有侵权请联系 cloudcommunity@tencent.com 删除

python

connection

matrix

path

本文分享自老齐教室微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

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

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐