第16讲 图的矩阵表示, 赋权图与最短路径 主要内容: 1.图的矩阵表示. 2.赋权图与最短路径.

7.6 图的矩阵表示 将一个图画出来是最直观的表示图的方式. 为了便于使用计算机存储和处理图,更为了借助于完善的矩阵理论(线性代数知识之一!)研究图的有关性质,有必要学习图的矩阵表示. 本节简单介绍图的常见的3种矩阵表示及一些简单结论, 不涉及更多的有关图的矩阵方面的知识.

1.图的邻接矩阵 第一种图的矩阵表示—邻接矩阵,它表示的是图中任意两个节点间的邻接关系. Def 7-29  G = (V, E), 对节点编号V = {v1, v2, …, vn}. 其中aij是vi邻接到vj的边数, i, j = 1, 2, …, n.

显然, 无向图的邻接矩阵是对称矩阵. 一个图与其邻接矩阵是一一对应的. 从一个图G的邻接矩阵A(G)容易得出每个节点的度数. 以有向图为例, A(G)中第i行元素之和为第个i节点的出度vi, i = 1, 2, …, n, 第j列元素之和为第个j节点的入度, j = 1, 2, …, n.

从图的邻接矩阵可以得出从节点vi到vj长度为l(l  1)的路的数目. Theorem 7-12 设A是图G的邻接矩阵, 则Al中(i, j)位置元素为从节点vi到vj长度为l(l  1)的路的数目. Proof 对l归纳. l = 1, 显然. Al = Al-1∙A:

例7-7 Solution

2.图的可达矩阵 第二种图的矩阵表示—可达矩阵,它表示的是图中任意两个节点间的可达关系. Def  G = (V, E), 对节点编号V = {v1, v2, …, vn}. 其中pij= 1, 若vi可达vj, 否则pij= 0, i, j = 1, 2, …, n.

例子? 容易由图的邻接矩阵得出其可达矩阵,一个非常有效的算法是Warshall算法. 根据我们的可达矩阵的定义知, 中所有主对角线上的元素全为1, 这是由于任意节点可达自身所致. 更容易从图的可达矩阵得出图的连通性质.

3.图的关联矩阵 第三种图的矩阵表示—关联矩阵,它表示的是图中节点与边之间的关联关系. (1)无向图 Def  无向图G = (V, E), 对节点编号V = {v1, v2, …, vn}, 对边编号E = {e1, e2, …, em}. 其中mij是vi与ej的关联次数, i, j.

(2)有向图 Def  无吊环有向图G = (V, E), 对节点编号V = {v1, v2, …, vn}, 对边编号E = {e1, e2, …, em}: 例子? 图与其关联矩阵是一一对应的.

图还有其他矩阵表示,如距离矩阵、圈矩阵以及割集矩阵等,参考有关文献 图还有其他矩阵表示,如距离矩阵、圈矩阵以及割集矩阵等,参考有关文献. 前面已经谈到,有了这些图的矩阵表示,可以用线性代数中的知识,特别是矩阵理论对图做更深入的研究,由于篇幅所限,本书不涉及这些内容的进一步讨论,可参见有关图论文献.

7.7 赋权图及最短路径 1.赋权图 在图的实际应用中,除建立图论模型外,有时还需要将一些附加信息赋予图的边或节点,其中之一就是赋权图(weighted graph). 本节仅讨论边赋权图. Def 设G = (V, E)是任意图,若的每一条边上都赋予一个非负实数,则称G是边赋权图. 图7.39(a)(b)是两个边赋权图.

在边赋权图中,每条边上所赋的非负实数称为这条边上的权,它可以理解为该边上的流量或通过该边的时间,还可以理解为该边的长度.

2.最短路径 在边赋权图中,从一个节点到另一个节点的路上所有边上的权之和称为该路的“权”,例如在图7.39(a)中路v2 v3v5 v6 v7的权为 2 + 3 + 1 + 5 = 11. 在实际应用中,最短线路的铺设、运输网络的最少时间以及互联网上的最短路由问题等,都需要得出从一个节点到别的节点权最小的一条路,它必为路径,称为最短路径.

荷兰著名计算机专家E. W. Dijkstra (1930 ~)于1959年提出的求一个节点到其他任意节点的最短路径算法, 是至今为止被大家公认的有效算法, 其时间复杂度为O(n2), 其中n为图的节点个数. 《数据结构》, 《算法分析与设计》. 设G = (V, E)是n阶边赋权图, V = {v1, v2, …, vn}, 用wij表示节点vi到vj的边上的权,若vi到vj无边, 则令wij= +. 目标: 求节点v1到其他任意节点的最短路径.

Dijkstra算法将V划分成两部分P和T, P表示永久性节点集,而T = V - P称为临时节点集 Dijkstra算法将V划分成两部分P和T, P表示永久性节点集,而T = V - P称为临时节点集. 对P的每节点v进行P标号l(v), l(v)表示节点v1到v的最短路径的权; 而T中每节点v的T标号l(v), l(v)表示节点v1到v的一条路上的权. Dijkstra算法: Step 1 令P = {v1}且v1进行P标号l(v1), 对T = V- P中节点进行T标号l(vj) = w1j, j = 2, 3, …, n. Step 2 在所有T标号的节点中,选取最小标号节点vi进入P.

Step 3 重新按下列方式计算具有T标号的其他节点vj的T标号: Step 4 重复上述步骤, 直至|P| = n. 例7-10(P218): Figure 7-39(a)

正确性? 复杂度分析? 算法实现?

Solution v5所在列7/ v3表示v3在v1到v5的最短路径上,并且与v3邻接,依此类推. 2 3 4 5 6 2/ v1 4/ v2 3/v1  8 7/ v3 9 8/v5 14 13/ v6

(b)Dijkstra算法既适合于无向图,也适合于有向图. v1 v2 v3 v4 v5 v6 1 2 3 4 5 1/ v1 3/ v2  8 7/ v5 6 4/v3 10 9/v5

Warshall算法是由Warshall给出并经R. W Warshall算法是由Warshall给出并经R. W. Floyd(弗洛伊德)改进的算法, 它可求出任意两个点之间的最短路径,也可参见文献[13]. Warshall算法? 关键路径(critical path)?