数据结构图的基本知识点.ppt

1、第8章图,2020年9月17日,第8章图,8.1 图的基本概念 8.2 图的基本存储结构 8.2.1 邻接距阵及其实现 8.2.2 邻接表及其实现 8.3 图的遍历 8.3.1 深度优先搜索遍历 8.3.2 广度优先搜索遍历 8.4 图的应用 8.4.1 连通图的最小生成树 8.4.2 拓扑排序,一、现实中的图,8.1 图的基本概念,图最常见的应用是在交通运输和通信网络中找出造价最低的方案。通信网络示例如下图所示：,图G是由一个顶点集V和一个边集E构成的数据结构。记为二元组形式： G= (V, E) 其中: V是由顶点构成的非空有限集合，记为：VV0, V1, V2, Vn-1 E是由V中顶点

2、的对偶构成的有限集合，记为：E=(V0, V2), (V3, V4), ，若E为空，则图中只有顶点而没有边。 其中对偶可以表示成： (Vi, Vj)无序的对偶称为边，即(Vi, Vj)=(Vj, Vi) ，其图称为无向图 有序的对偶称为弧，即 ，则称Vi为弧尾，称Vj为弧头，该图称为有向图,二、图的定义,有向图和无向图示例：,无向图G1的二元组表示： V(G1)=V1, V2, V3, V4 E(G1)=(V1, V2)，(V1, V3)，(V1, V4)，(V2, V3)，(V2, V4)，(V3, V4),有向图G3的二元组表示： V(G3)=V1, V2, V3 E(G3)=，,在无向图

3、中，若存在一条边（Vi, Vj），则称Vi和Vj互为邻接点（Adjacent） 在有向图中，若存在一条弧，则称Vi为此弧的起点，称Vj为此弧的终点，称Vi邻接到Vj，Vj邻接自Vi，Vi和Vj互为邻接点。,1邻接点,2顶点的度、入度和出度,在无向图中，与顶点v相邻接的边数称为该顶点的度，记为D(v)。 在有向图中，顶点v的度又分为入度和出度两种： 以顶点v为终点(弧头)的弧的数目称为顶点v的入度，记为ID(v)； 以顶点v为起点(弧尾)的弧的数目称为顶点v的出度，记为OD(v)； 有向图顶点v的度为该顶点的入度和出度之和，即 D(v)=ID(v)+OD(v),无论是有向图还是无向图，一个图的顶

4、点数n、边(弧)数e和每个顶点的度di之间满足以下的关系式：,即在有向图或无向图中： 所有顶点度数之和 ：边数 = 2 ：1,3完全图、稠密图和稀疏图,在图G中： 若G为无向图，任意两个顶点之间都有一条边，称G为无向完全图。顶点数为n，无向完全图的边数： e=Cn2 =n(n1)/2 若G为有向图，任意两个顶点Vi, Vj之间都有弧 、 ，称G为有向完全图。如顶点数为n，有向完全图的弧数： e=Pn2 =n(n1) 例如，无向图G1就是4个顶点无向完全图。 若一个图接近完全图，则称其为稠密图；反之，若一个图含有很少条边或弧（即en2），则称其为稀疏图。,4子图,若有图G=(V, E)和G=(V

5、, E) 且V 是V的子集，即V V ， E是E的子集，即 E E 则称图G为图G的子图。,5路径、回路和路径长度,在无向图G中，若存在一个顶点序列(Vp , Vi1 , Vi2 , , Vin , Vq)，使(Vp, Vi1)，(Vi1, Vi2)，(Vin, Vq)均为图G的边，则该称顶点的序列为顶点Vp到顶点Vq的路径。若G是有向图，则路径是有向的。 路径长度定义为路径上的边数或者弧的数目。 若一条路径中不出现重复顶点，则称此路径为简单路径。 若一条路径的起点和终点相同（Vp=Vq）称为回路或环。 除了起点和终点相同外，其余顶点不相同的回路，称为简单回路或简单环。,例如，在无向图G1中：

