数据结构-清华大学-殷人昆-05讲解

1、第第5章章 图图 清华大学计算机系清华大学计算机系 殷人昆殷人昆 数据结构课件数据结构课件 第五章第五章 图图 138-2 图的基本概念图的基本概念 图的存储表示图的存储表示 图的遍历与连通性图的遍历与连通性 最小生成树最小生成树 最短路径最短路径 活动网络活动网络 第第5章章 图图 138-3 图的基本概念图的基本概念 n图定义图定义 r图是由顶点集合图是由顶点集合(vertex)及顶点间的关系集合及顶点间的关系集合 组成的一种数据结构：组成的一种数据结构： Graph( V, E ) r其中，其中，V = x | x 某个数据对象某个数据对象 是顶点的是顶点的 有穷非空集合；有穷非空集合；

2、E = (x, y) | x, y V 或或 E = | x, y V 顶点顶点 v 的出度的出度是以是以 v 为始点的有向边的为始点的有向边的 条数条数, 记作记作 OD(v)。 n路径路径 在图在图 G(V, E) 中中, 若从顶点若从顶点 vi 出发出发, 沿一沿一 些边经过一些顶点些边经过一些顶点 vp1, vp2, , vpm，到达顶点到达顶点vj。 则称顶点序列则称顶点序列 (vi vp1 vp2 . vpm vj) 为从顶点为从顶点vi 到顶到顶 点点 vj 的路径。它经过的边的路径。它经过的边(vi, vp1)、(vp1, vp2)、.、 (vpm, vj) 应是属于应是属于E

3、的边。的边。 138-7 n路径路径长度长度 非带权图的路径长度是指此路径上边非带权图的路径长度是指此路径上边 的条数。带权图的路径长度是指路径上各边的权的条数。带权图的路径长度是指路径上各边的权 之和。之和。 n简单路径简单路径 若路径上各顶点若路径上各顶点 v1,v2,.,vm 均不均不 互相互相 重复重复, 则称这样的路径为简单路径。则称这样的路径为简单路径。 n回路回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个顶点与最后一个顶点vm 重合，则称这样的路径为回路或环。重合，则称这样的路径为回路或环。 0 12 3 0 12 3 0 12 3 138-8 n连通图与连通分量连

4、通图与连通分量 在无向图中在无向图中, 若从顶点若从顶点v1到顶到顶 点点v2有路径有路径, 则称顶点则称顶点v1与与v2是连通的。如果图中是连通的。如果图中 任意一对顶点都是连通的任意一对顶点都是连通的, 则称此图是连通图。则称此图是连通图。 n非连通图的极大连通子图叫做连通分量。非连通图的极大连通子图叫做连通分量。 n强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中, 若对于每一若对于每一 对顶点对顶点vi和和vj, 都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径, 则称此图是强连通图。则称此图是强连通图。 n非强连通图的极大强连通子图叫做强连通分量。非

5、强连通图的极大强连通子图叫做强连通分量。 n生成树生成树 一个连通图的生成树是其极小连通子图，一个连通图的生成树是其极小连通子图， 在在 n 个顶点的情形下，有个顶点的情形下，有n-1条边。条边。 138-9 图的存储表示图的存储表示 n在图的邻接矩阵表示中，有一个记录各个顶点信在图的邻接矩阵表示中，有一个记录各个顶点信 息的息的顶点表顶点表，还有一个表示各个顶点之间关系的，还有一个表示各个顶点之间关系的 邻接矩阵邻接矩阵。 n设图设图 A = (V, E)是一个有是一个有 n 个顶点的图个顶点的图, 图的邻接图的邻接 矩阵是一个二维数组矩阵是一个二维数组 A.edgenn，定义：定义： 邻邻

