数据结构 第7章 图.

Presentation on theme: "数据结构 第7章 图."— Presentation transcript:

1 数据结构 第7章 图

2 第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用
7.6 最短路经

3 第7章 图 离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。 图是较线性表和树更为复杂的数据结构，除了在遍历图的同时对顶点或弧进行各种操作以外，本章还重点介绍几个常用算法在计算机中的具体实现。

4 7.1 图的定义和术语 图的抽象数据类型定义如下： ADT Graph { 数据对象： V是具有相同特性的数据元素的集合，称为顶点集。
　数据关系： 　　VR＝{<v,w>| v,w∈V且P(v,w)，<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息 }

5 7.1 图的定义和术语 基本操作P： {结构初始化} CreateGraph(&G, V, VR);
　{结构初始化} 　　CreateGraph(&G, V, VR); 　　　初始条件：V 是图的顶点集，VR 是图中弧的集合。 　　　操作结果：按 V 和 VR 的定义构造图 G。 　{销毁结构} 　　DestroyGraph(&G); 　　　初始条件：图 G 存在。 　　　操作结果：销毁图 G。 　{引用型操作} 　　LocateVex(G, u); 　　　初始条件：图 G 存在，u 和 G 中顶点有相同特征。 　　　操作结果：若 G 中存在和 u 相同的顶点，则返回该顶点在图中位置；否则返回其它信息。 　　GetVex(G, v); 　　　初始条件：图 G 存在，v 是 G 中某个顶点。 　　　操作结果：返回 v 的值。 　　FirstAdjVex(G, v); 　　　操作结果：返回 v 的第一个邻接点。若该顶点在 G 中没有邻接点，则返回"空"。 　　NextAdjVex(G, v, w); 　　　初始条件：图 G 存在，v 是 G 中某个顶点，w 是 v 的邻接顶点。 　　　操作结果：返回 v 的（相对于 w 的）下一个邻接点。若 w 是 v 的最后一个邻接点，则返回"空"。

6 7.1 图的定义和术语 …… {加工型操作} PutVex(&G, v, value); 初始条件：图 G 存在，v 是 G 中某个顶点。
　{加工型操作} 　　PutVex(&G, v, value); 　　　初始条件：图 G 存在，v 是 G 中某个顶点。 　　　操作结果：对 v 赋值 value。 　　InsertVex(&G, v); 　　　初始条件：图 G 存在，v 和图中顶点有相同特征。 　　　操作结果：在图 G 中增添新顶点 v。 　　DeleteVex(&G, v); 　　　操作结果：删除 G 中顶点 v 及其相关的弧。 　　InsertArc(&G, v, w); 　　　初始条件：图 G 存在，v 和 w 是 G 中两个顶点。 　　　操作结果：在 G 中增添弧<v,w>，若 G 是无向的，则还增添对称弧<w,v>。 　　DeleteArc(&G, v, w); 　　　操作结果：在 G 中删除弧<v,w>，若 G 是无向的，则还删除对称弧<w,v>。 　　DFSTraverse(G, Visit()); 　　　初始条件：图 G 存在，Visit 是顶点的应用函数。 　　　操作结果：对图 G 进行深度优先遍历。遍历过程中对每个顶点调用函数Visit 一次且仅一次。一旦 visit() 失败，则操作失败。 　　BFSTraverse(G, Visit()); 　　　操作结果：对图 G 进行广度优先遍历。遍历过程中对每个顶点调用函数Visit 一次且仅一次。一旦 visit() 失败，则操作失败。 } ADT Graph

7 7.1 图的定义和术语 图由一个顶点集和弧集构成，通常写作：Graph=(V,VR)。由于空的图在实际应用中没有意义，因此一般不讨论空的图，即V是顶点的有穷非空集合。 <v,w>表示从顶点 v 到顶点 w 的一条弧，其中顶点 v 被称为弧尾，顶点 w 被称作弧头。由于弧是有方向的，故称有向图。 例如下列定义的有向图如右图所示。 G1=(V1, VR1) 其中：V1 = {A, B, C, D, E} VR1= {<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>} 若<v,w>∈R 必有<w,v>∈R，则称 (v,w) 为顶点 v 和顶点 w 之间存在一条边。由顶点集和边集构成的图称作无向图。 例如下列定义的无向图如右所示。 G2=(V2, VR2) 其中：V2={A, B, C, D, E, F} VR2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F) }

8 7.1 图的定义和术语 数学上的定义： 图（graph）G是一个序偶<V, E>， 其中 V是一个非空有限集合， 称为图G的点集， E称为图G的弧集。

9 7.1 图的定义和术语 几个有关图的常用术语 顶点的度 对无向图而言，邻接点的个数定义为顶点的度。 对有向图而言，顶点的度为其出度和入度之和，其中出度定义为以该顶点为弧尾的弧的个数，入度定义为以该顶点为弧头的弧的个数。 子图 假设有两个图 G=(V,E) 和G‘=(V’,E‘)，如果V’ is a subset of V 且 E’ is a subset of E，则称 G‘为G的子图(subgraph)。 路径和回路 若有向图 G 中 k+1 个顶点之间都有弧存在（即<v0,v1>, <v1,v2>, … <vk-1,vk> 都是图 G 中的弧），则这个顶点的序列 { v0,v1,…,vk } 为从顶点v0到顶点vk的一条有向路径，路径中弧的数目定义为路径长度，若序列中的顶点都不相同，则为简单路径。对无向图，相邻顶点之间存在边的 k+1 个顶点序列构成一条长度为 k 的无向路径。如果v0和vk是同一个顶点，则是一条由某个顶点出发又回到自身的路径，称这种路径为回路或环。

10 7.1 图的定义和术语 几个有关图的常用术语 连通图和连通分量、强连通图和强连通分量 若无向图中任意两个顶点之间都存在一条无向路径，则称该无向图为连通图，否则称为非连通图。若有向图中任意两个顶点之间都存在一条有向路径，则称该有向图为强连通图。 非连通图中各个极大连通子图称作该图的连通分量。非强连通的有向图中的极大强连通子图称作有向图的强连通分量。 生成树和生成森林 一个含 n 个顶点的连通图的生成树是该图中的一个极小连通子图，它包含图中 n 个顶点和足以构成一棵树的 n-1 条边。对于非连通图，对其每个连通分量可以构造一棵生成树，合成起来就是一个生成森林。 无向网和有向网 在实际应用中，图的弧或边往往与具有一定意义的数相关，称这些数为"权"，分别称带权的有向图和无向图为有向网和无向网。