6、 顶点序列（V1, V2, V3, V4）是一条从顶点V1到顶点V4，长度为3的简单路径； 顶点序列（V1, V2, V4, V1, V3）是一条从顶点V1到顶点V3，长度为4的路径，但不是简单路径； 顶点序列（V1, V2, V3, V1）是一条长度为3的简单回路。 在有向图G3中： 顶点序列（V2, V3, V2）是一个长度为2的有向简单环。,6连通、连通分量和连通图、生成树,在无向图G中： 如果从顶点Vi 到顶点Vj至少有一条路径，则称Vi与Vj是连通的。 如果图中任意两个顶点都连通，则称G为连通图，否则称为非连通图。 在非连通图G中，任何一个极大连通子图称为G的连通分量。 任何连通图的

7、连通分量只有一个，即其自身，而非连通图有多个连通分量。 在一个连通图中，含有全部顶点的极小(边数最少)连通子图，称为该连通图的生成树。(包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添加一条边之后，必定会形成回路或环),非连通图G4,图G1和G2为连通图,非连通图G4的三个连通分量,连通图G5,连通图G5的两棵生成树,7强连通、强连通分量和强连通图,在有向图G中： 存在从顶点Vi 到顶点Vj的路径，也存在从顶点Vj 到顶点Vi的路径，则称Vi与Vj是强连通的。 如果图中任意两个顶点都是强连通，则称G为强连通图，否则称为非强连通图。 在非强连通图G中，任何一个极大强连通子图称为G

8、的强连通分量。 任何强连通图的强连通分量只有一个，即其自身，而非强连通图有多个强连通分量。,有向图G和强连通分量示例：,8权、带权图、有向网和无向网,在一个图中，各边(或弧)上可以带一个数值，这个数值称为权。 这种每条边都带权的图称为带权图或网 有向网：带权有向图 无向网：带权无向图,8.2 图的基本存储结构,图需存储的信息： 各顶点的数据 各个边（弧）的信息，包括： 哪两个顶点有边（弧） 若有权要表示出来 顶点数、边（弧）数,8.2.1 邻接矩阵及其实现,顶点数据存储： 一维数组（顺序存储） 边（弧）信息的存储： 邻接矩阵：图中n个顶点之间相邻关系的n阶方阵（即二维数组ann） 邻接矩阵中元

9、素值情况（规定自身无边、无弧）：,无向图,有向图,网,W 表示边上的权值； 0 表示vi与vj是同一个顶点 表示一个计算机允许的、大于所有边上权值的数。,1、举例,无向图,特点： 对称 行或列方向的非零元素（或1）的个数为此顶点的度,无向网,1、举例,有向图,特点： 不一定对称 行方向的非零元素（或1）的个数为此顶点的出度 列方向的非零元素（或1）的个数为此顶点的入度,容易实现图的操作，如：求某顶点的度、判断顶点之间是否 有边（弧）、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。,邻接矩阵法优点：,邻接矩阵法缺点：,2、邻接矩阵法

10、特点,3、邻接矩阵存储的图类型定义,# define MAX 100 /* MAX为图中顶点最多个数 */ typedef int vextype; /* vextype为顶点的数据类型 */ typedef struct vextype vexMAX; /* 一维数组存储顶点信息 */ int arcMAXMAX; /*邻接矩阵存储边（弧）信息 */ int vn, en; /* vn顶点数和en边数 */ MGraph; /* 图类型 */,注：MGraph 既可以表示有向图、无向图，也可以表示有整型权的网,分析： 各顶点信息：键盘输入 各边信息：邻接矩阵，顶点间有边值为1，无边值为0 顶