6、接矩阵接矩阵 (Adjacency Matrix) 否否则则 或或若若 , , 0 ),(,1 A.Edge EjiEji ji 138-10 n无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的; n有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。 0101 1010 0101 1010 A.edge 0 12 3 0 1 2 000 101 010 A.edge 138-11 n在有向图中在有向图中, 统计统计第第 i 行行 1 的个数可得顶点的个数可得顶点 i 的的出出 度度，统计，统计第第 j 列列 1 的个数可得顶点的个数可得顶点 j 的的入度入度。 n在无向图中在无向

7、图中, 统计第统计第 i 行行 (列列) 1 的个数可得顶点的个数可得顶点i 的的度度。 n若若图中有图中有 n 个顶点，个顶点，e 条边，邻接矩阵有条边，邻接矩阵有 n2 个矩个矩 阵元素，对于无向图，其中有阵元素，对于无向图，其中有 2e 个非零元素，个非零元素， 对于有向图，只有对于有向图，只有 e 个非零元素。个非零元素。 n如果如果 e 远远小于远远小于 n2，则称该图为，则称该图为稀疏图稀疏图，其邻接，其邻接 矩阵将是稀疏矩阵；否则该图为矩阵将是稀疏矩阵；否则该图为稠密图稠密图，邻接矩，邻接矩 阵适用于稠密图。阵适用于稠密图。 n对于一个图来说，对于一个图来说，邻接矩阵表示是惟一的

8、邻接矩阵表示是惟一的。 138-12 网络的邻接矩阵网络的邻接矩阵 ji ji,ji,ji ji,ji,jiji ji 若若 或或且且若若 或或且且若若 , )(, )(),( 0 EE EEW A.edge 8 6 3 1 2 9 5 4 2 0 3 1 06 8053 290 410 A.edge 138-13 用邻接矩阵表示的图结构的定义用邻接矩阵表示的图结构的定义 #define maxValue INT_Max /在在中中 #define maxEdges 30/最大边条数最大边条数 #define maxVertices 10/最大顶点个数最大顶点个数 typedef char V

9、Type; /顶点数据类型顶点数据类型 typedef int WType; /边上权值类型边上权值类型 typedef struct /静态存储定义静态存储定义 VType verticesListmaxVertices; /顶点表顶点表 WType EdgemaxVerticesmaxVertices; /邻接矩阵邻接矩阵, 可视为边之间的关系可视为边之间的关系 int numVertices, numEdges; /当前顶点个数与边数当前顶点个数与边数 MGraph; 138-14 WType GetWeight ( MGraph else return 0; VType GetValu

10、e ( MGraph 138-15 int FirstNeighbor (MGraph col 0 /顺序检测第顺序检测第 v 行寻找第一个邻接顶点行寻找第一个邻接顶点 /对于无权图，对于无权图，maxValue应为应为INT_MAX return -1; 138-16 int NextNeighbor ( MGraph if ( v != -1 col 0 else p = p-link; return 0; 138-24 无向图邻接表的构造算法无向图邻接表的构造算法 void CreateGraph ( ALGraph cin G.numVertices G.numEdges; /输入顶点

11、个数和边数输入顶点个数和边数 for ( i = 0; i G.VerticesListi.data; /输入顶点信息输入顶点信息 G.VerticesListi.first = NULL; /边链指针置空边链指针置空 for ( i = 0; i tail head weight; EdgeNode * p = new EdgeNode; /创建边结点创建边结点 138-25 p-dest = head; p-cost = weight; /链入第链入第 tail 号链表的前端号链表的前端 p-link = G.VerticesListtail.first; G.VerticesListta

12、il.first = p; p = new EdgeNode; p-dest = tail; p-cost = weight; /链入第链入第 head 号链表的前端号链表的前端 p-link = G.VerticesListhead.first; G.VerticesListhead.first = p; 138-26 VType GetValue ( ALGraph return -1; /若顶点不存在若顶点不存在 138-27 int NextNeighbor ( ALGraph while ( p != NULL ) if ( p-dest = w /返回下一个邻接顶点在邻接表中位置返

13、回下一个邻接顶点在邻接表中位置 else p = p-link; return -1; /没有查到下一个邻接顶点没有查到下一个邻接顶点 138-28 邻接多重表邻接多重表 (Adjacency Multilist) n在解决以边的处理为主的问题中，无论是邻接矩在解决以边的处理为主的问题中，无论是邻接矩 阵或邻接表，都有重复处理的麻烦。改进的办法阵或邻接表，都有重复处理的麻烦。改进的办法 就是使用邻接多重表，每一条边仅被表示一次。就是使用邻接多重表，每一条边仅被表示一次。 n无向图的情形无向图的情形 r边结点的结构边结点的结构 r其中其中, mark 是处理标记是处理标记; vertex1和和v

14、ertex2是该是该 边两顶点位置。边两顶点位置。Path1 指向下一条依附指向下一条依附 vertex1 的边；的边；path2 指向下一条依附指向下一条依附 vertex2 的边。的边。 mark vertex1 vertex2 path1 path2 138-29 r对于带权图还需设置一个存放与该边相关的权对于带权图还需设置一个存放与该边相关的权 值的域值的域 cost。 r顶点结点的结构顶点结点的结构 r存储顶点信息的结点表以顺序表方式组织，每存储顶点信息的结点表以顺序表方式组织，每 一个顶点结点有两个数据成员：其中，一个顶点结点有两个数据成员：其中，data 存存 放与该顶点相关的信

15、息，放与该顶点相关的信息，Firstout 是指示第一是指示第一 条依附该顶点的边的指针。条依附该顶点的边的指针。 r在邻接多重表中在邻接多重表中, 所有依附同一个顶点的边都所有依附同一个顶点的边都 链接在同一个单链表中。链接在同一个单链表中。 data Firstout 138-30 mark vtx1 vtx2 path1 path2 0 1 0 2 1 3 e1 e2 e3 data Fout A B C D 0 1 2 3 e1 e2 e3 A B C D r从顶点从顶点 i 出发出发, 可以循链找到所有依附于该顶点可以循链找到所有依附于该顶点 的边，也可以找到它的所有邻接顶点。的边，

16、也可以找到它的所有邻接顶点。 邻接多重表结构图示邻接多重表结构图示 138-31 n有向图的情形有向图的情形 r在用邻接表表示有向图时在用邻接表表示有向图时, 有时需要同时使用有时需要同时使用 邻接表和逆邻接表。用有向图的邻接多重表邻接表和逆邻接表。用有向图的邻接多重表 （十字链表）可把两个表结合起来表示。（十字链表）可把两个表结合起来表示。 r边结点的结构边结点的结构 r其中，其中，mark 是处理标记；是处理标记；vertex1 和和 vertex2 指明该有向边始顶点和终顶点的位置。指明该有向边始顶点和终顶点的位置。Path1 指向同一顶点发出的下一条边的边结点；指向同一顶点发出的下一条

17、边的边结点； path2 指向进入同一顶点的下一条边的边结点。指向进入同一顶点的下一条边的边结点。 r需要时还可有权值域需要时还可有权值域 cost。 mark vertex1 vertex2 path1 path2 138-32 r顶点结点的结构顶点结点的结构 r每个顶点有一个结点，它相当于出边表和入边每个顶点有一个结点，它相当于出边表和入边 表的头结点：其中，数据成员表的头结点：其中，数据成员 data 存放与该顶存放与该顶 点相关的信息，指针点相关的信息，指针 Firstout 指示以该顶点为指示以该顶点为 始顶点的出边表的第一条边，始顶点的出边表的第一条边，Firstin 指示以该指示

18、以该 顶点为终顶点的入边表的第一条边。顶点为终顶点的入边表的第一条边。 data Firstin Firstout 138-33 mark vtx1 vtx2 path1 path2 0 1 0 3 1 2 2 3 3 4 4 0 e1 e2 e3 e4 e5 e6 data Fin Fout A B C D E 0 1 2 3 4 e1 e2 e3 e4 e5 e6 A BC D E 邻接多重表结构的图示邻接多重表结构的图示 138-34 图的遍历与连通性图的遍历与连通性 n从已给的连通图中某一顶点出发，沿着一从已给的连通图中某一顶点出发，沿着一 些边访些边访 遍图中所有的顶点，且使每个顶点

19、仅被访问一次，遍图中所有的顶点，且使每个顶点仅被访问一次， 就叫做图的遍历就叫做图的遍历 ( Graph Traversal )。 n北京大学版本的教材称遍历为北京大学版本的教材称遍历为“周游周游”。 n图中可能存在回路，且图的任一顶点都可能与其图中可能存在回路，且图的任一顶点都可能与其 它顶点相通，在访问完某个顶点之后可能会沿着它顶点相通，在访问完某个顶点之后可能会沿着 某些边又回到了曾经访问过的顶点。某些边又回到了曾经访问过的顶点。 n为了避免重复访问，可设置一个标志顶点是否被为了避免重复访问，可设置一个标志顶点是否被 访问过的辅助数组访问过的辅助数组 visited 。 138-35 n

20、辅助数组辅助数组 visited 的初始状态为的初始状态为 0, 在图的遍历在图的遍历 过程中过程中, 一旦某一个顶点一旦某一个顶点 i 被访问被访问, 就让就让 visited i 为为 1，防止它被多次访问。，防止它被多次访问。 n图的遍历的分类图的遍历的分类: r深度优先搜索深度优先搜索 DFS (Depth First Search) r广度优先搜索广度优先搜索 BFS (Breadth First Search) 138-36 深度优先搜索深度优先搜索DFS ( Depth First Search ) n深度优先搜索的示例深度优先搜索的示例 A C DEG B F H 1 2 3

21、4 5 7 6 8 前进前进回退回退 深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树 A C DEG B F H 1 2 3 4 5 7 6 8 138-37 n深度优先搜索算法在访问图中某一起始顶点深度优先搜索算法在访问图中某一起始顶点 v 后后, 由由 v 出发出发, 访问它的任一邻接顶点访问它的任一邻接顶点 w1; 再从再从 w1 出发出发, 访问与访问与 w1邻邻 接但还没有访问过的顶点接但还没有访问过的顶点 w2; 然后再然后再 从从 w2 出发出发, 进行类似的访问进行类似的访问, 如此进行下去如此进行下去, 直直 至所有的邻接顶点都被访问过的顶点至所有的邻接顶点都

22、被访问过的顶点 u 为止。为止。 n接着接着, 退回一步退回一步, 退到前一次刚访问过的顶点退到前一次刚访问过的顶点, 看看 是否还有其它没有被访问的邻接顶点。如果有是否还有其它没有被访问的邻接顶点。如果有, 则则 访问此顶点访问此顶点, 之后再从此顶点出发之后再从此顶点出发, 进行与前述类进行与前述类 似的访问似的访问; 如果没有如果没有, 就再退回一步进行搜索。就再退回一步进行搜索。 n重复上述过程重复上述过程, 直到连通图中所有顶点都被访问过直到连通图中所有顶点都被访问过 为止。为止。 深度优先搜索的基本思路深度优先搜索的基本思路 138-38 图的深度优先搜索算法图的深度优先搜索算法

23、void Graph_Traverse ( ALGraph for ( int i = 0; i G.numVertices; i+ ) visited i = 0; /访问数组访问数组 visited 初始化初始化 for ( int i = 0; i G.numVertices; i+ ) if ( ! visitedi ) DFS (G, i, visited ); /从顶点从顶点 i 出发开始搜索出发开始搜索 delete visited; /释放释放 visited n每调用一次每调用一次 DFS 就遍历了图的一个连通分量。就遍历了图的一个连通分量。 138-39 void DFS

24、(ALGraph /访问顶点访问顶点 v visitedv = 1; /顶点顶点 v 作访问标记作访问标记 int w = FirstNeighbor (G, v); /取取 v 的第一个邻接顶点的第一个邻接顶点 w while ( w != -1 ) /若邻接顶点若邻接顶点 w 存在存在 if ( !visitedw ) DFS (G, w, visited ); /若若顶点顶点 w 未访问过未访问过, 递归访问顶点递归访问顶点 w w = NextNeighbor (G, v, w ); /取顶点取顶点 v 排在排在 w 后的下一个邻接顶点后的下一个邻接顶点 138-40 广度优先搜索广度

25、优先搜索BFS ( Breadth First Search ) n广度优先搜索的示例广度优先搜索的示例 广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树 A C DEG B F H 1 2 3 45 67 8 A C DEG B F H 138-41 nBFS在访问了在访问了起始顶点起始顶点 v 之后之后, 由由 v 出发，依次访出发，依次访 问问 v 的各个的各个未被访问过的邻接顶点未被访问过的邻接顶点 w1, w2, , wt, 然后再顺序访问然后再顺序访问 w1, w2, , wt 的所有还未被访问的所有还未被访问 过的邻接顶点。再从这些访问过的顶点出发，再过的邻接顶点。

26、再从这些访问过的顶点出发，再 访问它们的所有还未被访问过的邻接顶点访问它们的所有还未被访问过的邻接顶点, 如如 此做下去，直到图中所有顶点都被访问到为止。此做下去，直到图中所有顶点都被访问到为止。 n深度优先搜索是一种回溯的算法，而广度优先搜深度优先搜索是一种回溯的算法，而广度优先搜 索不是，它是一种分层的顺序搜索过程，每向前索不是，它是一种分层的顺序搜索过程，每向前 走一步可能访问一批顶点。因此，广度优先搜索走一步可能访问一批顶点。因此，广度优先搜索 不是一个递归的过程。不是一个递归的过程。 广度优先搜索的基本思路广度优先搜索的基本思路 138-42 n为了实现逐层访问，广度优先搜索算法使用

27、了一为了实现逐层访问，广度优先搜索算法使用了一 个队列，以记忆正在访问的这一层和下一层的顶个队列，以记忆正在访问的这一层和下一层的顶 点，以便于向下一层访问。点，以便于向下一层访问。 n为避免重复访问为避免重复访问, 需要一个辅助数组需要一个辅助数组 visited ， 给被访问过的顶点加标记。给被访问过的顶点加标记。 n为了实现和控制广度优先搜索算法的执行，在图为了实现和控制广度优先搜索算法的执行，在图 的遍历得主程序的遍历得主程序 void Graph_Traverse (ALGraph /访问顶点访问顶点v visitedv = 1; /作访问标记作访问标记 Queue Qu; Init

28、Queue(Qu); /定义队列定义队列 EnQueue (Qu, v); /顶点顶点v 进队列进队列 while (! QueueEmpty (Qu) /队空搜索结束队空搜索结束 DeQueue (Qu, v); int w = FirstNeighbor (G, v); /取顶点取顶点v 的第一个邻接顶点的第一个邻接顶点w 138-44 while ( w != -1 ) /若邻接顶点若邻接顶点 w 存在存在 if ( !visitedw ) /未访问过未访问过 cout GetValue (w) ; visitedw = 1; EnQueue (Qu, w); w = NextNeigh

29、bor (G, v, w); /重复检测重复检测 v 的所有邻接顶点的所有邻接顶点 /外层循环，判队列空否外层循环，判队列空否 138-45 连通分量连通分量 (Connected component) n当无向图为非连通图时，从图中某一顶点出发，当无向图为非连通图时，从图中某一顶点出发， 利用深度优先搜索算法或广度优先搜索算法不可利用深度优先搜索算法或广度优先搜索算法不可 能遍历到图中的所有顶点，只能访问到该顶点所能遍历到图中的所有顶点，只能访问到该顶点所 在的最大连通子图在的最大连通子图（连通分量）（连通分量）的所有顶点。的所有顶点。 n若从无向图的每一个连通分量中的一个顶点出发若从无向图

30、的每一个连通分量中的一个顶点出发 进行遍历，可求得无向图的所有连通分量。进行遍历，可求得无向图的所有连通分量。 n求连通分量的算法求连通分量的算法需要对图的每一个顶点进行检需要对图的每一个顶点进行检 测：若已被访问过，则该顶点一定是落在图中已测：若已被访问过，则该顶点一定是落在图中已 求得的连通分量上；若还未被访问，则从该顶点求得的连通分量上；若还未被访问，则从该顶点 出发遍历图，可求得图的另一个连通分量。出发遍历图，可求得图的另一个连通分量。 138-46 n对于非连通的无向图，所有连通分量的生成树组对于非连通的无向图，所有连通分量的生成树组 成了非连通图的生成森林。成了非连通图的生成森林。

31、 I H JO NML K 非连通非连通 无向图无向图 A CDEB FG A CDEB FG H I J K O N ML 非连通图的非连通图的 连通分量连通分量 138-47 n从不同顶点出发，通过强连通有向图的遍历，可从不同顶点出发，通过强连通有向图的遍历，可 以得到不同的生成树。以得到不同的生成树。 强连通有向图强连通有向图 深度优先生成树深度优先生成树 A C D EB F A C D EB F 1 2 3 4 5 6 A C D EB F 1 2 3 4 5 6 A C D EB F 1 2 3 4 5 6 138-48 n有向图的遍历一般得到的是生成森林。有向图的遍历一般得到的是

32、生成森林。 非强连通有向图非强连通有向图 深度优先生成森林深度优先生成森林 1 2 3 5 4 A C D EB A C D EB 138-49 最小生成树最小生成树 ( minimum cost spanning tree ) n使用不同的遍历方法，可得到不同的生成树；从使用不同的遍历方法，可得到不同的生成树；从 不同的顶点出发，也可能得到不同的生成树。不同的顶点出发，也可能得到不同的生成树。 n按照生成树的定义，按照生成树的定义，n 个顶点的连通带权图的生个顶点的连通带权图的生 成树有成树有 n 个顶点、个顶点、n-1 条边。条边。 n构造最小生成树的准则构造最小生成树的准则 r必须使用且

33、仅使用该带权图中的必须使用且仅使用该带权图中的n-1 条边来联条边来联 结网络中的结网络中的 n 个顶点；个顶点； r不能使用产生回路的边；不能使用产生回路的边； r各边上的权值的总和达到最小。各边上的权值的总和达到最小。 138-50 克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法 n克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想： r设有一个有设有一个有n个顶点的连通带权图个顶点的连通带权图N = V, E , 先构造一个只有先构造一个只有n个顶点个顶点, 没有边的非连通图没有边的非连通图 T = V, , 图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。 r当在当在

34、E 中选到一条具有最小权值的边时，中选到一条具有最小权值的边时，若该若该 边的两个顶点落在不同的连通分量上，则将此边的两个顶点落在不同的连通分量上，则将此 边加入到边加入到 T 中中；否则将此边舍去，重新选择一；否则将此边舍去，重新选择一 条权值最小的边。条权值最小的边。 r如此重复下去，直到所有顶点在同一个连通分如此重复下去，直到所有顶点在同一个连通分 量上为止。量上为止。 138-51 n首先首先, 将将 E 中所有的边按权值存放在小根堆中，每中所有的边按权值存放在小根堆中，每 次选择权值最小的边出堆次选择权值最小的边出堆, 每个边结点的格式为每个边结点的格式为 n在构造最小生成树过程中，

35、利用并查集的运算检在构造最小生成树过程中，利用并查集的运算检 查依附一条边的两顶点查依附一条边的两顶点tail、head 是否在同一连是否在同一连 通分量（即并查集的同一个子集合）上，是则舍通分量（即并查集的同一个子集合）上，是则舍 去这条边；否则将此边加入去这条边；否则将此边加入 T，同时将这两个顶，同时将这两个顶 点放在同一个连通分量上。点放在同一个连通分量上。 边的两个顶点位置边的两个顶点位置 边的权值边的权值 tail head cost 算法的设计思路算法的设计思路 138-52 n随着各边逐步加入到最小生成树的边集合中随着各边逐步加入到最小生成树的边集合中, 各各 连通分量也在逐步

36、合并连通分量也在逐步合并, 直到形成一个连通分量直到形成一个连通分量 为止。为止。 原图原图 (a) (b) 10 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 25 0 4 6 1 3 2 应用应用Kruskal算法构造最小生成树的过程算法构造最小生成树的过程 138-53 10 12 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 25 0 4 6 1 3 2 10 14 12 原图原图 (c) (d) (e) (f) (g) 5 0 4 6 1 3 2 10 1416 1

37、2 5 0 4 6 1 3 2 10 14 22 16 12 5 0 4 6 1 2 10 25 14 22 16 12 3 138-54 最小生成树的结构定义最小生成树的结构定义 n为使用小根堆存放图的各条边，需定义既适用于为使用小根堆存放图的各条边，需定义既适用于 小根堆又适用于最小生成树的边结点。小根堆又适用于最小生成树的边结点。 const int maxValue = 问题中不可能出现的大数问题中不可能出现的大数 typedef struct MSTEdgeNode /边结点边结点 int tail, head; /生成树各边的两顶点生成树各边的两顶点 float cost; /生成

38、树各边的权值生成树各边的权值 n同时还要修改小根堆（第同时还要修改小根堆（第3章）的定义，把章）的定义，把 key 改改 为为cost，把，把 HElemType 改为改为 MSTEdgeNode。 138-55 利用克鲁斯卡尔算法建立最小生成树利用克鲁斯卡尔算法建立最小生成树 void Kruskal (ALGraph InitHeap(H); /小根堆小根堆 UFSets F; InitUFSets(F); /并查集并查集 int u, v, count; MSTEdgeNode e; /辅助单元辅助单元 for ( u = 0; u G.numVertices; u+ ) v = Fir

39、stNeighbor (G, u); /取取u第一个邻接顶点第一个邻接顶点 while ( v != -1 ) /插入小根堆插入小根堆 e.tail = u; e.head = v; e.cost = GetWeight (G, u, v); Insert (H, e); v = NextNeighbor (G, u, v); /取取u下一个邻接顶点下一个邻接顶点 138-56 count = 1; /最小生成树加入边数计数最小生成树加入边数计数 while ( count G.numVertices ) Remove ( H, e ); /从堆中退出一条边从堆中退出一条边 u = Find

40、( F, e.tail ); v = Find ( F, e.head ); if ( u != v ) /两端点不在同一连通分量两端点不在同一连通分量 Merge(F, u, v); /合并两端点所在连通分量合并两端点所在连通分量 cout e.tail e.head e.cost endl; count+; 138-57 n初始堆初始堆 并查集并查集 1. 边边 (0,5,10) 出堆，两端点出堆，两端点0, 5不在同一连通分量不在同一连通分量 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 0241814 02510 2425022 1822012 12

41、016 1416028 10280 16 24142218 2825 12 10 -1 0 -1 1 -1 2 -1 3 -1 4 -1 5 -1 6 138-58 调整后的小根堆调整后的小根堆 合并后的并查集合并后的并查集 2. 边边 (2,3,12) 出堆，两端点出堆，两端点2, 3不不 在同一连通分量在同一连通分量 16 24252218 28 14 12 -1 1 -1 2 -1 3 -1 4 -1 6 -2 0 0 5 16 28252218 24 14 -1 1 -1 4 -1 6 -2 0 0 5 -2 2 2 3 5 0 4 6 1 3 2 28 10 25 14 24 22

42、16 18 12 138-59 3. 边边 (1,6,14) 出堆，两端点出堆，两端点1, 6不在同一连通分量不在同一连通分量 调整后的小根堆调整后的小根堆 合并后的并查集合并后的并查集 4. 边边 (1,2,16) 出堆，两端点出堆，两端点1, 2不不 在同一连通分量在同一连通分量 18 282522 24 16 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 -1 4 -2 0 0 5 -2 2 2 3 -2 1 1 6 22 2825 24 18 -1 4 -2 0 0 5 1 2 2 3 1 -4 1 6 138-60 5. 边边 (6,3,18) 出

43、堆，两端点出堆，两端点6, 3在同一连通分量，舍在同一连通分量，舍 弃。弃。 6. 边边 (4,3,22) 出堆，两端点出堆，两端点4, 3不不 在同一连通分量在同一连通分量 18 5 0 4 6 1 3 2 28 10 25 14 24 22 16 12 25 28 24 22-1 4 -2 0 0 5 1 2 2 3 1 -4 1 6 1 4 -2 0 0 5 1 2 2 3 1 -5 1 6 2528 24 138-61 7. 边边 (6,4,24) 出堆，两端点出堆，两端点6, 4在在同一连通分量，舍同一连通分量，舍 弃。弃。 8. 边边 (5,4,25) 出堆，两端点出堆，两端点5,

44、 4不不 在同一连通分量在同一连通分量 n完成（并查集完成（并查集 合并为一棵树）合并为一棵树） 18 5 0 4 6 1 3 2 28 10 25 14 24 22 16 12 28 25 1 4 -2 0 0 5 1 2 2 3 1 -5 1 6 28 1 4 1 0 0 5 1 2 2 3 1 -5 1 6 138-62 普里姆（普里姆（Prim）算法）算法 n普里姆算法的基本思想：普里姆算法的基本思想： r从连通从连通带权图带权图N = V, E 中的某一顶点中的某一顶点 u0 出发，出发， 选择与它关联的具有最小权值的边选择与它关联的具有最小权值的边 ( u0, v )， 将其顶点加

45、入到将其顶点加入到生成树顶点集合生成树顶点集合U中。中。 r以后每一步从一个顶点在以后每一步从一个顶点在U中，而另一个顶点中，而另一个顶点 不在不在U中的各条边中选择权值最小的边中的各条边中选择权值最小的边(u, v), 把它的顶点加入到把它的顶点加入到集合集合U 中。如此继续下去中。如此继续下去, 直到直到带权图带权图中的所有顶点都加入到生成树顶点中的所有顶点都加入到生成树顶点 集合集合 U中为止。中为止。 n采用邻接矩阵作为采用邻接矩阵作为带权图带权图的存储表示。的存储表示。 138-63 例子：设从顶点例子：设从顶点 0 出发构造最小生成树出发构造最小生成树 5 0 4 6 1 3 2

46、28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 1. 与顶点与顶点 0 关联的候选边有两条，权值小的边是关联的候选边有两条，权值小的边是 (0, 5), 10，选取它及顶点，选取它及顶点 5 加入最小生成树。加入最小生成树。 2. 与顶点与顶点 0、5 关联的候选边有两条，权值小的是关联的候选边有两条，权值小的是 (5, 4), 25，选取它及顶点，选取它及顶点 4 加入最小生成树。加入最小生成树。 138-64 5 0 4

47、6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 3. 与顶点与顶点 0、5、4 关联的候选边有三条，权值小的关联的候选边有三条，权值小的 是是 (4, 3), 22，选取它及顶点，选取它及顶点 3 加入最小生成树。加入最小生成树。 4. 与顶点与顶点 0、5、4、3 关联的候选边有四条，权值关联的候选边有四条，权值 小的是小的是 (3, 2), 12，选取它及顶点，选取它及顶点 2 加入最小生成加入最小生成 树。树。 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18

48、 12 138-65 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5. 与顶点与顶点 0、5、4 、3、2 关联的边有四条，权值关联的边有四条，权值 小的小的 (2, 1), 16，选取它及顶点，选取它及顶点 1 加入生成树。加入生成树。 6. 与顶点与顶点 0、5、4、3、2、1 关联的候选边有四条，关联的候选边有四条， 权值小的是权值小的是 (1, 6), 14，选取它及顶点，选取它及顶点 6 加入最小加入最小 生成树。生成树。 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 2 28 10 2

49、5 14 24 22 16 18 12 138-66 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 n所有顶点所有顶点 0、5、4 、3、2、1 均已加入最小生成均已加入最小生成 树，算法完成，树，算法完成，7 个顶点选取了个顶点选取了 6 次。次。 n每次为了在候选边中选取权值最小的边，算法使每次为了在候选边中选取权值最小的边，算法使 用了一个小根堆，把当前的候选边放在堆内，每用了一个小根堆，把当前的候选边放在堆内，每 次从堆中退出的一定是候选边权值最小的。次从堆中退出的一定是候选边权值最小的。 5 0 4 6 1 3 2 10 25 14 24 22 1

50、6 12 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 138-67 void Prim ( MGraph /边结点辅助单元边结点辅助单元 int i, u, v, count; minHeap H; InitHeap(G.numEdges); /小根堆小根堆 int Vmst = new intG.numVertices; /最小生成树顶点集合最小生成树顶点集合 for ( i = 0; i G.numVertices; i+) Vmsti = 0; Vmstu0 = 1; /起始顶点起始顶点u0 加入生成树加入生成树 count = 1; u = u0;

51、 do /逐一寻找生成树的顶点逐一寻找生成树的顶点 用用Prim算法求最小生成树算法求最小生成树 138-68 v = FirstNeighbor(G, u); /检查检查 u 的邻接顶点的邻接顶点 while ( v != -1 ) /若邻接顶点若邻接顶点 v 存在存在 if ( !Vmstv ) /且且 v 不在不在 MST 中中 ed.tail = u; ed.head = v; ed.cost = GetWeight (G, u, v); Insert(H, ed); /(u, v) 加入小根堆加入小根堆 v = NextNeighbor(G, u, v); while ( !H.Is

52、Empty() /选堆中具最小权的边选堆中具最小权的边 if ( !Vmsted.head ) /若边另一顶点在若边另一顶点在Vmst中会出现回路中会出现回路 cout ed.tail ed.head ed.cost; /输出最小生成树的一条边输出最小生成树的一条边 u = ed.head; Vmstu = 1; / u 加入生成树顶点集合加入生成树顶点集合 count+; break; /while寻找不构成回路的边处理寻找不构成回路的边处理 while ( count G.numVertices ); 138-70 nKruskal 算法通过选边来构造最小生成树，算法通过选边来构造最小生成

53、树，Prim 算法通过选顶点来构造最小生成树。算法通过选顶点来构造最小生成树。 nPrim算法仅适用于边稠密的带权图，算法仅适用于边稠密的带权图， Kruskal算算 法对于边稀疏和边稠密的带权图都适用法对于边稀疏和边稠密的带权图都适用 。 n设连通带权图有设连通带权图有 n 个顶点个顶点, 且采用邻接矩阵存储，且采用邻接矩阵存储， 则两个算法在建立小根堆都需检测矩阵，耗时则两个算法在建立小根堆都需检测矩阵，耗时 O(n2)；若图中有；若图中有 e 条边，堆的插入和删除都需耗条边，堆的插入和删除都需耗 时时O(log2e)，Kruskal算法需插入和退出算法需插入和退出 e 次，需次，需 耗时

54、耗时O(e log2e)；Prim 算法需算法需 O(n) 次迭代，每次次迭代，每次 将平均将平均 2e/n 条边插入堆中，总共条边插入堆中，总共 e 条边出堆，耗条边出堆，耗 时也是时也是O(e log2e)。 138-71 n若采用邻接表存储图，则两个算法在建立小根堆若采用邻接表存储图，则两个算法在建立小根堆 都需检测矩阵，耗时都需检测矩阵，耗时O(n+e)，其他堆操作时间耗，其他堆操作时间耗 时时O(e log2e)。 n当带权图各边的权值不相同时，产生的最小生成当带权图各边的权值不相同时，产生的最小生成 树一定是唯一的。树一定是唯一的。 n当带权图各边的权值有部分相同时，如果基于邻当带

55、权图各边的权值有部分相同时，如果基于邻 接矩阵，由于选边的顺序惟一，产生的最小生成接矩阵，由于选边的顺序惟一，产生的最小生成 树也是惟一的；如果基于邻接表，由于边链表可树也是惟一的；如果基于邻接表，由于边链表可 以不惟一，选边的顺序也可能不惟一。以不惟一，选边的顺序也可能不惟一。 138-72 其他：破圈法其他：破圈法 n对一个有对一个有 n 个顶点的连通带权图，按其权值从大个顶点的连通带权图，按其权值从大 到小顺序逐个删除各边，直到剩下到小顺序逐个删除各边，直到剩下n-1 条边为止。条边为止。 删除的原则是：要确保删除该边后各个顶点之间删除的原则是：要确保删除该边后各个顶点之间 还是连通的。

56、还是连通的。 n为了判断图的连通性，一种方案是每删除一条权为了判断图的连通性，一种方案是每删除一条权 值最大的边，就调用值最大的边，就调用DFS遍历图，如果能够访遍遍历图，如果能够访遍 图中所有顶点则表明删除此边没有破坏图的连通图中所有顶点则表明删除此边没有破坏图的连通 性，此边可删，否则撤销删除，恢复此边。性，此边可删，否则撤销删除，恢复此边。 n若采用邻接矩阵存储图，若采用邻接矩阵存储图，DFS的的时间代价时间代价O(n2)， 若采用邻接表，若采用邻接表，DFS的时间代价的时间代价O(n+e)。 138-73 18 5 0 4 6 1 3 2 28 10 25 14 24 22 16 12

57、 18 5 0 4 6 1 3 2 10 25 14 24 22 16 12 18 5 0 4 6 1 3 2 10 25 14 24 22 16 12 18 5 0 4 6 1 3 2 10 25 14 22 16 12 18 5 0 4 6 1 3 2 10 25 14 22 16 12 5 0 4 6 1 3 2 10 25 14 22 16 12 原图 删除 (0, 1) 保留 (5, 4) 删除 (6, 4) 保留 (4, 3) 删除 (6, 3) 138-74 其他：迪杰斯特拉其他：迪杰斯特拉(Dijkstra)算法算法 n最初将最初将带权图带权图中每个顶点视为一个独立的连通分中每

58、个顶点视为一个独立的连通分 量，然后逐个检查各条边：量，然后逐个检查各条边： r如果该边的两个端点在不同的连通分量上，直如果该边的两个端点在不同的连通分量上，直 接把它加入生成树；接把它加入生成树； r如果该边的两个端点在同一个连通分量上，加如果该边的两个端点在同一个连通分量上，加 入它后会形成一个环，把该环上权值最大的边入它后会形成一个环，把该环上权值最大的边 删除。删除。 n重复以上操作，直到所有边都检查完为止。重复以上操作，直到所有边都检查完为止。 n在此算法中，在此算法中，边的检查顺序没有限制，只要出现边的检查顺序没有限制，只要出现 圈就破圈。圈就破圈。为此又用到了为此又用到了并查集并

59、查集。 138-75 18 5 0 4 6 1 3 2 28 10 25 14 24 22 16 12 5 0 4 6 1 3 2 5 0 4 6 1 3 2 10 25 14 22 16 12 原图原图 各顶点自成连通分量各顶点自成连通分量 加入加入 (0,5)(5,4)(0,1) 加入加入(6,4)后后,删删(0,1) 加入加入(4,3)后后,删删(6,4) 加入加入(6,3)后后,删删(6,3) 5 0 4 6 1 3 2 10 25 28 16 14 12 5 0 4 6 1 3 2 10 25 1416 12 28 24 5 0 4 6 1 3 2 10 25 14 22 16 12

60、 24 18 138-76 最短路径最短路径 (Shortest Path) n最短路径问题：如果从图中某一最短路径问题：如果从图中某一顶点顶点(称为源点称为源点) 到达另一顶点到达另一顶点(称为终点称为终点)的路径可能不止一条，的路径可能不止一条， 如何找到一条路径使得沿此路径上各边上的权值如何找到一条路径使得沿此路径上各边上的权值 总和达到最小。总和达到最小。 n问题解法问题解法 r 边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题 Dijkstra算法算法 r 所有顶点之间的最短路径所有顶点之间的最短路径 Floyd算法算法 138-77 边上权值非负情形的单源最短路