《数据结构图学习.pptx》由会员分享，可在线阅读，更多相关《数据结构图学习.pptx（183页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、揭安全江西省高等学校精品课程江西师范大学计算机信息工程学院江西师范大学计算机信息工程学院第1页/共183页第章图图的基本概念 图的基本运算 生成树与最小生成树 拓扑排序 图的基本存储结构 最短路径关键路径 图的遍历第2页/共183页8.1 图的基本概念图的基本概念一、图的定义图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，它可以形式化地表示为：图（V，E）其中V=x|x某个数据对象集，它是顶点的有穷非空集合；E=（x，y）|x，yV或E=|x，yV且P（x，y），它是顶点之间关系的有穷集合，也叫做边集合，P（x，y）表示从x到y的一条单向通路。第3页/共
2、183页图的应用举例例1 交通图（公路、铁路）顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示；V0 V4 V3 V1 V2 V0 V1 V2 V3例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线第4页/共183页 通常，也将图G的顶点集和边集分别记为V（G）和E（G）。E（G）可以是空集，若E（G）为空，则图G只有顶点而没有边。若图G中的每条边都是有方向的，则称G为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对表示一条由vi到vj的有向边。有向边又称为弧，弧的始点称为弧尾，弧的终
3、点称为弧头。若图G中的每条边都是没有方向的，则称G为无向图。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。第5页/共183页图8-1v1v2v3v4v1v2v4v5v3（a）有向图G1（b）无向图G2图8.1（a）表示的是有向图G1，该图的顶点集和边集分别为：V（G1）=v1，v2，v3，v4E（G1）=，例例有序对：用以为vi起点、以vj为终点的有向线段表示，称为有向边或弧；第6页/共183页例：图8-1v1v2v3v4v1v2v4v5v3（a）有向图G1（b）无向图G2图8.1（b）表示的是无向图G2，该图的顶点集和边集分别为：V（G2）=v1，v2，v3，v4，v5E（G2）=（
4、vl，v2），（v1，v3），（v1，v4），（v2，v3），（v2，v5），（v4，v5）无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；第7页/共183页在以后的讨论中，我们约定：（1）一条边中涉及的两个顶点必须不相同，即：若（vi，vj）或是E（G）中的一条边，则要求vivj；（2）一对顶点间不能有相同方向的两条有向边；（3）一对顶点间不能有两条无向边，即只讨论简单的图。第8页/共183页若用n表示图中顶点的数目，用e表示图中边的数目，按照上述规定，容易得到下述结论：对于一个具有n个顶点的无向图，其边数e小于等于n（n-1）/2，边数恰好等于n（n-1）/2的无向图称为
5、无向完全图；对于一个具有n个顶点的有向图，其边数e小于等于n（n-1），边数恰好等于n（n-1）的有向图称为有向完全图。也就是说完全图具有最多的边数，任意一对顶点间均有边相连。二、完全图第9页/共183页例：图8-2v1v2v3v4v1v2v3v4（a）无向完全图G3（b）有向完全图G4图8.2所示的GG3 3与与GG4 4分别是具有4个顶点的无向完全图和有向完全图。图G3共有4个顶点6条边；图GG4 4共有4个顶点12条边。若（vi，vj）是一条无向边，则称顶点v vi i和和v vj j互为邻接点。第10页/共183页若是一条有向边，则称vi邻接到vj，vj邻接于vi，并称有向边关联于vi
6、与vj，或称有向边与顶点vi和vj相关联。三、度、入度、出度在图中，一个顶点的度就是与该顶点相关联的边的数目，顶点v的度记为D（v）。例如在图8.2（a）所示的无向图GG3 3中，各顶点的度均为3。若G为有向图，则把以顶点v为终点的边的数目称为顶点v的入度，记为ID（v）；把以顶点v为始点的边的数目称为v的出度，记为OD（v），有向图中顶点的度数等于顶点的入度与出度之和，即D（v）=ID（v）+OD（v）。第11页/共183页无论有向图还是无向图，图中的每条边均关联于两个顶点，因此，顶点数n、边数e和度数之间有如下关系：e=e=.（式8-1）四、子图给定两个图Gi和Gj，其中Gi=（Vi，Ei
7、），Gj=（Vj，Ej），若满足ViVj，EiEj，则称Gi是Gj的子图。第12页/共183页v1v2v4v2v3v4v1v2v3v4v1v4v2v3v4v1v1v3v2v4子图示例（a）无向图G3的部分子图（b）有向图G4的部分子图第13页/共183页五、路径 无向图G中若存在着一个顶点序列v v、v v1 1、v v2 2、v vmm、u u，且且（v v，v v1 1）、（v v1 1，v v2 2）、（v vmm，u u）均均属属于于E E（GG），则称该顶点序列为顶点v到顶点u的一条路径，相应地，顶点序列u u、v vmm、v vm-1m-1、v v1 1、v是顶点u到顶点v的一条路
8、径。如果G是有向图，路径也是有向的，它由E（G）中的有向边、v、vu组成。路径长度是该路径上边或弧的数目。第14页/共183页如果一条路径上除了起点v和终点u相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同（v=u）的简单路径称为简单回路或简单环。第15页/共183页六、连通图与强连通图在无向图G中，若从顶点v vi i到顶点v vj j有路径，则称v vi i与与v vj j是连通的。若V（G）中任意两个不同的顶点v vi i和和v vj j都连通（即有路径），则称G为连通图。例如，图8.1（b）所示的无向图GG2 2、图8.2（a）所示的无向图GG3 3是都是连通图。无向
9、图G的极大连通子图称为G的连通分量。根据连通分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。第16页/共183页例：非连通图及其连通分量示例（a）非连通图G5（b）G5的两个连通分量H1和H2在有向图G中，若对于V（G）中任意两个不同的顶点v vi i和和v vj j，都存在从v vi i到到v vj j以以及从及从v vj j到到v vi i的路径，则称G是强连通图。V V1 1V V2 2V V4 4V V5 5V V3 3V V1 1V V2 2V V4 4V V5 5V V3 3第17页/共183页有向图的极大强连通子图称为G的强连通分量。根据强连通图的定义
10、，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分量。例如，图8.2（b）所示的有向图GG4 4是一个具有4个顶点的强连通图，图8.5（a）所示的有向图GG6 6不是强连通图（v v2 2、v v3 3、v v4 4没有到达v v1 1的路径），它的两个强连通分量H H3 3与H H4 4如图8.5（b）所示。v1v2v3v4v1v2v3v4（a）非强连通图G6（b）G6的两个强连通分量H3和H4第18页/共183页七、网络有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫权。权可以表示两个顶点之间的距离、耗费等具有某种意义的数。若将图的每条边都赋上一个权，则称这种
11、带权图为网络。V0V1V3V234567825V0V2V1455064（a）无向网络G7（b）有向网络G8第19页/共183页8.2图的基本运算 图是一种复杂数据结构，由图的定义及图的一组基本操作构成了图的抽象数据类型。ADTGraph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=|v，wV且P（v，w），P（v，w）定义了边（v，w）的信息第20页/共183页图的基本操作如下：（1）Creat（n）创建一个具有n个顶点，没有边的图；（2）Exist（i，j）如果存在边（i，j）则返回1，否则返回0；（3）Edges（）返回图中边的数目；（4）Vertices（）返
12、回图中顶点的数目；（5）Add（i，j）向图中添加边（i，j）；（6）Delete（i，j）删除边（i，j）；（7）Degree（i）返回顶点i的度；（8）InDegree（i）返回顶点i的入度；（9）OutDegree（i）返回顶点i的出度；ADTGraph第21页/共183页8.3 图的基本存储结构图的基本存储结构 图的邻接矩阵存储表示法图的邻接多重表表示法图的邻接表表示法第22页/共183页8.3 图的基本存储结构图的基本存储结构 图的存储结构至少要保存两类信息：1)顶点的数据2)顶点间的关系约定:G=是图,V=v0,v1,v2,vn-1,设顶点的角标为它的编号 如何表示顶点间的关系？V
13、0 V4 V3 V1 V2 V0 V1 V2 V3第23页/共183页邻接矩阵及其实现给定图G=（V，E），其中V（G）=v v0 0，v vi i，v vn-1n-1，G的邻接矩阵（AdacencyMatrix）是具有如下性质的n阶方阵：无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。一、非网络的邻接矩阵第24页/共183页v0v1v3v2v3v1v0v2图的邻接矩阵示例01111010110110100100101011000100A1=A2=图8.7 无向图G9及有向图G10的邻接矩阵表示 第25页/共183页用邻接矩阵表示图，很容易判定任意两个顶点之间是否有边相连，并求得各个
14、顶点的度数。对于无向图，顶点v vi i的度数是邻接矩阵中第i行或第i列值为1的元素个数，即：D D（v vi i）=（8-28-2）对于有向图，邻接矩阵中第i行值为1的元素个数为顶点v vi i的出度，第i列值为1的元素的个数为顶点v vi i的入度，即：ODOD（v vi i）=;ID=;ID（v vi i）=（8-38-3）第26页/共183页二、网络的邻接矩阵当G=（V，E）是一个网络时，G的邻接矩阵是具有如下性质的n阶方阵：Wij当（vi，vj）或E（G）0当（vi，vj）或E（G）且i=j当（vi，vj）或E（G）且ijAi，j=其中Wij表示边上的权值；表示一个计算机允许的、大于
15、所有边上权值的数。第27页/共183页V0V1V3V234567825V0V2V1455064网络的邻接矩阵示例05634785603402578250050045640A3=A4=（a）G7的邻接矩阵（b）G8的邻接矩阵图8.8网络邻接矩阵示例第28页/共183页邻接矩阵存储结构/*/*邻接矩阵类型定义文件名：ljjz.h*/*/#include#defineFINITY5000/*此处用5000代表无穷大*/#defineM20/*最大顶点数*/typedefcharvertextype;/*顶点值类型*/typedefintedgetype;/*权值类型*/typedefstructve
16、rtextypevexsM;/*顶点信息域*/edgetypeedgesMM;/*邻接矩阵*/intn,e;/*图中顶点总数与边数*/Mgraph;第29页/共183页/*函数功能：建立图的邻接矩阵存储结构函数参数：邻接矩阵的指针变量g；存放图信息的文件名s；图的类型参数c，c=0表示建立无向图，否则表示建立有向图函数返回值：无*/voidcreat(Mgraph*g,char*s,intc)inti,j,k,w;/*建立网络的邻接矩阵存储结构*/FILE*rf;rf=fopen(s,r);/*从文件中读取图的边信息*/if(rf)fscanf(rf,%d%d,&g-n,&g-e);/*读入图
17、的顶点数与边数*/第30页/共183页for(i=0;in;i+)/*读入图中的顶点值*/fscanf(rf,%1s,&g-vexsi);for(i=0;in;i+)/*初始化邻接矩阵*/for(j=0;jn;j+)if(i=j)g-edgesij=0;elseg-edgesij=FINITY;for(k=0;ke;k+)/*读入网络中的边*/fscanf(rf,%d%d%d,&i,&j,&w);g-edgesij=w;if(c=0)g-edgesji=w;/*建立无向图邻接矩阵*/fclose(rf);第31页/共183页elseg-n=0;图的文件信息以文本文件的形式提供，里面存放了图的顶
18、点数、边数、顶点信息和所有的边信息。当建立网络存储结构时，边信息以三元组（i，j，w）的形式输入，i、j分别表示两顶点的序号，w表示边上的权。第32页/共183页V0V1V3V2345678254401230156023403782325输入文件g7.txt内容建图调用方式:creat(&g,”g7.txt”，0)例:对图8.6所示的无向网络G7当参数c=1时，将建立有向图的存储结构。当建立非网络的存储结构时，所有的边信息只需按二元组（i，j）的形式输入，边的权值取值为0或1。第33页/共183页邻接表及其实现邻接表及其实现 用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而
19、与边的数目无关。一个含有n个顶点的图，如果其边数比n n2 2少得多，那么它的邻接矩阵就会有很多空元素，浪费了存储空间。第34页/共183页n无向图的邻接表对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表。单链表中的每个结点至少包含两个域，一个为邻接点域（adjvex），它指示与顶点v vi i邻接的顶点在图中的位序，另一个为链域（next），它指示与顶点v vi i邻接的下一个结点。第35页/共183页adjvexnextvertexfirstdege为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成
20、了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结构。v0v1v3v2图8.7无向图G91 2 3 0 2 0 1 3 0 2 V0V1V2V3图8.9G9的邻接表表头结点结构边结点结构第36页/共183页对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边；对于有向图来说，如果每一顶点vi的邻接表中每个表结点都存储以vi的为始点射出的一条边，则称这种表为有向图的出边表（有向图的邻接表），反之，若每一顶点vi的邻接表中每个表结点都对应于以vi为终点的边（即射入vi的边），则称这种表为有向图的入边表（又称逆邻接表）。v0v1v2v31 0 2 0 1 1
21、G10的出边表v3v1v0v2图8.7(b)有向图G10第37页/共183页对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边；对于有向图来说，如果每一顶点vi的邻接表中每个表结点都存储以vi的为始点射出的一条边，则称这种表为有向图的出边表（有向图的邻接表），反之，若每一顶点vi的邻接表中每个表结点都对应于以vi为终点的边（即射入vi的边），则称这种表为有向图的入边表（又称逆邻接表）。v0v1v2v3 1 2 0 2 1 3 G10的入边表v3v1v0v2图8.7(b)有向图G10第38页/共183页在无向图的邻接表中，顶点vi的度为第i个链表中结点的个数；而在有向图的出边表中，
22、第i个链表中的结点个数是顶点vi的出度；为了求入度，必须对整个邻接表扫描一遍，所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。1 2 3 0 2 0 1 3 0 2 V0V1V2V3V0的度为3v0v1v2v31 0 2 0 1 1 G10的出边表V0的出度为1，入度为2第39页/共183页邻接表的存储结构/*/*邻接表存储结构文件名：ljb.h*/*/#include#include#defineM20/*预定义图的最大顶点数*/typedefcharDataType;/*顶点信息数据类型*/typedefstructnode/*边表结点*/intadjvex;/*邻接点*/str
23、uctnode*next;EdgeNode;adjvexnextadjvexnext边结点结构边结点结构第40页/共183页typedefstructvnode/*头结点类型*/DataTypevertex;/*顶点信息*/EdgeNode*FirstEdge;/*邻接链表头指针*/VertexNode;typedefstruct/*邻接表类型*/VertexNodeadjlistM;/*存放头结点的顺序表*/intn,e;/*图的顶点数与边数*/LinkedGraph;vertexfirstdege头结点结构第41页/共183页/*函数功能：建立图的邻接表函数参数：邻接表指针变量g；存放图信
24、息的文件名filename；图的类型参数c，c=0表示建立无向图，否则表示建立有向图函数返回值：无*/voidcreat(LinkedGraph*g,char*filename,intc)inti,j,k;EdgeNode*s;FILE*fp;fp=fopen(filename,r);if(fp)fscanf(fp,%d%d,&g-n,&g-e);/*读入顶点数与边数*/第42页/共183页for(i=0;in;i+)fscanf(fp,%1s,&g-adjlisti.vertex);/*读入顶点信息*/g-adjlisti.FirstEdge=NULL;/*边表置为空表*/for(k=0;k
25、e;k+)/*循环e次建立边表*/fscanf(fp,%d%d,&i,&j);/*输入无序对（i,j）*/s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=j;/*邻接点序号为j*/s-next=g-adjlisti.FirstEdge;g-adjlisti.FirstEdge=s;/*将新结点*s插入顶点vi的边表头部*/第43页/共183页if(c=0)/*无向图*/s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=i;/*邻接点序号为i*/s-next=g-adjlistj.FirstEdge;g-adj
26、listj.FirstEdge=s;/*将新结点*s插入顶点vj的边表头部*/fclose(fp);else g-n=0;/*文件打开失败*/算法8.2建立无向图的邻接表算法第44页/共183页说明：一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为在邻接表结构中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。第45页/共183页45ABCD0102031223ABDC例:若需建立下图所示的无向图邻接表存储结构,则输入文件的内容应该是：则将建立如下的邻接表存储结构。A3-2-1B2-0C3-1-0D2-0第46页/共183页邻接多重表邻接多重表 在邻接多重表中，每一条边
27、只有一个边结点。为有关边的处理提供了方便。边结点的结构 mark vexi linki vexj linkj 其中，mark是记录是否处理过的标记；vexi和vexj是依附于该边的两顶点位置。lniki域是链接指针，指向下一条依附于顶点vexi的边；linkj也是链接指针，指向下一条依附于顶点vexj的边。需要时还可设置一个存放与该边相关的权值的域cost。第47页/共183页顶点结点的结构 存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中，vertex存放与该顶点相关的信息，firstedge是指示第一条依附于该顶点的边的指针。在邻接多重表中,所有依附于同一个顶点的边
28、都链接在同一个单链表中。从顶点i出发,可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。vertex Firstedge第48页/共183页V0V1V3V234567825V0V1V2V356013402780325230123无向网络的邻接多重表示例其中边表结点增加了一个存储权值的数据域。第49页/共183页8.4 图的遍历图的遍历图的遍历与树的遍历有什么不同有两种遍历方法（它们对无向图，有向图都适用）深度优先遍历广度优先遍历第50页/共183页深度优先遍历从图中某顶点v出发：1）访问顶点v；2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历；算法演示acdefkhbg
29、230164857第51页/共183页深度优先遍历对于给定的图G=（V，E），首先将V中每一个顶点都标记为未被访问，然后，选取一个源点vV，将v标记为已被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，如果从v出发有路的顶点都已被访问过，则从v的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，并从这个顶点开始做新的搜索。上述过程一直进行到V中所有顶点都已被访问过为止。第52页/共183页 V0 V7 V6 V5 V4 V3 V2 V1 V0 V1 V3 V2 V
30、7 V6 V5 V4例序列1：V0,V1,V3,V7,V4,V2,V5,V6深度优先遍历过程：由于没有规定访问邻接点的顺序，深度优先序列不是唯一的序列2：V0,V1,V4,V7,V3,V2,V5,V6第53页/共183页c0c1c3c2c4c5c0c1c3c2c4c5DFS序列：c0c1c3c4c5c2但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果将是确定的。第54页/共183页采用邻接表存储结构的深度优先遍历算法实现：/*/*图的深度优先遍历算法文件名：dfs.c*/*/#includeljb.hintvisitedM;/*函数功能：从顶点i开始深度优先遍历图的连通分量函数
31、参数：图的邻接表g，遍历起点i*/voiddfs(LinkedGraphg,inti)EdgeNode*p;printf(visitvertex:%cn,g.adjlisti.vertex);第55页/共183页/*访问顶点i*/visitedi=1;p=g.adjlisti.FirstEdge;while(p)/*从p的邻接点出发进行深度优先搜索*/if(!visitedp-adjvex)dfs(g,p-adjvex);p=p-next;第56页/共183页/*函数功能：深度优先遍历图函数参数：图的邻接表g*/voidDfsTraverse(LinkedGraphg)inti;for(i=0
32、;ig.n;i+)visitedi=0;/*初始化标志数组*/for(i=0;ihead)/*当队列非空时，执行下列循环体*/j=queue+head;/*出队*/p=g.adjlistj.FirstEdge;while(p)/*广度优先搜索邻接表*/if(visitedp-adjvex=0)printf(%c,g.adjlistp-adjvex.vertex);queue+tail=p-adjvex;visitedp-adjvex=1;第65页/共183页p=p-next;/*函数功能：广度优先遍历图g函数参数：邻接表g函数返回值：返回连通分量的个数*/intBfsTraverse(Link
33、edGraphg)inti,count=0;for(i=0;ig.n;i+)visitedi=0;/*初始化标志数组*/for(i=0;ig.n;i+)第66页/共183页if(!visitedi)/*vi未访问过*/printf(n);count+;/*连通分量个数加1*/bfs(g,i);returncount;voidmain()LinkedGraphg;intcount;charfilename20;printf(PleaseinputfilenameofGraph:n);gets(filename);第67页/共183页creat(&g,filename,0);/*创建无向图的邻接表
34、*/printf(nThegraphis:n);print(g);count=BfsTraverse(g);/*从顶点0出发广度优先遍历图g*/printf(n该图共有%d个连通分量。n,count);算法8.4图的广度优先遍历算法（邻接表表示法）算法的时间复杂度与深度优先算法相同。第68页/共183页8.5 生成树与最小生成树生成树与最小生成树生成树与最小生成树的概念构造最小生成树的Prim算法构造最小生成树的kruskal算法构造最小生成树的准则第69页/共183页8.5 生成树与最小生成树生成树与最小生成树对于一个无向的连通图G=（V，E），设G是它的一个子图，如果G中包含了G中所有的顶
35、点（即V（G）=V（G）且G是无回路的连通图，则称G为G一棵的生成树。生成树是无向图的极小连通子图。图的遍历过程中经过的n个顶点n-1条边即为一棵生成树。第70页/共183页深度优先生成树：按深度优先遍历生成的生成树c0c1c3c2c4c5例c0c1c3c2c4c5第71页/共183页c0c1c3c2c4c5例例c0c1c3c2c4c5广度优先生成树：按广度优先遍历生成的生成树第72页/共183页非连通图的生成森林V0V1V3V4V2V6V8V7V5V9（a）不连通的无向图G12V0V1V3V4V2V8V7V9V6V5（c）图G12的一个BFS生成森林V0V1V3V4V2V6V8V7V5V9（
36、b）图G12的一个DFS生成森林第73页/共183页最小生成树的定义最小生成树的定义例例要在n个城市间建立通讯网，如何在保证n个城市连通的前题下最节省经费?ABCDEF101015121287665无向网G1ABCDEF10101276花费：45ABCDEF1512865花费：465ABCDEF107610花费：38第74页/共183页最小生成树的定义最小生成树的定义例例要在n个城市间建立通讯网，如何在保证n个城市连通的前题下最节省经费?ABCDEF101015121287665无向网无向网GG1 1这个问题实际上是连通图的最小生成树问题。第75页/共183页最小生成树的定义最小生成树的定义定
37、义：对于一个具有n个顶点的无向连通网G，若G是的G的一棵生成树，并且树中n-1条边的权值之和在所有的生成树中最小，则称G是无向网G的最小生成树。ABCDEF1010151212876655ABCDEF107610第76页/共183页最小生成树的应用集成电路布线通讯线路布线第77页/共183页如何快速有效地构造最小生成树第78页/共183页构造最小生成树的准则：假设G=（V，E）是一个连通网，U是顶点集V的一个非空真子集，若（u，v）是满足uU，vV-U的边（称这种边为两栖边）且（u，v）在所有的两栖边中具有最小的权值，则必存在一棵包含边（u，v）的最小生成树。构造最小生成树的MST性质：必须只
38、使用该网络中的边来构造最小生成树；必须使用且仅使用n-1条边来联接网络中的n个顶点。第79页/共183页证明：反证时假设G中的任何一棵最小生成树都不含此最小两栖边。MST性质图示：u uuuU UvvV-UV-U该边必在一棵最小生成树中第80页/共183页证明：设T是连通网上的一棵最小生成树，且T不包含(u,v)。MST性质图示：u uuuU UvvV-UV-UT T当将（u,v）加入到T中时，由生成树的定义，T中必存在一条包含（u,v）的回路。第81页/共183页证明：删去图中的边（u,v），便可消除上述回路，同时得到另一棵生成树T。因为（u,v）的代价不高于（u,v），则T的代价亦不高于T
39、，T是包含（u,v）的一棵最小生成树。由此和假设矛盾。MST性质图示：uuU UvvV-UV-UTT第82页/共183页n普里姆算法的基本思想：最小生成树的普里姆算法最小生成树的普里姆算法(Prim)算法和和(Kruskal)算法是两个利用MST性质构造最小生成树的算法。从连通网络 G=V,E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合U中。第83页/共183页n普里姆算法的基本思想：最小生成树的普里姆算法最小生成树的普里姆算法(Prim)算法和和(Kruskal)算法是两个利用MST性质构造最小生成树的算法。以后每一步从一个顶点在U中
40、，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。第84页/共183页ABCDEF101015121287665（a）无向网G1算法演示:Prim算法求解最小生成树A ABCE101512（b）求解过程第85页/共183页67ABCDEF1010151212865（a）无向网G1算法演示:Prim算法求解最小生成树A AB BCDEF101512765（b）求解过程第86页/共183页ABCDEF101015121287665（a）无向网G1算法演示:Prim算法求解最小生成树A AB BCD
41、EF1015765（b）求解过程第87页/共183页6ABCDEF10101512128765（a）无向网G1算法演示:Prim算法求解最小生成树A AB BCD DEF1015765（b）求解过程第88页/共183页6ABCDEF10101512128765（a）无向网G1算法演示:Prim算法求解最小生成树A AB BCD DEF10157665（b）求解过程第89页/共183页ABCDEF101015121287665（a）无向网G1算法演示:Prim算法求解最小生成树A AB BCD DEF F1015765（b）求解过程第90页/共183页86ABCDEF10101512128766
42、5（a）无向网G1算法演示:Prim算法求解最小生成树B BCD DEF F10101575（b）求解过程A A第91页/共183页6ABCDEF101015121287665（a）无向网G1算法演示:Prim算法求解最小生成树A AB BC CD DEF F101075（b）求解过程第92页/共183页67ABCDEF101015121287665（a）无向网G1算法演示:Prim算法求解最小生成树A AB BC CD DEF F1010125（b）求解过程E E第93页/共183页67ABCDEF101015121287665（a）无向网G1算法演示:Prim算法求解最小生成树最小生成树A
43、 AB BC CD DEF F10105E E第94页/共183页Prim算法的基本步骤如下：（1）初始化：U=u0，Tree=;（2）如果U=V（G），则输出最小生成树T，并结束算法；（3）在所有两栖边中找一条权最小的边（u，v）（若候选两栖边中的最小边不止一条，可任选其中的一条），将边（u，v）加入到边集Tree中，并将顶点v并入集合U中。（4）由于新顶点的加入，U的状态发生变化，需要对U与V-U之间的两栖边进行调整。（5）转步骤（2）第95页/共183页Prim算法实现：1、连通图用邻接矩阵net表示：edgesij=WWij ij 当（当（v vi i,v,vj j）E E（GG）且权
44、为）且权为WWij ij 否则否则 0 0 当当i=ji=j第96页/共183页Prim算法实现：2、边tree（生成树）edgetreen-1typedefstructedgedataintbeg,en;/*beg,en是结点序号*/intlength;/*边长*/edge;第97页/共183页for(j=k+1;j=g.n-2;j+)/*求最小两栖边所在位置*/if(treej.lengthmin)算法关键一步：求第k条最小两栖边，将其加入tree中1）求当前最小两栖边及应添加的点vmin=treek.length;s=k;/*S记录最小边所在的位置*/min=treej.length;s
45、=j;v=trees.en;/*用v记录入选顶点*/第98页/共183页2）通过交换，将当前最小两栖边加入tree中x=trees;trees=treek;treek=x;3）调整各剩余点对应的最小两栖边（由v加入引起）for(j=k+1;j=g.n-2;j+)d=g.edgesv treej.en;if(dtreej.length)treej.length=d;treej.beg=v;第99页/共183页算法总体控制：1）初始化：建立初始入选点，并初始化生成树边集tree。for(v=1;v=g.n-1;v+)treev-1.beg=0;treev-1.en=v;treev-1.length
46、=g.edges0v;begenlength0000012345101215第100页/共183页算法总体控制：2）依次求当前最小两栖边，并将其加入treefor(k=0;kg.n-2;k+)执行算法关键一步 第101页/共183页程序演示：prim.cABCDEF101015121287665（a）无向网G1610ABCDEF01100212041512724121351562583564510数据文件G1.txt第102页/共183页程序演示：prim.cABHIGCEDF1812979525631108598672145834（b）无向网G2915ABCDEFGHI01340245071
47、20818789128675285792656243164102321346745853598数据文件G2.txt第103页/共183页程序演示：prim.cABHIGCEDF12979311021834（c）无向网G2的最小生成树第104页/共183页 易于分析，prim算法的时间复杂度为O(n2)，适于稠密图。第105页/共183页最小生成树的克鲁斯卡尔算法最小生成树的克鲁斯卡尔算法 Kruskal算法基本思想：(基于避圈思想，称避圈法）为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克鲁斯卡尔算法需对e条边按权值进行排序，其时间复杂度为O(elog2e)，则适于稀疏
48、图。克鲁斯卡尔算法的做法就是：先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。第106页/共183页算法：（1）初始化，TV=v0，v1，vn，TE=；（2）如果TE具有n-1条边，则输出最小生成树T，并结束算法。（3）在有序的E（G）边表序列中，从当前位置向后寻找满足下面条件的一条边（u，v）：使得u在一个连通分量上，v在另一个连通分量上，即（u，v）是满足此条件权值最小的边，将其加入到T中，合并u与v所在的两个连通分量为一个连通分量。（4）转（2）第107页/共183页例2：Kruskal算法构
49、造最小生成树的过程ABCDEF101015121287665无向网G1ABCDEF5(a)ABCDEF65(b)ABCDEF65(c)7ABCDEF65(d)710ABCDEF65(e)71010第108页/共183页练习一、对下图所示的连通网，用kruskal算法构造其最小生成树。二、用C语言实现kruskal算法。A7BCDEFG46435214651245无向连通网第109页/共183页思考：还有什么方法可以求出一个图的最小生成树？第110页/共183页求最小生成树的破圈法p此法1975年由中国数学家管梅谷教授首先提出,具体算法如下:步骤若Tree无回路,则Tree是最小生成树,算法结束
50、,否则转步骤.步骤在Tree中任取的一条回路C中取有最大权的边e,置Tree:=Tree-e后转步骤.p将赋权简单连通无向图G=V,E的边排序:e1e2em。开始时Tree:=E.第111页/共183页8.6 最短路径最短路径问题的提出：交通咨询系统、通讯网、计算机网络常要寻找两结点间最短路径；交通咨询系统：A到B最短路径；计算机网络：发送Email节省费用A到B沿最短路径传送；路径长度：路径上边数路径上边的权值之和最短路径：两结点间权值之和最小的路径；第112页/共183页ABDCFE2415288181013始点 终点 最短路径 路径长度A B （A，C，B）19 C （A，C）4 D （