1、生成树生成树生成树生成树：极小连通子图。包含图的所有：极小连通子图。包含图的所有 n 个结点，但只含图的个结点，但只含图的 n-1 条边。在生成树中添条边。在生成树中添 加一条边之后，必定会形成回路或环。加一条边之后，必定会形成回路或环。ABCDEHMABCDEHM无向图无向图G 无向图无向图G的生成树的生成树 图的其它术语图的其它术语完全图完全图：有：有 n(n-1)/2 条边的无向图。其中条边的无向图。其中 n 是结点个数。是结点个数。有向完全图有向完全图：有：有 n(n-1)条边的有向图。其中条边的有向图。其中 n 是结点个数。是结点个数。边的权值边的权值，边有权的图称之为，边有权的图称
2、之为网络网络。邻接点邻接点：无向图结点的无向图结点的度度(注意：同树中的结点的度定义是不同的注意：同树中的结点的度定义是不同的)有向图结点的有向图结点的出度出度和和入度入度ABCDEHM无向图无向图G1 有向图有向图G2ABCD2n22n图的图的ADTData:顶点和边的集合。边是连接一对顶点(v,u)或 的，其中(v,u)是连接顶点v和u的无向 边，而.是连接顶点 v 到 u 的有向边。边可以有一权值，或称为从一个顶点到 另一个顶点的代价。Operations:Constructor 前提：无。结果：创建一个包含顶点和边的集合的图。Getweight 前提：顶点 Vi 和 Vj 组成的顶点对
3、的数据值，该顶点对必须属于该图。结果：如果顶点 Vi 和 Vj 之间的边如果存在，则返回其权值。GetNeighbor 前提：顶点 V。结果：返回和顶点相邻接的所有的顶点。InsertVertex 前提：一个新的顶点。结果：将该新顶点插入到图的顶点集合。InsertEdge 前提：一条边的顶点 V 和 U 及其它们的权值，且顶点 V 和 U已在图中 ，而顶点 V 到 U 的边不在图中。结果：将该条边插入到图中，图的边的集合的规模增大1。RemoveVertex 前提：顶点 V 的数据值，并且它必须存在于图的顶点集之中。结果：将该顶点删除，并且删除从顶点 V 出发的，和进入顶点 V 的所 有的边
4、。图的边的集合和顶点的集合规模被更新。RemoveEdge 前提：一条边的顶点 V 和 U 及其它们的权值，且相应的权值必须存在 于顶点的值的集合之中。结果：如果该条边存在，则将它从图中删除，图的边的少1。图的存储表示图的存储表示图的四种常用的存储形式：图的四种常用的存储形式：邻接矩阵和加权邻接矩阵（邻接矩阵和加权邻接矩阵（labeled adjacency matrix）邻接表邻接表十字链表十字链表邻接多重表邻接多重表邻接矩阵邻接矩阵ABCD无权值的无权值的有向图的邻接矩阵有向图的邻接矩阵 设有向图具有设有向图具有 n 个结点，则用个结点，则用 n 行行 n 列的布尔矩阵列的布尔矩阵 A 表
5、示该有向图；表示该有向图；并且并且 Ai,j =1,如果如果i 至至 j 有一条有向边；有一条有向边；Ai,j=0如果如果 i 至至 j 没有一条有向边没有一条有向边 注意：注意：Ai,i =0。出度。出度:i行之和。入度行之和。入度:j列之和。列之和。表示成右图矩阵表示成右图矩阵0 1 1 00 0 0 00 0 0 11 0 0 0在物理实现时的考虑在物理实现时的考虑：分别用：分别用 0、1、2、3 分别标识结点分别标识结点A、B、C、D。而将真。而将真正的数据场之值放入一个一维数组之中。正的数据场之值放入一个一维数组之中。0 1 2 30123DABC 0 1 2 3邻接矩阵邻接矩阵无权
6、值的无权值的无向图的邻接矩阵无向图的邻接矩阵 设无向图具有设无向图具有 n 个结点，则用个结点，则用 n 行行 n 列的布尔矩阵列的布尔矩阵 A 表示该无向图；表示该无向图；并且并且 Ai,j =1,如果如果i 至至 j 有一条无向边；有一条无向边；Ai,j=0如果如果 i 至至 j 没有一条无向边没有一条无向边 注意：注意：Ai,i =0。i结点的度结点的度:i行或行或i列之和。列之和。上三角矩阵上三角矩阵或或下三角矩阵下三角矩阵。表示成右图矩阵表示成右图矩阵0 1 1 0 01 0 0 1 11 0 0 0 10 1 0 0 10 1 1 1 0ABCDE在物理实现时的考虑，和前一页的无向
7、图类似。在物理实现时的考虑，和前一页的无向图类似。加权邻接矩阵加权邻接矩阵有向图的加权邻接矩阵有向图的加权邻接矩阵 设有向图具有设有向图具有 n 个结点，则用个结点，则用 n 行行 n 列的矩阵列的矩阵 A 表示该有向图；表示该有向图；并且并且 Ai,j =a,如果如果i 至至 j 有一条有向边且它的权值为有一条有向边且它的权值为a。Ai,j=空空 或其它标或其它标 志；如果志；如果 i 至至 j 没有一条有向边。没有一条有向边。ABCD表示成右图矩阵表示成右图矩阵 a b b ba a aaabbb优点优点：判断任意两点之间是否有边方便，仅耗费：判断任意两点之间是否有边方便，仅耗费 O(1)
8、时间。时间。缺点缺点：即使：即使 j 是否有边，最坏需耗费是否有边，最坏需耗费 O(n)时间。无向图同一条边表示两次时间。无向图同一条边表示两次 边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。dataadj结点表中的结点的表示结点表中的结点的表示：用数组用数组data:结点的数据场，保存结点的数据值。结点的数据场，保存结点的数据值。adj:结点的指针场，给出自该结点出发的结点的指针场，给出自该结点出发的 的第一条边的边结点的地址。的第一条边的边结点的地址。邻接表邻接表datafirstarc结点表中的结点的表示结点表中的结点的表
9、示：用单链表用单链表data:结点的数据场，保存结点的结点的数据场，保存结点的 数据值。数据值。firstarc:结点的指针场，给出自该结点的指针场，给出自该 结点出发的的第一条边的结点出发的的第一条边的 边结点的地址。边结点的地址。nextvex:结点的指针场，给出该结结点的指针场，给出该结 点的下一结点的地址。点的下一结点的地址。nextvexcostdestlink边结点表中的结点的表示边结点表中的结点的表示：cost:边结点的数据场，保存边的边结点的数据场，保存边的 权值等。权值等。dest:边结点的指针场，给出本边结点的指针场，给出本 条边依附的另一结点（非条边依附的另一结点（非 出
10、发结点）的地址。出发结点）的地址。link:结点的指针场，给出自该结点的指针场，给出自该 结点出发的的下一条边的结点出发的的下一条边的 边结点的地址。边结点的地址。邻接表邻接表实例实例：ABCD无向图无向图 G2ABCDE向图向图 G1ABCD12030123nullnullnullnull data adj dest linkAB1201234null data adj03041423CDE41nullnullnullnull6条边却用了条边却用了 12 个边结点个边结点!改进：建立邻接多重表改进：建立邻接多重表寻找进入结点的边非常困难寻找进入结点的边非常困难!改进：建立逆邻接表或十字链表改
11、进：建立逆邻接表或十字链表 dest link邻接表邻接表逆邻接表实例逆邻接表实例：ABCD有向图有向图 G1AB230123null002CDnullnullnull注意：在说明邻接表表示图时，我们用数组表示了结点表，这是用于讲解原理用的。注意：在说明邻接表表示图时，我们用数组表示了结点表，这是用于讲解原理用的。但课本中采用用链表表示结点表。如下图所示，其中，但课本中采用用链表表示结点表。如下图所示，其中，为数据场之值为为数据场之值为C的结点的地址，其余类推。的结点的地址，其余类推。nullnullnullnullABCDnullhead邻接表邻接表邻接表的表邻接表的表示和实现：示和实现：A
12、BCD向图向图 G1结点表结点表A tag data next adj dest link边表边表BDC head邻接表的实现邻接表的实现template Graph:Graph(VertexType flag,EdgeType tag):Vertex_finish_flag(flag),Edge_finish_flag(tag)NumVertex=0;NumEdge=0;VertexType v,u;EdgeType e;Vertex*p,*q;/指向顶点的指针。cout Input vertex data one by one!v,v!=Vertex_finish_flag)head=ne
13、w Vertex(v,head,NULL);Exception(!head,“Head is NULL!”);NumVertex+;邻接表的实现邻接表的实现 cout Input edges data one by one!v,cin u,cin e,e!=Edge_finish_flag)Exception(!(p=GetVertexPos(v),“It is NULL!”);/寻找边的出发顶点的地址，为空则错。Exception(!(q=GetVertexPos(u),“It is NULL!”);/寻找边的到达顶点的地址，为空则错。p-adj=new Edge(q,e,p-adj);Ex
14、ception(!p-adj,“Fail on memory!”);NumEdge+;十字接表十字接表datafirstinfirstoutmarkver1ver2边结点表中的结点的表示边结点表中的结点的表示：结点表中的结点的表示结点表中的结点的表示：data:结点的数据场，保存结点的结点的数据场，保存结点的 数据值。数据值。firstout:结点的指针场，给出自该结点的指针场，给出自该 结点出发的的第一条边的结点出发的的第一条边的 边结点的地址。边结点的地址。firstin:结点的指针场，给出进入该结点的指针场，给出进入该 结点的第一条边的结点的第一条边的 边结点的地边结点的地 址。址。ma
15、rk:边结点的标志域边结点的标志域。本书未使用。本书未使用。path2Path1ver1:本条边的出发结点本条边的出发结点 的地址。的地址。ver2:本条边的终止结点本条边的终止结点 的地址。的地址。path1:出发结点相同的边出发结点相同的边 中的下一条边的地址。中的下一条边的地址。path2:终止结点相同的边终止结点相同的边 中的下一条边的地址。中的下一条边的地址。十字接表十字接表实例实例：ABCD向图向图 G10123ABCD01022220033331data firstin firstoutver1ver2 path2 path1用途：用于有向图，用途：用于有向图，查询查询 进入结点
16、和离开结点进入结点和离开结点 的边容易。的边容易。邻接多重表邻接多重表datafirstmarkvertex1path1边结点表中的结点的表示边结点表中的结点的表示：结点表中的结点的表示结点表中的结点的表示：data:结点的数据场，保存结点的结点的数据场，保存结点的 数据值。数据值。first:结点的指针场，给出自该结点的指针场，给出自该 结点出发的的第一条边的结点出发的的第一条边的 边结点的地址。边结点的地址。info:边结点的数据场，保存边的边结点的数据场，保存边的 权值等。本书未使用。权值等。本书未使用。mark:边结点的标志域，用于标识边结点的标志域，用于标识 该条边是否被访问过。该条
17、边是否被访问过。vertex2infovertex1:本条边依附一本条边依附一个结点的地址。个结点的地址。path1:依附于该结点依附于该结点（地址由（地址由vertex1给出）给出）的的边中的下一条边的的地边中的下一条边的的地址。址。path2vertex2:本条边依附的本条边依附的另一个结点的地址。另一个结点的地址。path2:依附于该结点依附于该结点（地址由（地址由vertex2给出）给出）的的边中的下一条边的的地边中的下一条边的的地址。址。邻接多重表邻接多重表实例实例：无向图无向图 G2用途：用于无向图，边表中用途：用于无向图，边表中 的边结点只需存放一的边结点只需存放一 次，节约内存
18、。次，节约内存。ABCDEAB01234 data firstCDE012441310234markvertex1path1vertex2path2注意：本书介绍的图的存储表示方法，注意：本书介绍的图的存储表示方法，计有：邻接矩阵、邻接表、逆邻接计有：邻接矩阵、邻接表、逆邻接表、十字链表、邻接多重表。除邻表、十字链表、邻接多重表。除邻接矩阵之外，其它几种表示方法中接矩阵之外，其它几种表示方法中的结点表和边表，都应该采用动态的结点表和边表，都应该采用动态链表表示。因为这将避免顺序存储链表表示。因为这将避免顺序存储的许多缺点。的许多缺点。图的遍历与连通性图的遍历与连通性图的三种常见的遍历形式：图的
19、三种常见的遍历形式：深度优先搜索深度优先搜索广度广度(或宽度或宽度)优先搜索优先搜索优先度优先搜索优先度优先搜索深度优先搜索深度优先搜索注意：每个结点只能被访问一次，又因为一个结点可以和其它的任何结点相邻接，注意：每个结点只能被访问一次，又因为一个结点可以和其它的任何结点相邻接，为了避免对一个结点的重复访问，必须对访问过的结点加以标记。为了避免对一个结点的重复访问，必须对访问过的结点加以标记。结点的邻接结点的次序是任意的，因此深度优先搜索的序列可能有多种。结点的邻接结点的次序是任意的，因此深度优先搜索的序列可能有多种。深度优先搜索类似于树的前序周游。深度优先搜索类似于树的前序周游。访问方式：访
20、问方式：1、选中第一个被访问的结点。、选中第一个被访问的结点。2、对结点作已访问过的标志。、对结点作已访问过的标志。3、依次从结点的未被访问过的第一个、第二个、第三个、依次从结点的未被访问过的第一个、第二个、第三个 邻接结邻接结 点出发，进行深度优先搜索。转向点出发，进行深度优先搜索。转向2。4、如果还有顶点未被访问，则选中一个起始结点，转向、如果还有顶点未被访问，则选中一个起始结点，转向2。5、所有的结点都被访问到，则结束。、所有的结点都被访问到，则结束。深度优先搜索深度优先搜索有向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。如：有向图的实例：为了说明问题，邻接结点
21、的访问次序以序号为准。序号小的先访问。如：结点结点 5 的邻接结点有两个的邻接结点有两个 6、7，则先访问结点，则先访问结点 6，再访问结点，再访问结点 7。56724135672314从结点从结点 出发的搜索序列：出发的搜索序列：5、6、2、3、1、4、7适用的数据结构：栈适用的数据结构：栈51243从结点从结点 出发的搜索序列：出发的搜索序列：1、2、3、4没有搜索没有搜索 到所有的结点，必到所有的结点，必 须另选图中未访须另选图中未访 问过的结点，问过的结点，继续进行继续进行 搜索。搜索。1567声明：深度（或广度）优先生成树应遵守规范的画法声明：深度（或广度）优先生成树应遵守规范的画法
22、。深度优先搜索的实现深度优先搜索的实现#include SqStack.htemplate void Graph:DFS_Traveling(const VertexType&start)Stack Edge*s(NumEdge);Vertex*p,*m;Edge*q;p=head;while(p)p-tag=0;p=p-next;/置所有顶点未被访问过的标志。p=GetVertexPos(start);/得到 DFS 遍历的起始顶点。if(!p)cout Start vertex is Error!tag=0)p-tag=1;/标志顶点已被访问。cout visited vertex dat
23、a:data adj)s.Push(p-adj);while(!s.IsEmpty()q=s.Top();s.Pop();if(q-link)s.Push(q-link);m=q-dest;if(m-tag=0)m-tag=1;/设置已被访问的标志。cout visited vertex data:data adj)s.Push(m-adj);p=p-next;if(!p&!finished)p=head;finished=1;return;时间复杂性：时间复杂性：邻接矩阵：邻接矩阵：O（n2）邻接表：邻接表：O（n+e）n：结点数：结点数 e：边数：边数广度优先搜索广度优先搜索注意：每个结点
24、只能被访问一次，又因为一个结点可以和其它的任何结点相邻接，注意：每个结点只能被访问一次，又因为一个结点可以和其它的任何结点相邻接，为了避免对一个结点的重复访问，必须对访问过的结点加以标记。为了避免对一个结点的重复访问，必须对访问过的结点加以标记。结点的邻接结点的次序是任意的，因此广度优先搜索的序列可能有多种。结点的邻接结点的次序是任意的，因此广度优先搜索的序列可能有多种。广度优先搜索类似于树的从根出发的按层次遍历。广度优先搜索类似于树的从根出发的按层次遍历。访问方式：访问方式：1、选中第一个被访问的结点、选中第一个被访问的结点 V 2、对结点、对结点 V 作已访问过的标志。作已访问过的标志。3
25、、依次访问结点、依次访问结点 V 的未被访问过的第一个、第二个、第三个的未被访问过的第一个、第二个、第三个第第 M个个 邻接结点邻接结点 W1、W2、W3 Wm，且进行标记。，且进行标记。4、依次访问结点、依次访问结点 W1、W2、W3 Wm的未被访问过的邻接结点，的未被访问过的邻接结点，且进行标记。且进行标记。5、如果还有结点未被访问，则选中一个起始结点，也标记为、如果还有结点未被访问，则选中一个起始结点，也标记为V，转向，转向2。6、所有的结点都被访问到，则结束。、所有的结点都被访问到，则结束。广度优先搜索广度优先搜索 队列的变化队列的变化：ABCDEFGHIJKL树的按层次进行访问的次序
26、：树的按层次进行访问的次序：A、B、C、D、E、F、G、H、I、J、K、L适用的数据结构：队列适用的数据结构：队列 树树：ABCD1、结点、结点A访问后进队访问后进队2、结点、结点A出队、队空出队、队空3、结点、结点A的儿子结点的儿子结点B、C、D访问后进队访问后进队4、结点、结点B出队出队5、结点、结点B的儿子结点的儿子结点E、F、G访问后进队访问后进队6、结点、结点C出队出队7、结点、结点C的儿子结点的儿子结点H访问后进队访问后进队CDEFGCDEFGDEFGDH广度优先搜索广度优先搜索 无向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。如：无向图的实例：为了说明问
27、题，邻接结点的访问次序以序号为准。序号小的先访问。如：结点结点 1 的邻接结点有三个的邻接结点有三个 2、12、11，则先访问结点，则先访问结点 2、11，再访问结点，再访问结点 12。图的广度优先的访问次序：图的广度优先的访问次序：1、2、11、12、3、6、7、10、4、5、8、9适用的数据结构：队列适用的数据结构：队列注意：结点被访问后，进队；然后队首结点出队注意：结点被访问后，进队；然后队首结点出队.121211367104589121211367104589时间复杂性：时间复杂性：邻接矩阵：邻接矩阵：O（n2）邻接表：邻接表：O（n+e）n：结点数：结点数 e：边数：边数无向图的连通
28、分量和生成树无向图的连通分量和生成树ABCDEFGIJLHMKABCDEHMFGIJLK无向图无向图G的三个连通分量的三个连通分量无向图无向图G连通：顶点连通：顶点v至至v 之间有路径存在之间有路径存在连通图：无向图图连通图：无向图图 G 的任意两点之间都是连通的，则称的任意两点之间都是连通的，则称 G 是连通图。是连通图。连通分量：极大连通子图连通分量：极大连通子图无向图的连通分量和生成树无向图的连通分量和生成树生成树生成树：极小连通子图。包含图的所有：极小连通子图。包含图的所有 n 个结点，但只含图的个结点，但只含图的 n-1 条边。在生成树中添条边。在生成树中添 加一条边之后，必定会形成
29、回路或环。因为在生成树的任意两点之间，本来就加一条边之后，必定会形成回路或环。因为在生成树的任意两点之间，本来就是连通的，添加一条变之后，形成了这两点之间的第二条通路。是连通的，添加一条变之后，形成了这两点之间的第二条通路。ABCDEHMABCDEHM无向图无向图G 无向图无向图G的生成树的生成树 生成方法生成方法：进行深度为主的遍历或广度为主的遍历，得到深度优先生成树或广度优先生：进行深度为主的遍历或广度为主的遍历，得到深度优先生成树或广度优先生 成树。成树。GO38无向图的连通分量和生成树无向图的连通分量和生成树生成森林生成森林：在进行深度为主的遍历或广度为主的遍历时，对于非连通图，将得到
30、多棵深：在进行深度为主的遍历或广度为主的遍历时，对于非连通图，将得到多棵深 度优先生成树或广度优先生成树。称之为生成森林。度优先生成树或广度优先生成树。称之为生成森林。ABCDEFGIJLHMKABCDEHMFGIJLK无向图无向图G的生成森林的生成森林无向图无向图G图的优先度优先搜索图的优先度优先搜索(Priority First Search)：根据优先度确定首先被访问的邻接顶点。：根据优先度确定首先被访问的邻接顶点。如：最小生成树中的如：最小生成树中的 Prim 算法等算法等。有向图的强连通分量的求法有向图的强连通分量的求法强连通图：有向图图强连通图：有向图图 G 的任意两点之间都是连通
31、的，则称的任意两点之间都是连通的，则称 G 是强连通图。是强连通图。强连通分量：极大连通子图强连通分量：极大连通子图有向图有向图G有向图有向图G的两个强连通分量的两个强连通分量ABCDABCD有向图的强连通分量的求法有向图的强连通分量的求法1、对有向图、对有向图 G 进行深度为主的搜索，按照退进行深度为主的搜索，按照退 出该结点的次序给结点进行编号。最先退出该结点的次序给结点进行编号。最先退 出的结点的编号为出的结点的编号为 1，其它结点的编号按，其它结点的编号按 次序逐次增大次序逐次增大 1。2、将有向图、将有向图 G 的所有的有向边进行倒置，构的所有的有向边进行倒置，构 造新的有向图记为造
32、新的有向图记为 Gr3、根据步骤、根据步骤 1 对结点进行的编号，选取最大对结点进行的编号，选取最大 编号的结点。从该结点出发，在有向图编号的结点。从该结点出发，在有向图 Gr 上进行深度为主的遍历。如果没有访问上进行深度为主的遍历。如果没有访问 到所有的结点，则从剩余的那些结点中到所有的结点，则从剩余的那些结点中 选取编号最大的结点再进行深度为主的遍选取编号最大的结点再进行深度为主的遍 历。直至所有的结点都被访问到为止。历。直至所有的结点都被访问到为止。4、在最后得到的生成森林中的每一棵生成树、在最后得到的生成森林中的每一棵生成树 ，都是有向图，都是有向图 G 的强连通分量顶点集。的强连通分
33、量顶点集。在主程序中置：在主程序中置：count=0DFS（vextex v）;vextex w;1、mark v =visited 2、for（v 的邻接表中的每一个邻接结的邻接表中的每一个邻接结 点点 w）3、if（mark w =unvisited）;4、DFS（w）;count+;finished v =count;有向图的强连通分量的求法有向图的强连通分量的求法实例：实例：有向图有向图GABCDACDB有向图有向图GrABCDACDBACDB123442134213第一步第一步第二步第二步第三步第三步第四步第四步二棵生成树的结点是有向图二棵生成树的结点是有向图G的两个强连通分量的顶点
34、集：的两个强连通分量的顶点集：A、C、D及及B注意：在第注意：在第 3 步中，在步中，在Gr选取序号最大的结点开始进行选取序号最大的结点开始进行 DFS，目的是保证以该结点为根得到的生成树中，其它结，目的是保证以该结点为根得到的生成树中，其它结点的序号都比它小。这在点的序号都比它小。这在 G 的相应的生成树中，由根到其的相应的生成树中，由根到其它结点之间，是有路径，即连通的。它结点之间，是有路径，即连通的。有向图的强连通分量的求法有向图的强连通分量的求法断言断言：有向图中的强连通分量中的顶点和第二次搜索时得到的生成森林中的生成树中的结点：有向图中的强连通分量中的顶点和第二次搜索时得到的生成森林
35、中的生成树中的结点 精确对应。精确对应。证明要点证明要点：相互直达的：相互直达的v、w;肯定在同一生成树之中。不管是肯定在同一生成树之中。不管是 G 还是还是 Gr,假定在假定在 Gr 中的根为中的根为x 在在 Gr 中，存在着由中，存在着由 x 至至 v 的路径，那么在的路径，那么在 G 中存在一条由中存在一条由 v 至至 x 路径。在路径。在 G 中中 ，由于，由于 x 序号大，而序号大，而 v 序号小；所有存在着一条序号小；所有存在着一条 x 至至 v 的路径。的路径。同理：在同理：在 Gr 中，存在着由中，存在着由x至至 w 的路径，那么在的路径，那么在G中存在一条由中存在一条由 w
36、至至 x 路径。路径。G 中，由于中，由于x序号大，而序号大，而 w 序号小；所有存在着一条序号小；所有存在着一条x至至w的路径。的路径。所以，所以，Gr 中的任意二点中的任意二点 v、w 之间，相互可以到达。之间，相互可以到达。有向图有向图GABCDACDB最小生成树最小生成树定义：生成树中边的权值（代价）之和最小的树。定义：生成树中边的权值（代价）之和最小的树。实例：实例：V0V1V3V2V4V56165556342V0V1V3V2V4V515342左图的最小代价生成树左图的最小代价生成树GO32例：例：Kruscal 算法算法V0V1V3V2V4V56165556342最小代价生成树最小
37、代价生成树V0V1V3V2V4V51534255例：例：Kruscal 算法算法 实例的执行过程实例的执行过程 图图G1、初始连通分量：、初始连通分量：0,1,2,3,4,52、反复执行添加、放弃动作。、反复执行添加、放弃动作。条件：边数不等于条件：边数不等于 n-1时时 边边 动作动作连通分量连通分量 (0,2)添加添加0,2,1,3,4,5 (3,5)添加添加0,2,3,5,1,4 (1,4)添加添加0,2,3,5,1,4 (2,5)添加添加0,2,3,5,1,4 (0,3)放弃放弃因构成回路因构成回路 (2,3)放弃放弃因构成回路因构成回路 (1,2)添加添加0,2,3,5,1,4最小代
38、价生成树最小代价生成树算法实现要点算法实现要点:每个结点增加一个数据场，用于标识该结每个结点增加一个数据场，用于标识该结点所属的集合。可用于判断新的边加入后是否构成回路。点所属的集合。可用于判断新的边加入后是否构成回路。V0V1V3V2V4V56165556342V0V1V3V2V4V51534255Kruscal 算法算法数据结构：用邻接表表示图，用最小化堆实现挑选代价最小的边。数据结构：用邻接表表示图，用最小化堆实现挑选代价最小的边。时间复杂性级别：时间复杂性级别：O(eloge)，用于稀疏图。如：边数，用于稀疏图。如：边数 e 和顶点数和顶点数 n 成正比。成正比。设设 U：set of
39、 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)，否则放
40、弃。转回，否则放弃。转回 最小生成树最小生成树 MST 性质：假设性质：假设 G=V,E 是一个连通图，是一个连通图，U 是结点集合是结点集合 V 的一个非空子集。若：的一个非空子集。若：(u,v)是是 一条代价最小的边，且一条代价最小的边，且 u 属于属于 U,v 属于属于 V-U，则必存在一棵包，则必存在一棵包 括边括边 (u,v)在内在内 的最小代价生成树。的最小代价生成树。证明：假定存在一棵不包括边证明：假定存在一棵不包括边 (u,v)在内的最小代价生成树，设其为在内的最小代价生成树，设其为 T。将边。将边(u,v)添加到树添加到树 T，则形成一条包含，则形成一条包含 (u,v)的回路
41、。因此，必定存在另一条边的回路。因此，必定存在另一条边 (u ，v )，且，且 u 属于属于 U,v 属于属于 V-U。删去边。删去边(u ，v )，得到另一棵生成，得到另一棵生成 树树 T ;因为边因为边(u,v)的代价小于边的代价小于边 (u ，v )的代价，所以新的生成树的代价，所以新的生成树T 将是代价最小的树。和原假设矛盾。将是代价最小的树。和原假设矛盾。uvuvTPrim算法算法 Prim 算法算法的基本描述的基本描述设设 U：set of vertex,G:Graph,T:set of edges(mininum cost spanning tree;u,v:vertex;V:s
42、et of vertex;/初始时，初始时，V 包含所有结点包含所有结点 T ；U v0;/T为最小生成树的边集合为最小生成树的边集合 由于由于v0在在 U 中，其余各结点都在中，其余各结点都在 VU 中，可用一数组记录中，可用一数组记录 VU中的结点至中的结点至v0 的路径。因为它们构成了当前横跨的路径。因为它们构成了当前横跨 U 和和 VU 两个集合的所有的边。两个集合的所有的边。while(U !=V)设设(u,v)是一条代价最小的边，并且是一条代价最小的边，并且 u 在在 U 中，中，v 在在 V-U中。中。T=T+(u,v)；U=U+v;由于由于 v 已被加入已被加入U 中，查找中，
43、查找 由由 v 至它的仍在至它的仍在 VU中的邻接结点中的邻接结点w的边的边 ，若小于原来相应的数组元素记录的最小值，则数组元素之值用该值取，若小于原来相应的数组元素记录的最小值，则数组元素之值用该值取 代。即：该值为从代。即：该值为从w（在（在V-U中）到中）到U中的所有边中最短的一条边的长度中的所有边中最短的一条边的长度 例：例：Prim算法算法最小代价生成树最小代价生成树的生成过程的生成过程UV0V1V3V2V4V56165556342V0V1V3V2V4V56165556342例：例：Prim算法算法最小代价生成树最小代价生成树的生成过程的生成过程UV0V1V3V2V4V5616555
44、6342V0V1V3V2V4V56165556342615 例：例：Prim算法算法最小代价生成树最小代价生成树的生成过程的生成过程UV0V1V3V2V4V56165556342V0V1V3V2V4V56165556342615 例：例：Prim算法算法最小代价生成树最小代价生成树的生成过程的生成过程UV0V1V3V2V4V56165556342V0V1V3V2V4V5616555634251546例：例：Prim算法算法最小代价生成树最小代价生成树的生成过程的生成过程UV0V1V3V2V4V56165556342V0V1V3V2V4V5616555634251546例：例：Prim算法算法最
45、小代价生成树最小代价生成树的生成过程的生成过程UV0V1V3V2V4V56165556342V0V1V3V2V4V5616555634251246例：例：Prim算法算法最小代价生成树最小代价生成树的生成过程的生成过程UV0V1V3V2V4V56165556342V0V1V3V2V4V5616555634251246例：例：Prim算法算法最小代价生成树最小代价生成树的生成过程的生成过程UV0V1V3V2V4V56165556342V0V1V3V2V4V5616555634251246例：例：Prim算法算法最小代价生成树最小代价生成树的生成过程的生成过程UV0V1V3V2V4V5616555
46、6342V0V1V3V2V4V5616555634251243例：例：Prim算法算法最小代价生成树最小代价生成树的生成过程的生成过程UV0V1V3V2V4V56165556342V0V1V3V2V4V5616555634251246例：例：Prim算法算法最小代价生成树最小代价生成树的生成过程的生成过程UV0V1V3V2V4V56165556342V0V1V3V2V4V51534251246例：例：Prim算法算法061501234500000 lowcost closet s注意：注意：lowcost j 表示在表示在 VU 中的结点中的结点 j直接到直接到U中结点的中结点的 所有边之中的
47、最短边的距离。所有边之中的最短边的距离。closet j:表示结点表示结点 j 和和 U 中的中的 结点结点 k=closet j 距离距离当前当前是是 最短的，且为最短的，且为 lowcost j；如：如：sj 为为1，表示，表示 j 在集合在集合U中中 注意：结点注意：结点j直接到直接到U中结点的中结点的边边 通常有多条。通常有多条。0051564012345200220结点结点v0,v1,v2,v3,v4,v5，用下标，用下标0,1,2,3,4,5标识。标识。000001010001 lowcost closet sUV0V1V3V2V4V56165556342V0V1V3V2V4V56
48、165556342615 UV0V1V3V2V4V5616555634251546Prim算法算法template int Graph:Prim(VertexType start,VertexType*tail,EdgeType*weight,VertexType*head)/start是起始顶点的数据值。是起始顶点的数据值。tail、head、weight用于保存边的起始顶点（箭尾指向的用于保存边的起始顶点（箭尾指向的 /顶点）、终止顶点（箭头指向的顶点）和边的权值的一维数组。顶点）、终止顶点（箭头指向的顶点）和边的权值的一维数组。/VertexType和和EdgeType分别是顶点数据和分
49、别是顶点数据和边的权值的类型。边的权值的类型。/AdjMatrixj*MaxNumVertexk 保存保存顶点顶点j、k之间的权值，用一维数组之间的权值，用一维数组 /保存邻接矩阵。即：得到邻接矩阵保存邻接矩阵。即：得到邻接矩阵 j,k j,k EdgeType*lowcost=new EdgeTypeMaxNumVertex;int*closet=new int MaxNumVertex;int*s=new intMaxNumVertex;/若若sk=1，那么顶点，那么顶点k已在顶点集已在顶点集U中。中。int i,j,k,m;for(m=0;m=MaxNumVertex)cout This
50、 is error!endl;return 0;for(i=0;i MaxNumVertex;i+)/查询代价矩阵的第查询代价矩阵的第 m 行。得到在行。得到在V-U中的顶点的中的顶点的 lowcosti=AdjMartrix m*MaxNumVertex+i;/(从顶点出发的从顶点出发的)最短路径。最短路径。closeti=m;si=0;sm=1;/表示顶点表示顶点m已在顶点集已在顶点集U中，中，m 是起始顶点。是起始顶点。Prim算法算法for(i=0;i MaxNumVertex-1;i+)EdgeType min;for(k=0;k MaxNumVertex;k+)if(!sk)bre