11 7.2 图的存储结构 7.2.1 数组表示法（邻接矩阵） 7.2.2 邻接表 7.2.3 十字链表 7.2.4 邻接多重表

12 7.2.1 数组表示法 假设图中顶点数为n，则邻接矩阵A=(ai,j) 定义为 ai,j=1 若vi和vj有弧或边存在 ai,j=0 否则
将图的顶点信息存储在一个一维数组中，并将它的邻接矩阵存储在一个二维数组中即构成图的数组表示。

13 7.2.1 数组表示法 图的数组(邻接矩阵)存储表示 const INFINITY = INT_MAX; // 最大值∞
　　const MAX_VERTEX_NUM = 20;　　　　// 最大顶点个数 　　typedef enum {DG, DN, AG, AN} GraphKind; 　　　　　　　　　　　　　　　// 类型标志{有向图,有向网,无向图,无向网} 　　typedef struct ArcCell { 　　　　// 弧的定义 　　　VRType adj; 　　　　　　　　　　// VRType是顶点关系类型。 　　　　　　　　　// 对无权图，用1或0表示相邻否；对带权图，则为权值类型。 　　　InfoType *info; 　　　　　　　　// 该弧相关信息的指针 　　} AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 　　typedef struct { 　　　　　　　// 图的定义 　　　VertexType vexs[MAX_VERTEX_NUM]; // 顶点信息 　　　AdjMatrix arcs; 　　　　　　　　// 表示顶点之间关系的二维数组 　　　int vexnum, arcnum; 　　　　　　// 图的当前顶点数和弧(边)数 　　　GraphKind kind; 　　　　　　　　// 图的种类标志 　　} MGraph;

14 7.2.1 数组表示法 无向图的数组表示存储结构 有向图的数组表示存储结构

15 7.2.2 邻接表 类似于树的孩子链表，将和同一顶点"相邻接"的所有邻接点链接在一个单链表中，单链表的头指针则和顶点信息一起存储在一个一维数组中。