11、点数、边数：键盘输入,例：建一个如图所示的无向图,4、建图运算 建图就是完成图类型变量中各个成员值的创建过程。,执行时输入数据： 5 6 0 1 2 3 4 0 1 0 3 1 2 1 4 2 3 2 4,算法实现（无向图）,void CreateGraph(MGraph *g) int i, j, v, e; scanf(%d %d, /*建有向图时此句不要*/ ,8.2.2 邻接表及其实现,是顺序与链接相结合的图的存储方式 所有顶点组成一个数组，为每个顶点建立一个单链表 有两部分组成： 表头顶点数组（存放顶点信息） 表体单链表（存放与顶点相关的边或弧的信息）,1、举例,无向图,顶点的度：该

12、顶点所在单链表中表结点个数,无向网,与顶点V1相邻接的顶点在数组中的下标,权值,1、举例,有向图,以顶点V1为始点的弧的终点顶点在数组中的下标,顶点的出度 该顶点所在单链表中表结点个数 顶点的入度 查询整个邻接表中的表结点，与该顶点的序号（数组下标）一致的表结点个数,邻接表的缺点：,邻接表的优点：,空间效率高；容易寻找顶点的邻接点；,判断任意两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。,2、邻接表法特点,3、邻接表存储的图类型定义,（1）表(边)结点表示边(或弧)信息的链表中结点,表结点：,邻接点序号(下标),下一个邻接点地址,权值,typedef struct arcn

13、ode int adjvex; struct arcnode *next; ArcNode, *Arc;,表结点类型,3、邻接表存储的图类型定义,（2）顶点结点类型,顶点结点：,顶点信息,链表头指针(指向第一个表结点),typedef struct vexnode vextype vertex; ArcNode *firstarc; VexNode;,顶点结点类型,（3）图的邻接表类型,typedef struct VexNode adjlistMAX; /*顶点结点所在数组*/ int vn, en; ALGraph;,分析： 各顶点信息：顶点数据键盘输入 各链表：若顶点有出度弧，创建表结点

14、，头插入链表 顶点数、边数：键盘输入,例：建一个如图所示的有向图,4、建图运算 建图就是完成图类型变量中各个成员值的创建过程。,执行时输入数据： 4 4 0 1 2 3 0 2 0 1 2 3 3 0,vertex,firstarc,adjvex,next,算法实现（有向图）,void CreateAGraph(ALGraph *g) int i, j, v, e; ArcNode* p; scanf(%d %d, ,思考： 建无向图如何修改？,B,A,C,D,F,E,补例：图的邻接表存储表示,有向图的邻接表,A,B,E,C,D,可见，在有向图的邻接表中不易找到指向该顶点的弧,A,B,E,C,

15、D,有向图的逆邻接表,在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧,8.3 图的遍历,从图中某个顶点出发遍历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。 图的遍历有两种方法： 深度优先搜索遍历（DFS） 广度优先搜索遍历（BFS）。 它们对无向图和有向图都适用。,8.3.1 连通图的深度优先搜索遍历,1深度优先搜索(dfs)的基本思想 首先访问初始出发点V0，并将其标记设置为已访问； 然后任选一个与V0相邻接且没有被访问的邻接点V1作为新的出发点，访问V1之后，将其标记设置为已访问； 再以V1为新的出发点，继续进行深度优先搜索，访问与V1相邻接且没有被访问的任一个

16、顶点V2； 重复上述过程，若遇到一个所有邻接点均被访问过的顶点，则回到已访问顶点序列中最后一个还存在未被访问的邻接点的顶点，再从该顶点出发继续进行深度优先搜索，直到图中所有顶点都被访问过，搜索结束。,例,序列1： V0,V1,V3,V7,V4,V2,V5,V6,从v0出发的DFS序列为：,由于没有规定 访问邻接点的顺序， DFS序列不是唯一的,序列2： V0,V1,V4,V7,V3,V2,V5,V6,算法描述： 访问开始顶点（如 v）； 寻找 v 顶点未被访问的第一个邻接顶点（如 w）； 并把 w 作为开始顶点继续深度优先搜索遍历（递归思想）； 直到所有顶点被访问； 其中处理： （1）访问顶点

17、：自定义访问函数 visit() （2）未被访问的邻接点：定义一个标记数组：int visitedMAX visitedi= 0 i号顶点未被访问 1 i号顶点已被访问 注意：由于函数是递归的，数组定义成外部数组 （3）第一个邻接点：按邻接距阵或邻接表中边存储的顺序,2 dfs递归算法实现,函数实现： 形参：图变量地址，开始顶点的序号（下标） 返回值：无 void dfs(MGraph *g, int v) int j, w; visit(g, v); /*访问v号顶点*/ visitedv=1; /*v号顶点为已访问*/ for(j=0; jvn; j+) /*找所有的邻接顶点*/ if(

18、g-arcvj=1 ,2 dfs递归算法实现,邻接距阵存储结构的图,起始顶点的序号（下标）,void visit (MGraph *g, int v) printf(n %d, g-vexv); ,按算法实现的dfs遍历举例：,V0顶点出发遍历结果（唯一） ： V0、 V1、 V2、 V3、 V4 V2顶点出发遍历结果（唯一） ： V2、 V1、 V0、 V4、 V3,设计程序创建邻接矩阵的无向图，并用dfs图中顶点信息并输出： 宏定义及数据类型： #include #define MAX 20 /*图顶点最多不超过20*/ typedef int vextype; /*图顶点为int型*/

19、typedef struct vextype vexMAX; int arcMAXMAX; int vn, en; MGraph; /*邻接矩阵图类型*/ int visitedMAX; /*访问标记数组*/,函数定义： void CreateGraph(MGraph *g) /*创建无向图*/ void visit(MGraph *g, int v) /*访问图中某个顶点*/ void dfs(MGraph *g, int v) /*dfs遍历图*/ main() /*主函数*/ MGraph mg; /*mg为图结构变量/ int i, start; /*start开始顶点序号*/ Cre

20、ateGraph( ,8.3.2 连通图的广度优先搜索遍历,1广度优先搜索(bfs)的基本思想 从图G=(V, E)的某个起始点v0出发，首先访问起始点v0，接着依次访问v0所有邻接点; 再找v0的第一个邻接顶点(如 w1)，再依次访问w1顶点的所有未被访问的邻接顶点； 再找v0的第二个邻接顶点(如 w2)，再依次访问w2顶点的所有未被访问的邻接顶点； 直到图中所有顶点都被访问到为止。,求图G 的以V0起点的的广度优先序列:,V0,V1,V2,V3,V4,V5,V6,V7,例,从C0出发的BFS序列为：,由于没有规定 访问邻接点的顺序， BFS序列不是唯一的,c0 c1 c2 c3 c4 c5

21、,从图中某顶点vi出发： 1）访问顶点vi ；（容易实现） 2）访问vi 的所有未被访问的邻接点w1 ,w2 , wk ； 3）依次从这些邻接点（在步骤 2）访问的顶点）出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问； 为实现 3），需要保存在步骤2）中访问的顶点，而且访问这些顶点邻接点的顺序为：“先被访问先出发”的原则。故用队列来管理邻接点出发的次序。,在广度优先遍历算法中， 需设置一队列Q， 保存已访问的顶点， 并控制遍历顶点的顺序。,2 bfs算法实现,QUEUE,V0,V1,V2,V3,V4,V5,V6,V7,V1,V2,V3,V0,V4,V

22、5,V6,V7,数据结构： 1）全局标记数组 int visitedMAX; visitedi= 0 i号顶点未被访问 1 i号顶点已被访问 2）邻接表存储结构,算法描述： (1) 定义一个队列Q并初始化 (2) 开始顶点（如 v）入队，置访问标记为1； (3) 当队列不空时，反复做： (a)队头顶点出队w ，访问w； (b)寻找w的所有未被访问的邻接顶点入队，置访问标记为1；,2 bfs算法实现,函数实现： 形参：图变量地址，开始顶点的序号（下标） 返回值：无 void bfs(ALGraph *g, int v) int i, w; ArcNode *p; SeqQueue Q; /*循环

23、队列*/ InitQueue( /*w号顶点的第一个邻接点地址*/,2 bfs算法实现,邻接表存储结构的图,起始顶点的序号（下标）,while(p!=NULL) i=p-adjvex; /*i为邻接顶点的序号（下标）*/ if(visitedi=0) EnQueue( /*找所有未访问的邻接点的循环*/ /*队列循环*/ /*函数结束*/,按算法实现的bfs遍历举例：,V0顶点出发遍历结果（唯一） ： V0、 V1、 V4、 V3、 V2 V2顶点出发遍历结果（唯一） ： V2、 V3、 V1、 V4、 V0,设计程序创建邻接表存储的无向图，并用bfs图中顶点信息并输出： 宏定义及数据类型：

24、#include #include Queue.h /*循环队列相关操作的定义文件*/ #define MAX 20 /*图顶点最多不超过20*/ typedef int vextype; /*图顶点为int型*/ typedef struct arcnode int adjvex; struct arcnode *next; ArcNode; /*表结点类型*/,typedef struct vexnode vextype vertex; ArcNode *firstarc; VexNode; /*顶点结点类型*/ typedef struct VexNode adjlistMAX; /*顶

25、点结点所在数组*/ int vn, en; ALGraph; /*邻接表存储的图类型*/ int visitedMAX; /*访问标记数组*/,函数定义： void CreateGraph(ALGraph *g) /*创建图*/ void visit(MGraph *g, int v) /*访问图中某个顶点*/ void bfs(MGraph *g, int v) /*bfs遍历图*/ main() /*主函数*/ ALGraph alg; /*mg为邻接表图结构变量/ int i, start; /*start开始顶点序号*/ CreateGraph( ,关于遍历小结： 若图是连通的或强连通

26、的，则从图中某一个顶点出发可以访问到图中所有顶点； 若图是非连通的或非强连通图，则需从图中多个顶点出发搜索访问，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为每个连通分量中的顶点集。,问题：如何通过遍历算法，求一个非连通图的连同分量个数？ int count (MGraph *g) int i, m=0; for(i=0; ivn; i+) if(visitedi=0) m+; dfs(g, i); return m; ,生成树定义,图的遍历过程中经过的n个顶点n-1条边即为一棵生成树。,8.4 图的应用,8.4.1 连通图的最小生成树无向图的应用,在无向连通图G中，其一个极

27、小连通子图(无回路)是G的生成树，它含有图中全部n个顶点，但只有n-1条边，且不唯一。,深度优先生成树：按深度优先遍历生成的生成树,c0,c1,c3,c2,c4,c5,例,c0,c1,c3,c2,c4,c5,例,c0,c1,c3,c2,c4,c5,广度优先生成树：按广度优先遍历生成的生成树,非连通图的生成森林,例,要在 n 个城市间建立通讯网，如何在保证 n 个城市连通的前题下最节省经费?,无向网G1,例,要在 n 个城市间建立通讯网，如何在保证 n 个城市连通的前题下最节省经费?,无向网G1,这个问题实际上是连通图的最小生成树问题。,最小生成树的定义,若图G是带权的无向连通图（连通网），生成

28、树上各边权值之和称为生成树的代价，代价最小的生成树称为最小生成树； n个顶点、n-1条边、权值之和最小。,代价：44,代价：60,最小生成树,例,最小生成树的应用,集成电路布线,通讯线路布线,构造最小生成树的准则：,必须只使用该网络中的边来构造最小生成树； 必须使用且仅使用n-1条边来联接网络中的n个顶点。,一、Prim(普里姆)算法,1、算法思想,设原连通网G=(V, E)，生成的最小生成树T=(U, TE)，则算法步骤如下： (1)任选一个顶点u0放入U中，即初始U=u0，TE= (2)找连接U与V-U集合的一条权值最小的边 即找顶点uU,顶点vV-U的权值最小的一条边(u,v)E； 并把

29、顶点v加入到U中，边(u,v) 加入到TE中，即修改U=U+v,TE=TE+(u,v) (3)转到（2）重复执行，直到U=V结束,（a）无向网G1,算法演示:Prim算法求解最小生成树,A,B,C,E,10,15,12,（b）求解过程,6,7,A,B,C,D,E,F,10,10,15,12,12,8,6,5,（a）无向网G1,算法演示:Prim算法求解最小生成树,A,B,C,D,E,F,10,15,12,7,6,5,（b）求解过程,（a）无向网G1,算法演示:Prim算法求解最小生成树,A,B,C,D,E,F,10,15,7,6,5,（b）求解过程,6,A,B,C,D,E,F,10,10,15

30、,12,12,8,7,6,5,（a）无向网G1,算法演示:Prim算法求解最小生成树,A,B,C,D,E,F,10,15,7,6,5,（b）求解过程,6,A,B,C,D,E,F,10,10,15,12,12,8,7,6,5,（a）无向网G1,算法演示:Prim算法求解最小生成树,A,B,C,D,E,F,10,15,7,6,5,（b）求解过程,（a）无向网G1,算法演示:Prim算法求解最小生成树,A,B,C,D,E,F,10,15,7,6,5,（b）求解过程,（a）无向网G1,算法演示:Prim算法求解最小生成树,A,B,C,D,E,F,10,15,7,6,5,（b）求解过程,6,A,B,C,

31、D,E,F,10,10,15,12,12,8,7,6,6,5,（a）无向网G1,算法演示:Prim算法求解最小生成树,B,C,D,E,F,10,10,15,7,5,（b）求解过程,A,6,（a）无向网G1,算法演示:Prim算法求解最小生成树,A,B,C,D,E,F,10,10,7,5,（b）求解过程,15,6,7,A,B,C,D,E,F,10,10,15,12,12,8,7,6,6,5,（a）无向网G1,算法演示:Prim算法求解最小生成树,A,B,C,D,E,F,10,10,5,（b）求解过程,E,6,7,（a）无向网G1,算法演示:Prim算法求解最小生成树,最小生成树,A,B,C,D,

32、E,F,10,10,5,E,1,Prim算法最小生成树生成过程事例(从1号顶点开始),课堂练习：写出如下连通网的最小生成树过程,最小生成树 不唯一！,定义一个结构数组： struct cost int adj; int dist; d20;,2、算法实现,说明： i数组下标，又是图中对应顶点的序号 di.adj表示i号顶点与生成树中顶点集合U距离最小的顶点号（u） di.dist表示i号顶点与生成树中adj顶点（u号顶点）的距离，当dist=0时表示i号顶点已到生成树中。,生成树初始 选0号顶点,2、算法实现,(1)取d数组中dist0的最小值，则把u=0, v=1,w=1送入生成树，其顶点集

33、为：0,1，并修改数组d的内容,生成树初始 选0号顶点,u,v,w,(2)取d数组中dist0的最小值，则把u=1, v=2,w=2送入生成树，其顶点集为：0,1,2，并修改数组d的内容,(3)取d数组中dist0的最小值，则把u=0, v=4,w=5送入生成树，其顶点集为：0,1,2,4，并修改数组d的内容,(4)取d数组中dist0的最小值，则把u=4, v=3,w=3送入生成树，其顶点集为：0,1,2,4,3，并修改数组d的内容,(5)取d数组中dist0的最小值，则把u=2, v=5,w=6送入生成树，其顶点集为：0,1,2,4,3,5，并修改数组d的内容,无向网的建立：,#inclu

34、de #define INF 32767 typedef struct int u, v, w; Tree; /*最小生成树顺序存储元素类型*/ void CreateGraph(MGraph *g) int i, j, w, e; FILE *fp; /*文件指针fp*/ fp=fopen(graph.dat, r); /*打开数据文件*/ /*图的顶点数和边数、顶点数据和边的信息从文件获取*/ fscanf(fp,%d %d, ,无向网的建立（续）：,for(i=0;ivn;i+) g-vexi=A+i; /*顶点数据为A、B、C*/ for(e=0;een;e+) /*从文件读取对应边信

35、息，即有边的顶点序号及权值*/ fscanf(fp, %d %d %d, /*关闭文件*/ /*结束函数*/,文件graph.dat中的内容为： 6 8 0 1 1 0 4 5 0 5 8 1 2 2 2 3 7 2 5 6 3 4 3 3 5 9,无向网邻接距阵的输出：,void OutGraph(MGraph *g) int i, j; printf(n-Graph-n); printf(n vn=%d t en=%d, g-vn, g-en); for(i=0;ivn;i+) for(j=0;jvn;j+) printf(%dt,g-arcij); printf(n); ,输出： -Gr

36、aph- 6 8,prim算法实现：,void Prim(MGraph *g, int v0, Tree E) int i,j, k, min; struct cost int adj; int dist; d20; for(i=0;ivn;i+) /*d数组初始化*/ di.adj=v0; di.dist=g-arcv0i; for(k=0; kvn-1; k+) /*求vn-1条生成树的边*/ min=INF; j=-1; for(i=0; ivn; i+) /*找权值最小的边*/ if(di.dist!=0 /*修改新送入生成树顶点的信息*/,prim算法实现（续）：,for(i=0;

37、ivn; i+) /*修改数组d中数组*/ /*新加入到生成树的j顶点与i顶点边的权值更小，则修改*/ if(di.dist!=0 /*结束求生成树的for */ /*结束函数 */,最小生成树的输出：,void OutTree(Tree E, int k) int i; printf(n spaning treen); for(i=0; ik; i+) /*生成树E数组中有k条边*/ printf(n%c-%c-%d, Ei.u, Ei.v, Ei.w ); ,输出： spaning tree 0-1-1 1-2-2 0-4-5 4-3-3 2-5-6,主函数：,main( ) MGraph G; Tree E20; CreateGraph( ,二、 Kruskal（克鲁斯卡尔）算法,1、算法思想,把图的所有边按其权值从小到大排成升序 先把权值最小的边加入生成树 依次选取后面的边，如该边加到生成树中，使生成树构成回路，则舍弃该边，否则该边加入到生成树中。 重复上述过程，直到生成树中包含n1条边为