16 7.2.2 邻接表 图的邻接表存储表示 const MAX_VERTEX_NUM = 20;
　　typedef struct ArcNode__ { 　　　// 弧结点的结构 　　　int adjvex; 　　　　　　　　　// 该弧所指向的顶点的位置 　　　struct ArcNode__ *nextarc;　　　// 指向下一条弧的指针 　　　VRType weight;　　　　　　　　// 与弧相关的权值，无权则为0 　　　InfoType *info; 　　　　　　　// 指向该弧相关信息的指针 　　} ArcNode; 　　typedef struct VNode {　　　　// 顶点结点的结构 　　　VertexType data;　　　　　　　// 顶点信息 　　　ArcNode *firstarc;　　　　　　// 指向第一条依附该顶点的弧 　　} AdjList[MAX_VERTEX_NUM]; 　　typedef struct { 　　　　　　// 图的邻接表结构定义 　　　AdjList vertices;　　　　　　// 顶点数组 　　　int vexnum, arcnum;　　　　　// 图的当前顶点数和弧数 　　　GraphKind kind;　　　　　　　// 图的种类标志 　　} ALGraph;

17 7.2.2 邻接表 有向图的邻接表中链接在每个顶点结点中的都是以该顶点为弧尾的弧，每个单链表中的弧结点的个数恰为弧尾顶点的出度，每一条弧在邻接表中只出现一次。虽然在邻接表中也能找到所有以某个顶点为弧头的弧，但必须查询整个邻接表。 若在应用问题中主要是对以某个顶点为弧头的弧进行操作，则可以为该有向图建立一个"逆邻接表"。

18 7.2.3 十字链表 十字链表是有向图的另一种存储结构，目的是将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结点表示，由于该弧在邻接表和逆邻接表中的顶点数据是相同的，因此十字链表中只需要出现一次，但需保留分别指向第一条"出弧"和第一条"入弧"的指针。

19 7.2.3 十字链表 7.2.1中的有向图的十字链表如下所示

20 7.2.3 十字链表 有向图的十字链表存储表示 const MAX_VERTEX_NUM = 20;
　　typedef struct ArcBox { 　　　// 弧结点结构定义 　　　int tailvex, headvex; 　　　　// 该弧的尾和头顶点的位置 　　　struct ArcBox *hlink, *tlink; // 分别为弧头相同和弧尾相同的弧的链域 　　　VRType weight;　　　　　　　　// 与弧相关的权值，无权则为0 　　　InfoType *info; 　　　　　　　// 该弧相关信息的指针 　　} ArcBox; 　　typedef struct VexNode {　　　// 顶点结点结构定义 　　　VertexType data; 　　　ArcBox *firstin, *firstout;　 // 分别指向该顶点第一条入弧和出弧 　　} VexNode; 　　typedef struct { 　　　　　　// 十字链表结构定义 　　　VexNode xlist[MAX_VERTEX_NUM]; // 表头向量 　　　int vexnum, arcnum;　　　　　// 有向图的当前顶点数和弧数 　　　GraphKind kind;　　　　　　　// 图的种类标志 　　} OLGraph;

21 7.2.4 邻接多重表 类似于有向图的十字链表，若将无向图中表示同一条边的两个结点合在一起，将得到无向图的另一种表示方法--邻接多重表。

22 7.2.4 邻接多重表 7.2.1中无向图的邻接多重表如下所示

23 7.2.4 邻接多重表 无向图的邻接多重表存储表示 const MAX_VERTEX_NUM = 20;
　　typedef emnu {unvisited, visited} VisitIf; 　　typedef struct EdgeNode{ 　　　　// 边结点结构定义 　　　VisitIf mark; 　　　　　　　　　// 访问标记 　　　int ivex, jvex; 　　　　　　　　// 该边依附的两个顶点的位置 　　　struct EdgeNode *ilink, *jlink; // 分别指向依附这两个顶点的下一条边 　　　VRType weight; 　　　　　　　　 // 与弧相关的权值，无权则为0 　　　InfoType *info; 　　　　　　　　// 与该边相关信息的指针 　　} ; 　　typedef struct { 　　　　　　　// 顶点结点结构定义 　　　VertexType data; 　　　EdgeNode *firstedge;　　　　　　// 指向第一条依附该顶点的边 　　} VexNode; 　　typedef struct { 　　　　　　　// 多重链表结构定义 　　　VexNode adjmulist[MAX_VERTEX_NUM]; 　　　int vexnum, edgenum;　　　　　　// 无向图的当前顶点数和边数 　　　GraphKind kind; 　　　　　　　　// 图的种类标志 　　} AMLGraph;

24 四种比较： 数组表示法 邻接表 十字链表 邻接多重表

25 7.3 图的遍历 与二叉树和树的遍历相同，图的"遍历"是对图中的每个顶点都进行一次访问且仅进行一次访问。但由于图结构较树和二叉树更为复杂，图中任意两个顶点之间都可能存在一条弧或边，反之也可能存在某个顶点和其它顶点之间都不存在弧或边。因此对图的遍历而言，除了要确定一条搜索路径之外，还要解决两个问题：(1)如何确保每个顶点都被访问到；(2)如何确保每个顶点只被访问一次。

26 7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索

27 7.3.1 深度优先搜索 深度优先搜索DFS ( Depth First Search )，类似于树的前序（先根）遍历。 访问方式：
1、选中第一个被访问的结点。 2、对结点作已访问过的标志。 3、依次从结点的未被访问过的第一个、第二个、第三个…… 邻接结点出发，进行深度优先搜索。转向2。 4、如果还有顶点未被访问，则选中一个起始结点，转向2。 5、所有的结点都被访问到，则结束。

28 7.3.1 深度优先搜索 对于图的遍历，为了确保每个顶点在遍历过程中只被访问一次，需要为每个顶点建立一个“访问标志 visited[i]”，在遍历开始之前，将它们设为 “FALSE”，一旦第i个顶点被访问，则令 visited[i] 为 “TRUE”。 结点的邻接结点的次序是任意的，因此深度优先搜索的序列可能有多种。

29 7.3.1 深度优先搜索 从结点1出发的搜索序列： 从结点5出发的搜索序列： 6 2 1 5 7 4 3 · 5 · 6 · 7 · 1 ·

30 7.3.1 深度优先搜索 以邻接表为存储结构的深度优先搜索遍历的算法 void DFSTraverse(ALGraph G) {
　　bool visited[G.vexnum]; 　　　// 附设访问标识数组 　　for (v=0; v<G.vexnum; ++v) 　　　visited[v] = FALSE; 　　　　// 访问标识数组初始化 　　　if (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用DFS } 　 时间复杂性： 邻接矩阵：O（n2） 邻接表： O（n + e） n：结点数 e：边数 void DFS(ALGraph G, int v){ 　　// 从第v个顶点出发递归地对图G进行深度优先搜索 　　VisitFunc(G.vertices[v].data); 　// 访问第 v 个顶点 　　visited[v] = TRUE; 　　　　　　// 设访问标志 　　for ( p=G.vertices[ v ].firstarc; p; p=p->nextarc; ){ 　// p 为指向弧结点的指针 　　　w = p->adjvex; 　　　if (!visited[w]) DFS(G, w);// 对v的尚未访问过的邻接顶点w递归调用DFS 　　} // for } // DFS

31 7.3.2 广度优先搜索 广度（宽度）优先搜索( Breadth First Search) 访问方式： 1、选中第一个被访问的结点 V
3、依次从结点 V 的未被访问过的第一个、第二个、第三个……第 M个邻接结点 W1 、W2、W3…… Wm ，且进行标记。 4、依次访问结点 W1 、W2、W3…… Wm的邻接结点，且进行标记。 5、如果还有结点未被访问，则选中一个起始结点，也标记为V，转向2。 6、所有的结点都被访问到，则结束。

32 7.3.2 广度优先搜索 树的按层次进行访问的次序： A、B、C、D、E、F、 G、H、I、J、K、L 适用的数据结构：队列 A C D B
5、结点B的儿子结点E、F、G访问后进队 6、结点C出队 7、结点C的儿子结点H访问后进队 …………………. C D C D E F G D E F G D E F G H

33 7.3.2 广度优先搜索 无向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。 · · · · · · · · · ·
1 1 12 11 11 2 2 12 3 6 7 10 3 6 7 10 4 5 8 9 4 5 8 9 时间复杂性： 邻接矩阵：O（n2） 邻接表： O（n + e） n：结点数 e：边数 图的广度优先的访问次序： 1、2、11、12、3、6、7、10、4、5、8、9

34 7.3.2 广度优先搜索 void BFSTraverse(MGraph G) { // 对以数组存储表示的图G进行广度优先搜索遍历
　　bool visited[G.vexnum];　　　　　　　　　　　// 附设访问标识数组 　　Queue Q;　　　　　　　　　　　　　　　　　　// 附设队列 Q 　　for (v=0; v<G.vexnum; ++v) visited[v] = FALSE; 　　InitQueue(Q，G.vexnum);　　　　　　　　　　　// 设置空队列 Q 　　for ( v=0; v<G.vexnum; ++v ) 　　　if ( !visited[v]) 　{ 　　　　　　　　// 从每一个未被访问的顶点出发进行广度优先搜索 　 　 　　 visited[v] = TRUE; VisitFunc(G.vexs[v]);　// 访问图中第 v 个顶点 　　　　EnQueue(Q, v); 　　　　　　　　　　　　　// v 入队列 　　　　while (!QueueEmpty(Q)) { 　　　　　DeQueue(Q, u); 　　　　　　　　　　　　// 队头元素出队并置为 u 　　　　　for ( w=0; w<G.vexnum; w++; ) 　　　　　　if ( G.arcs[u, w].adj && ! visited[w] ) { 　　　　　　　visited[w] = TRUE; VisitFunc(w);　　// 访问图中第 w 个顶点 　　　　　　　EnQueue(Q, w); 　　　　　　　　// 当前访问的顶点 w 入队列 Q 　　　　　} // if 　　　　} // while 　　　} // if 　　DestroyQueue(Q); 　} // BFSTraverse

35 7.4 图的连通性问题 7.4.1 无向图的连同分量和生成树 7.4.2 有向图的强连同分量 7.4.3 最小生成树
7.4.4 关节点和重连同分量

36 7.4.1 无向图的连同分量和生成树 连通：顶点v至v’之间有路径存在 连通图：无向图图 G 的任意两点之间都是连通的，则称 G 是连通图。
连通分量：极大连通子图 无向图G的三个连通分量 无向图G A B A B F G E F G E H I J H K L I J M M K L C D C D

37 7.4.1 无向图的连同分量和生成树 生成树：极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添 加一条边之后，必定会形成回路或环。因为在生成树的任意两点之间，本来就 是连通的，添加一条变之后，形成了这两点之间的第二条通路。 无向图G 无向图G的生成树 A B A B E E H H M M C D C D 生成方法：进行深度为主的遍历或广度为主的遍历，得到深度优先生成树或广度优先生 成树。 生成森林：在进行深度为主的遍历或广度为主的遍历时，对于非连通图，将得到多棵深 度优先生成树或广度优先生成树。称之为生成森林。

38 7.4.1 无向图的连同分量和生成树 生成森林：在进行深度为主的遍历或广度为主的遍历时，对于非连通图，将得到多棵深
度优先生成树或广度优先生成树。称之为生成森林。 无向图G 无向图G的生成森林 A B A B F G E F G E H I J H K L I J M M K L C D C D

39 7.4.2 有向图的强连同分量 深度优先搜索是求有向图的强连同分量的一个有效方法。

40 7.4.3 最小生成树 最小代价生成树（简称：最小生成树） Minimum Cost Spanning Tree
定义：生成树中边的权值（代价）之和最小的树。 实例： 左图的最小代价生成树 1 1 5 6 1 1 2 5 3 5 4 2 5 3 4 6 4 4 3 2 3 2 5 6 6 5 6 MST 性质： 假设 G = {V, { E } } 是一个连通图，U 是结点集合 V 的一个非空子集。若 ( u, v ) 是 一条代价最小的边，且 u 属于 U , v 属于 V - U，则必存在一棵包括边 ( u, v ) 在内 的最小代价生成树。

41 7.4.3 最小生成树 证明：假定存在一棵不包括边 ( u, v ) 在内的最小代价生成树，设其为 T。将边( u, v )
添加到树 T ，则形成一条包含 ( u, v ) 的回路。因此，必定存在另一条边 ( u‘ ，v‘ ) ，且 u’ 属于 U , v ‘ 属于 V - U。删去边 ( u‘ ，v‘ ) ，得到另一棵生成 树 T ‘ ; 因为边 ( u, v ) 的代价小于边 ( u‘ ，v‘ ) 的代价，所以新的生成树T ‘ 将是代价最小的树。和原假设矛盾。 新的生成树T‘ 是树的理由：连通且无回路。 T v u v’ u’

42 7.4.3 最小生成树 Kruscal 算法 1 1 2 3 4 2 3 4 5 6 5 6 最小代价生成树 5 6 5 1 1 5 5 5

43 7.4.3 最小生成树 Kruscal 算法的实现 Kruscal 算法的基本描述
设 U：set of vertex, G: Graph, T: mininum cost spanning tree ; u, v : vertex; V: set of vertex; E：set of edges //初始时，V 包含所有结点 { T ＝ { V , φ }; // T 初始时具有 n 个不同的连通分量，每个分量只有一个结点。 T 的边数 ＝ n - 1 吗？等则结束 在 E 中选择代价最小的边，令为 ( u,v ) 。并置 E ＝ E － ( u,v )。 如果 ( u,v ) 不和 T 中已有的边构成回路，则 T ＝ T ∪ ( u,v )，否则放弃。转回 } 数据结构：用邻接表标识该图，用堆实现挑选代价最小的边。 时间复杂性级别：O(eloge)，用于稀疏图。

44 7.4.3 最小生成树 克鲁斯卡尔(Kruskal)算法 typedef struct { VertexType vex1;
　　　VRType weight; }EdgeType; typedef ElemType EdgeType; typedef struct { 　　　　　　　　// 有向网的定义 　　　VertexType vexs[MAX_VERTEX_NUM]; 　// 顶点信息 　　　EdgeType edge[MAX_EDGE_NUM]; 　　　// 边的信息 　　　int vexnum,arcnum;　　　　　　　　// 图中顶点的数目和边的数目 }ELGraph;

45 7.4.3 最小生成树 克鲁斯卡尔(Kruskal)算法（续）
void MiniSpanTree_Kruskal(ELGraph G, SqList& MSTree)　{ 　　// G.edge 中依权值从小到大存放有向网中各边，按克鲁斯卡尔 算法求得生成树的边存放在顺序表 MSTree 中 　　MFSet F; 　　InitSet(F, G.vexnum);　　　　　　　　　// 将森林F初始化为n棵树的集合 　　InitList(MSTree, G.vexnum);　　　　　　// 初始化生成树为空树 　　i=0; k=1; 　　while( k<G.vexnum ) { 　　　e = G.edge[i];　　　　　　　　　　　// 取第 i 条权值最小的边 　　　r1 = fix_mfset(F, LocateVex(e.vex1)); 　　　r2 = fix_mfset(F, LocateVex(e.vex2)); // 返回两个顶点所在树的树根 　　　if (r1 != r2) { 　　　　　　　　　　// 选定生成树上第k条边 　　　　if (ListInsert(MSTree, k, e)) k++;　// 插入生成树 　　　　mix_mfset(F, r1, r2);　　　　　　　// 将两棵树归并为一棵树 　　　} // if 　　　i++; 　　　　　　　　　　　　　　　// 继续考察下一条权值最小边 　　} // while 　　DestroySet(F); 　} // MiniSpanTree_Kruskal

46 7.4.3 最小生成树 Prim 算法 Prim 算法的基本描述
设 U：set of vertex, G: Graph, T: set of edges(mininum cost spanning tree; u, v : vertex; V: set of vertex; //初始时，V 包含所有结点 { T ＝ φ；U ＝ { 1 }; 由于 1 在 U 中，其余各结点都在 V－U 中，可用一数组记录 V－U中的结点至 的路径。因为它们构成了当前横跨 U 和 V－U 两个集合的所有的边。 while ( U != V ) { 设 ( u,v ) 是一条代价最小的边，并且 u 在 U 中，v 在 V - U中。 T = T ∪ ( u,v )；U = U ∪ { v }; 由于 u 已在 U 中，查找 由 u 至它的仍在 V－U中的邻接结点的路径，若 小于原来相应的数组元素记录的最小值，则用该值数组元素之值。 } Prim 算法 时间代价分析：邻接矩阵：时间复杂性 O（n2），和边数无关。用于稠密图。 邻接表且使用最小化堆：时间复杂性 O((n+e)logn)。

47 7.4.3 最小生成树 Prim 算法的实例 U 1 1 2 3 4 2 3 4 5 6 5 6 最小代价生成树的生成过程 5 5 6 6

48 7.4.3 最小生成树 Prim 算法的实例 U 1 1 2 3 4 2 3 4 5 6 5 6 最小代价生成树的生成过程 5 5 6 6

49 7.4.3 最小生成树 Prim 算法的实例 U 1 1 2 3 4 2 3 4 5 6 5 6 最小代价生成树的生成过程 5 5 6 6

50 7.4.3 最小生成树 Prim 算法的实例 U 1 1 2 3 4 2 3 4 5 6 5 6 最小代价生成树的生成过程 5 5 6 6

51 7.4.3 最小生成树 Prim 算法的实例 U 1 1 2 3 4 2 3 4 5 6 5 6 最小代价生成树的生成过程 5 5 6 6

52 7.4.3 最小生成树 Prim 算法的实例 U 1 1 2 3 4 2 3 4 5 6 5 6 最小代价生成树的生成过程 5 5 6 6

53 7.4.3 最小生成树 Prim 算法的实例 U 1 1 2 3 4 2 3 4 5 6 5 6 最小代价生成树的生成过程 5 5 6 6

54 7.4.3 最小生成树 Prim 算法的实例 U 1 1 2 3 4 2 3 4 5 6 5 6 最小代价生成树的生成过程 5 5 6 6

55 7.4.3 最小生成树 Prim 算法的实例 U 1 1 2 3 4 2 3 4 5 6 5 6 最小代价生成树的生成过程 5 5 6 6

56 7.4.3 最小生成树 Prim 算法的实例 U 1 1 2 3 4 2 3 4 5 6 5 6 最小代价生成树的生成过程 5 5 6 6

57 7.4.3 最小生成树 Prim 算法的实例 U 1 1 2 3 4 2 3 4 5 6 5 6 最小代价生成树的生成过程
要点：每当新的结点并入 U 之后，则调整仍在 V - U 集合中的结点至 U 中结点的最小距离。

58 7.4.3 最小生成树 1、最小代价生成树（简称：最小生成树） Prim 算法数据结构： 1 1 1 2 3 4 2 3 4 2 3 4 5
U 1 1 1 U 5 5 5 6 6 6 1 1 1 2 5 3 5 4 2 5 3 5 4 2 5 3 5 4 6 4 6 4 6 4 3 2 3 2 3 2 5 6 6 5 6 6 5 6 6 图G 图G 图G 注意：lowcost [ j ] 表示在 V－U 中的结点 j 到 U 中的结点的 最短距离。 nearvex[ j ]: if 值为 -1, 表 示相应结点 j 已在 U 之中。 否则,表示结点 j 和 U 中的结 点 k = nearvex[ j ] 距离是最 短的， 且为 Lowcost [ j ]。 因结点j到U中结点路径有多条 -1 1 2 3 4 5 1 2 3 4 5 -1 6 5 2 1 1 -1 5 5 ∞ 6 2 ∞ 4 2 lowcost nearvex lowcost nearvex 值为1,2,3,4,5,6de 结点，用下标0,1,2,3,4,5标识。

59 7.4.4 关节点和重连同分量 T － 树边：(v1,v2)、 (v1,v5)、 (v2,v3)、 (v2,v4)、 (v5,v6)
B － 后向边：(v3,v1) 、(v4,v1)、 (v6,v1) 注意：子图 (V,T) 是一个无向森林，称为关于 G 的先深生成森林。如仅一棵树的情况下， (V,T) 称为先深生成树。 如 G 是连通的，则这个先深生成森林将是一棵树。

60 7.4.4 关节点和重连同分量 关节点：设 G＝（V，E）是一个连通无向图。一个结点 a 若说是 G 的一个关节点。则 存在和 a 不同的结点 v、w, v、w 之间的每一条路径都包含结点 a。或者换句话 说，a 是 G 的一个关节点，如果移去 a 就把 G 分裂成两个或两个以上的部分。 重连通图：图 G 是重连通的，如对于互不相同的结点 v、w、a 的每个三元组都存在 一条由 v 到 w 的不含 a 的路径。即一个无向图是重连通的，当且仅当它 没有关节点。 无向图G A B C E D F G H 关节点：A、B、D、G I K J L M

61 7.5 有向无环图及其应用 何为有向无环图（DAG 图） Directed Acyclic Graph B B B E F G E F G
有向树 DAG图 有向图（含环）

62 7.5 有向无环图及其应用 用途：描述工程项目或系统进行的工具
AOV 网络：(Activity On Vertex)定义结点为活动，有向边的指向表示活动执行的次序。 AOE网络：(Activity On Edge)定义结点为事件，有向边的指向表示事件的执行次序。单位是时间（时刻）。有向边定义为活动，它的权值定义为活动进行所需要的时间。 A B 10 A B

63 7.5.1拓扑排序 拓扑排序（Topological Sort） 由某个集合上的一个偏序得到该集合上的一个全序。
偏序(Partial Order)：若集合 X 上的关系 R 是传递的、自反的、反对称的，则称 R 是集合 X 上的偏序关系。 全序(Total Order)：若关系 R 是集合 X 上的偏序关系，如果对于每个 x, y 属于 X，必有 x R y 或 y R x ，则称 R 是集合 X 上的全序关系。

64 7.5.1拓扑排序 拓扑排序：由某个集合上的一个偏序关系通过人为地加上一些关系得到该集合上的一个全序。
用途：描述工程项目或系统进行的次序 AOV 网络：定义结点为活动，有向边的指向表示活动执行的次序。

65 7.5.1拓扑排序 实例：下述集合 M 代表课程的集合，其中，1代表数学， 2代表程序设计，3代表离散数学，4代表汇编程序设计，5代表数据结构，6代表结构程序设计, 7代表编译原理。 关系 R 课程学习的先后关系，如数学必须在离散数学之前学习。要求排一张学习的先后次序表。 数学 1 序列：1、3、2、4、6、5、7 合乎拓扑排序的要求 离散数学 程序设计 3 2 汇编程序设计 7 5 4 数据结构 编译原理 6 序列：3、1、2、4、6、5、7 不合乎拓扑排序的要求 结构程序设计

66 7.5.1拓扑排序 那么如何进行拓扑排序？步骤如下： （1） 在AOV网中选择一个没有前驱的顶点并输出；
重复以上两步直至AOV网变空（即已输出所有顶点）或者剩余子图中不存在没有前驱的顶点。后一种情况则说明该AOV网中含有向环。

67 7.5.1拓扑排序 实例：课程学习先后关系的排序。 数学 1 1 离散数学 程序设计 3 2 3 2 数据结构 汇编程序设计 7 5 4 7
编译原理 6 6 结构程序设计 1 3 2 4 6 5 7

68 7.5.1拓扑排序 算法（使用邻接表） 01234 0123456 56 算法的执行步骤：
1、用一个数组记录每个结点的入度。将入度为零的结点进栈。 2、将栈中入度为零的结点V输出。 3、根据邻接表找到结点V的所有的邻接结点，并将这些邻接结点的入度减一。如果某一结点的入度变为零，则进栈。 4、反复执行 2、3；直至栈空为止。 ………………… 次序执行结束，如果输出结点数等于图的结点总数，则有向图无环，否则有向图有环 算法（使用邻接表） 1 数学 程序设计 离散数学 3 2 汇编程序设计 数据结构 编译原理 7 5 4 栈 01234 56 1 2 6 1 null 结构程序设计 2 3 1 4 5 null 3 4 1 6 null 4 null 1 注意： 0,1,2,3,4,5,6 分别标识结点 1,2,3,4,5,6,7 5 2 6 null 6 1 3 null 7 null 3 indegree

69 7.5.1拓扑排序 算法（使用邻接矩阵） 算法的执行步骤： 1、找到全为零的第 j 列，输出 j 2、将第 j 行的全部元素置为零
3、找到全为零的第 k 列，输出 k 4、将第 k 行的全部元素置为零 ………………… 反复执行 3、4；直至所有元素输出完毕。 算法（使用邻接矩阵） 1 数学 程序设计 离散数学 3 2 汇编程序设计 1 2 3 4 5 6 7 数据结构 编译原理 7 5 4 6 结构程序设计

70 7.5.1拓扑排序 算法描述如下（使用邻接表） 建有向图的邻接表并统计各顶点的入度； InitStack(S); // 初始化S为空栈
　　建有向图的邻接表并统计各顶点的入度； 　　InitStack(S); 　　　　　　　　　// 初始化S为空栈 　　将当前所有入度为零的顶点入栈; 　　m=0; 　　　　　　　　　　　　　// 以 m 记输出的顶点个数 　　while (!StackEmpty(S)) { 　　　// 尚有入度为零的顶点存在 　　　Pop(S,v); 　　　输出 v ; ++m; 　　　　　　// 输出入度为零的顶点，并计数 　　　w = FirstAdj(G,v);　　　　　　// w 为 v 的邻接点 　　　while (w<>0) {　　　　　　　// 将v 的所有邻接点的入度减1 inDegree[w]--; 　　　　　　// w 的入度减一 if( 0==inDegree[w]) Push(S,w); w = nextAdj(G,v,w);　　　　// 取 v 的下一个邻接点 　　　} // while w 　　} // while S 　　if (m<n) printf(“图中有回路”); // 输出的顶点数不足图中顶点数 　　DestroyStack(S);

71 7.5.2 关键路径 关键路径: AOE 网络的应用 用途：估算工程项目完成时间
术语： 源点：表示整个工程的开始点，也称起点。 收点：表示整个工程的结束点，也称汇点。 事件结点：单位时间，表示的是时刻。 活动（有向边）：它的权值定义为活动进行所需要的时间。方向表示起始结点事件先发生，然后终止结点事件才能发生。

72 7.5.2 关键路径 一个实例： 待解决的问题 源点：v1 收点：v6 完成整项工程至少需要多少时间？ 哪些活动是影响工程进度的关键？ V5
3 5 1 2 1 V1 V3 V6 2 V4

73 7.5.2 关键路径 术语： 事件的最早发生时间（Ve(j)）：从起点到本结点的最长的路径。意味着事件最早能够发生的时刻。
事件的最迟发生时间（V l (j)）：不影响工程的如期完工（汇点的最早完成时间），本结点事件必须发发生的时刻。 活动的最早开始时间：e(ai ) = Ve( j ) 活动的最迟开始时间： l (ai ) = V l( k ) - dut( j , k ) 关键活动：最早开始时间 ＝ 最迟开始时间的活动 关键路径：从源点到收点的最长的一条路径，或者全部由关键活动构成的路径。 dut(j,k) j k ai 1 5 12 88 2 4 3 7 收点 起点: 1010 V1 VJ Vj Vn Vl(Vj) = 取 10-2、10-4、10-3、10-7的最小值 3;或 10 - 最长路径 7 Ve(Vj) = 88 取 1、5、12、88的最大值 88

74 7.5.2 关键路径 Ve(j) 的求法： 3 5 12 88 V1 VJ 起点:0 Ve(Vj) = 3、5、12、88的最大值 88 2
注意：本图说明由已知的所有的起始结点的 Ve ，可得知终止结点的 Ve 。 如：从Ve(Vu) 、Ve (Vv) 、 Ve (Vw) 、 Ve (Vx) 可知Ve(Vj) 由源点至收点 Vu 3 1 Vv 2 9 3 V1 Vw VJ 82 6 注意：开始时只有源点的 Ve ＝ 0 已知，利用拓扑排序的序列可得到每一个结点的 Ve 。且结点的 Ve 确定次序和拓扑排序的序列相同。 Vx Ve(Vj) = Vj 的起始结点的最早发生时间 + 各自的边的权值中的和的最大值 88

75 7.5.2 关键路径 求事件的最早发生时间的实例 2 利用拓扑排序算法求事件结点的最早发生时间的执行步骤：
2 利用拓扑排序算法求事件结点的最早发生时间的执行步骤： 1、设每个结点的最早发生时间为0，将入度为零的结点进栈。 2、将栈中入度为零的结点V取出，并压入另一栈，用于形成逆向拓扑排序的序列。。 3、根据邻接表找到结点V的所有的邻接结点，将结点V的最早发生时间 + 活动的权值 得到的和同邻接结点的原最早发生时间进行比较；如果该值大，则用该值取代原最早发生时间。另外，将这些邻接结点的入度减一。如果某一结点的入度变为零，则进栈。 4、反复执行 2、3；直至栈空为止。 V5 V2 1 1 3 5 2 1 V1 V3 V6 2 V4 1 3、 6 2 V5 V2 1 1 2 1 3、 3 5、 7、 8 3 2 V1 V3 V6 2 5 1 V4 正向拓扑排序： 5、 5 V1 V2 V3 V4 V5 V6

76 7.5.2 关键路径 2 4 3 7 Vl(j) 的求法： 收点 1010 Vj Vn Vl(Vj) = 取 10-2、10-4、10-3、10-7的最小值 3 注意：本图说明由已知的所有的终止结点的 Vl ，可得知起始结点的 Vl 。 如：从Vl(Vu) 、Vl (Vv) 、 Vl (Vw) 、 Vl (Vx) 可知 Vl(Vj) 由收点至源点 9 Vu 1 8 收点 2 Vv 1010 Vj Vn 1 8 Vw 注意：开始时只有收点的 Vl ＝ Ve(Vn) 已知，利用逆拓扑排序的序列可得到每一个结点的 Vl 。且结点的 Vl 确定次序和逆拓扑排序的序列相同。 2 5 Vx Vl(Vj) = 取终止结点的最迟发生时间 - 各自边权值的差的最小值 3

77 7.5.2 关键路径 实例：求事件结点的最迟发生时间 正向拓扑排序： V1 V2 V3 V4 V5 V6 8 8 2 V5 V2 1 1 3
·逆向拓扑排序同每个结点的 VL 发生时间的确定次序是一致的。 证；·最末一个结点的 VL 最先确定。它确定之后，就可推出对相应的起始结点的影响，如上图的 V5 V4 V3 结点的 VL 当前值，或者可以形象地认为结点V5 V4 V3的出度相应的减少了 1。 ·第二个可以确定 VL 的结点是正向拓扑排序中的倒数第二个结点，如V5 。理由：此时它已相当于出度为零的结点。即在它之前已确定 VL 的结点，对它发生的影响已全部产生(反证：如果没有全部产生，就意味着V5 V6之间还有一个结点 如Vx还对它产生影响， 边V5 Vx存在。但这样一来，它将不会是正向拓扑排序中的倒数第二个结点。证毕。) · 其余依次类推。 1 8 8 8 V1 V3 V6 2 8 4、 3 2 6 V4 V5 V2 1 1 2 1 8 6、 4 0、 0、 V1 3 2 V3 V6 2 1 5 V4 6、 5 逆向拓扑排序： V6 V5 V4 V3 V2 V1

78 7.5.2 关键路径 实例：求事件结点的最迟发生时间 正向拓扑排序： V1 V2 V3 V4 V5 V6 8 8 2 V5 V2 1
利用逆向拓扑排序算法求事件结点的最迟发生时间的执行步骤： 1、设每个结点的最迟发生时间为收点的最早发生时间。 2、将栈中的结点V取出。 3、根据逆邻接表找到结点V的所有的起始结点，将结点V的最迟发生时间 - 活动的权值得到的差同起始结点的原最迟发生时间进行比较；如果该值小，则用该值取代原最迟发生时间。 4、反复执行 2、3；直至栈空为止。 1 3 5 2 1 8 8 8 V1 V3 V6 2 8 4、 3 2 6 V4 V5 V2 1 1 2 1 8 3 6、 4 0、 0、 V1 2 V3 V6 2 1 5 V4 6、 5 逆向拓扑排序： V6 V5 V4 V3 V2 V1

79 7.5.2 关键路径 1 3 5 6 2 1 3 4 6 5 边 最早发生时间 最迟发生时间 实例的事件结点的最早发生时间 V1 V2 1
1 3 5 6 2 1 3 4 6 5 V1 V2 1 6 2 V5 V2 V1 V3 1 1 3 5 2 1 3 8 V1 V4 关键活动 V1 V3 V6 2 V2 V3 5 V4 V2 V5 实例的事件结点的最迟发生时间 V3 V4 3 6 2 V5 V2 V3 V6 1 1 3 5 2 1 4 8 V4 V5 关键活动 V1 V3 V6 2 V4 V6 5 V5 V6 V4 关键活动

80 7.5.2 关键路径 实例的关键路径（粗箭头所示） 6 1 2 V5 V2 2 3 1 6 1 3 5 1 3 8 V1 V3 V6 2 4
3 8 V1 V3 V6 2 4 8 5 V4 5 注意：关键路径可有多条 缩短工期必须缩短关键活动所需的时间 反过来不一定成立。 时间代价：图中的结点和边都要访问到，故：O(e+n)。

81 7.6 最短路经 图或网还经常用于描述一个城市或城市间的交通运输网络，以图中顶点表示一个城市或某个交通枢纽，以边或弧表示两地之间的交通状况，边或弧上的权值可表示各种相关信息，例如两地之间的路程长度，交通费用或行程时间等等。那么对于网来说，两个顶点之间的路径长度就不再是7.1节中所定义的路径中"弧的数目"，而是路径中"弧的权值之和"。则当两个顶点之间存在多条路径时，其中必然存在一条"最短路径"，即路径中弧的权值和取最小值的那条路径，本节就是讨论如何求得这条最短路径的算法。考虑到交通图的有向性，本节将讨论带权有向图(有向网)，并称路径中的第一个顶点为"源点"，路径中的最后一个顶点为"终点"。

82 7.6.1 单源点路径问题 单源点路径问题是指，已知一个有向网和网中某个源点，求得从该源点到图中其它各个顶点之间的最短路径。
实例:加权有向图 源点 100 10 30 1 4 源点 终点 最短路径 路径长度 V0 V1 ( V0 ,V1 ） V2 （V0,V3 ,V2 ） V3 （V0,V3） V4 （V0 ,V3 ,V2 ,V4） 50 10 60 2 3 20 加权邻接矩阵： 1 2 3 4 0 10 ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ 10 ∞ ∞ ∞ ∞ ∞ ∞ 0

83 7.6.1 单源点路径问题 源点 Dijkstra 算法: Dijkstra 算法求单源最短路径：
Dijkstra 算法求单源最短路径： 设 V 是该有向图的结点的集合、集合 S 是已求得最短路径的结点的集合, 求 V0 至其余各结点的最短距离。S[i]=1,表示结点i在S中，否则不在。 1、S[0] ＝ 1 ；// 结点 V0 最短路径已求得,是源点。 2、for ( i=1; i<n; i++ ) 3、 { D[i]=c[ 0, i ]; S[i]=0; } 4、for ( i=1; i<n; i++ ) 5、{ 在 V－S 中选择一个结点VW；使得 D[w] 最小。将W 加入集合 S 6、 for (每一个在 V－S 中的结点 v ) { 7、 D[v]=MIN( D[v],D[w]+C[w,v]) }; 9、 } 100 10 30 1 4 50 10 60 2 3 20 S3 S2 S1 100 10 10 100, 100, 100 ,60 30 1 4 S4 50 10 60 50, 60, ∞ 2 30, 30, 3 20 S5

84 7.6.1 单源点路径问题 Dijkstra 算法: Dijkstra 算法求单源最短路径：
设 V 是该有向图的结点的集合、集合 S 是已求得最短路径的结点的集合, 求 V0 至其余各结点的最短距离。S[i]=1,表示结点i在S中，否则不在。 1、S[0] ＝ 1 ；// 结点 V0 最短路径已求得,是源点。 2、for ( i=1; i<n; i++ ) 3、 { D[i]=c[ 0, i ]; S[i]=0; Path[ v ] = -1; } 4、for ( i=1; i<n; i++ ) 5、{ 在 V－S 中选择一个结点VW；使得 D[w] 最小。将W 加入集合 S // 用最小化堆选 6、 for (每一个在 V－S 中的结点 V ) //出最小的 { if (D[w]+C[w,v] < D[v ]) Path[ v ] = w; 7、 D[v]=MIN( D[v],D[w]+C[w,v]) }; //如用最小化堆实现，此处还要调整堆 9、 } 源点 100 10 30 1 4 50 10 60 2 3 20 Dijkstra 算法: 路径的求法：增加Path[v] = w; Dijkstra 算法的时间复杂性: 邻接矩阵:O(n2); 考察其余n-1个结点 邻接表:O((n+e)logn)) 考察直达边即可 (用堆来实现)

85 7.6.1 单源点路径问题 Dijkstra 算法: Dijkstra 算法求单源最短路径：
设 V 是该有向图的结点的集合、集合 S 是已求得最短路径的结点的集合, 求 V0 至其余各结点的最短距离。S[i]=1,表示结点i在S中，否则不在。 1、S[0] ＝ 1 ；// 结点 V0 最短路径已求得,是源点。 2、for ( i=1; i<n; i++ ) 3、 { D[i]=c[ 0, i ]; S[i]=0; Path[ v ] = -1; } 4、for ( i=1; i<n; i++ ) 5、{ 在 V－S 中选择一个结点VW；使得 D[w] 最小。将W 加入集合 S // 用最小化堆选 6、 for (每一个在 V－S 中的结点 V ) //出最小的 { if (D[w]+C[w,v] < D[v ]) Path[ v ] = w; 7、 D[v]=MIN( D[v],D[w]+C[w,v]) }; //如用最小化堆实现，此处还要调整堆 9、 } 源点 100 10 30 1 4 50 10 60 2 3 20 6、7的解释： V V－S 老 S X V 源点 V0 W 新 S

86 7.6.1 单源点路径问题 证明：设 V0 经 S 中的j结点，到 VZ 后直接 经有向边到达结点 Vj 的路径，是所有
这些路径中最短的。如图所示，路径 p1<P2; p1<p3;p1<p4。则 p1 就是源 点 V0 至 Vj 的最短路径。 假定存在一条更短的路径，那么肯定 要经过 T - { Vj } 中的一个顶点，设 为 Vn ；但 p3 > p1，同假设矛盾，不 可能。 Dijkstra 算法: 正确性证明 设 V 是结点的集合，S 是已经得到最短 路径（由源点至本结点）的结点的集合。 T = V - S V T S Vl Vz p1 源点 Dijkstra 算法: 边的权值不可以为负值。 V0 Vm Vy V1 p2 100 -99 Vx 5 p3 V0 V2 Vn p4 Vn 注意：边的权值不可以为负值，这一点可以 从上述证明中推出。 声明：Dijkstra 算法和Prim算法本质是相同的，甚至可以用同一个函数求出，区别仅在于权值不同。

87 7.6.2 每对顶点间的最短路径 如果希望求得图中任意两个顶点之间的最短路径，显然只要依次将每个顶点设为源点，调用迪杰斯特拉算法n次便可求出，其时间复杂度为 O(n3)。弗洛伊德提出了另外一个算法，虽然其时间复杂度也是 O(n3)，但算法形式更简单。

88 7.6.2 每对顶点间的最短路径 加权有向图： 求各结点之间的最短路径 3 0 8 5 3 0 ∞ ∞ 2 0 V0 V1 8 2 5 V2
Floyd 算法的求解过程 设 C 为 n 行 n 列的代价矩阵，c[ i, j ] 为 i ---> j 的权值。如果 i=j ；那么 c[ i, j ] = 0。如果 i 和 j 之间无有向边；则 c[ i, j ] = ∞ 1、使用 n 行 n 列的矩阵 A 用于计算最短路径。 初始时， A[ i, j ] = c[ i, j ] 2、进行 n 次迭代 在进行第 k 次迭代时，我们将使用如下的公式： Ak-1[ i, j ] Ak[ i, j ] = MIN Ak-1[ i, k ] + Ak-1[ k, j ] 注意：第 k 次迭代时，针对结点 k 进行。原 Ak-1 矩阵的第 k 行，第 k 列保持不变。左上至右下的对角线元素也不 变。 1 2 ∞ ∞ V0 V1 8 2 5 V2 左图的代价矩阵 c k Ak-1[ i, k ] Ak-1[ k, j ] Ak-1[ i, j ] i j

89 7.6.2 每对顶点间的最短路径 实例及求解过程: 3 0 8 5 3 0 ∞ ∞ 2 0 V0 V1 8 2 5 V2 0 8 5
Floyd 算法的求解过程 设 C 为 n 行 n 列的代价矩阵，c[ i, j ] 为 i ---> j 的权值。如果 i=j ；那么 c[ i, j ] = 0。如果 i 和 j 之间无有向边；则 c[ i, j ] = ∞ 1、使用 n 行 n 列的矩阵 A 用于计算最短路径。 初始时， A[ i, j ] = c[ i, j ] 2、进行 n 次迭代 在进行第 k 次迭代时，我们将使用如下的公式： Ak-1[ i, j ] Ak[ i, j ] = M IN Ak-1[ i, k ] + Ak-1[ k, j ] 注意：第 k 次迭代时，针对结点 k 进行。原 Ak-1 矩阵的第 k 行，第 k 列保持不变。左上至右下的对角线元素也不 变。 3 1 2 ∞ ∞ V0 V1 8 2 5 V2 ∞ ∞ ∞ A初值 A0 请看实例: 注意：k = 0 ~ ( n-1)。如在由 A初值得到A0时， 原A初值的第0行，第0列不变，仍反应在A0中。 A1 A2

90 7.6.2 每对顶点间的最短路径 Void ShortestPath_FLOYD( MGraph G, PathMatrix &P[], DistanceMatrix &D){ for( v=0; v<G.vexnum; ++v) for( w=0; w<G.vexnum; ++w){ D[v][w] = G.arcs[v][w]; for( u=0; u<G.vexnum; ++u) P[v][w][u]=FALSE; if( D[v][w]<INFINITY){ P[v][w][v] = TRUE; P[v][w][w] = TRUE; } for( u=0; u<G.vexnum; ++u) for( w=0; w<G.vexnum; ++w) if( D[v][u]+D[u][w]<D[v][w]){ D[v][w]=D[v][u]+D[u][w]; for( i=0; i<G.vexnum; ++i) P[v][w][i] = P[v][u][i] || “P[u][w][i];