数据结构图(共113张)课件.pptx

《数据结构图(共113张)课件.pptx》由会员分享，可在线阅读，更多相关《数据结构图(共113张)课件.pptx（113页珍藏版）》请在三一办公上搜索。

1、数据结构图,数据结构图,9.1 图的根本概念9.1.1 图的定义 图(Graph)G由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E),其中V是顶点的有限集合,记为V(G),E是连接V中两个不同顶点(顶点对)的边的有限集合,记为E(G)。,9.1 图的根本概念,在图G中,如果代表边的顶点对是无序的,那么称G为无向图,无向图中代表边的无序顶点对通常用圆括号括起来,用以表示一条无向边。如果表示边的顶点对是有序的,那么称G为有向图,在有向图中代表边的顶点对通常用尖括号括起来。,在图G中,如果代表边的顶点对是无序的,那么称G为,9.1.2 图的根本术语 1.端点和邻接点 在一个无向图

2、中,假设存在一条边(vi,vj),那么称vi和vj为此边的两个端点,并称它们互为邻接点。在一个有向图中,假设存在一条边,那么称此边是顶点vi的一条出边,同时也是顶点vj的一条入边；称vi和vj分别为此边的起始端点(简称为起点)和终止端点(简称终点)；称vi和vj互为邻接点。,9.1.2 图的根本术语,2.顶点的度、入度和出度 在无向图中,顶点所具有的边的数目称为该顶点的度。在有向图中,以顶点vi为终点的入边的数目,称为该顶点的入度。以顶点vi为始点的出边的数目,称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。假设一个图中有n个顶点和e条边,每个顶点的度为di(1in),那么有：,2.顶

3、点的度、入度和出度,3.完全图 假设无向图中的每两个顶点之间都存在着一条边,有向图中的每两个顶点之间都存在着方向相反的两条边,那么称此图为完全图。显然,完全无向图包含有条边,完全有向图包含有n(n-1)条边。例如,图(a)所示的图是一个具有4个顶点的完全无向图,共有6条边。图(b)所示的图是一个具有4个顶点的完全有向图,共有12条边。,3.完全图,4.稠密图、稀疏图 当一个图接近完全图时,那么称为稠密图。相反,当一个图含有较少的边数(即当en(n-1)时,那么称为稀疏图。5.子图 设有两个图G=(V,E)和G=(V,E),假设V是V的子集,即VV,且E是E的子集,即EE,那么称G是G的子图。例

4、如图(b)是图(a)的子图,而图(c)不是图(a)的子图。,4.稠密图、稀疏图,6.路径和路径长度 在一个图G=(V,E)中,从顶点vi到顶点vj的一条路径是一个顶点序列(vi,vi1,vi2,vim,vj),假设此图G是无向图,那么边(vi,vi1),(vi1,vi2),(vim-1,vim),(vim,vj)属于E(G)；假设此图是有向图,那么,属于E(G)。路径长度是指一条路径上经过的边的数目。假设一条路径上除开始点和结束点可以相同外,其余顶点均不相同,那么称此路径为简单路径。例如,有图中,(v0,v2,v1)就是一条简单路径,其长度为2。,6.路径和路径长度,7.回路或环 假设一条路径

5、上的开始点与结束点为同一个顶点,那么此路径被称为回路或环。开始点与结束点相同的简单路径被称为简单回路或简单环。例如,右图中,(v0,v2,v1,v0)就是一条简单回路,其长度为3。,7.回路或环,8.连通、连通图和连通分量 在无向图G中,假设从顶点vi到顶点vj有路径,那么称vi和vj是连通的。假设图G中任意两个顶点都连通,那么称G为连通图,否那么称为非连通图。无向图G中的极大连通子图称为G的连通分量。显然,任何连通图的连通分量只有一个,即本身,而非连通图有多个连通分量。,8.连通、连通图和连通分量,9.强连通图和强连通分量 在有向图G中,假设从顶点vi到顶点vj有路径,那么称从vi到vj是连

6、通的。假设图G中的任意两个顶点vi和vj都连通,即从vi到vj和从vj到vi都存在路径,那么称图G是强连通图。例如,右边两个图都是强连通图。有向图G中的极大强连通子图称为G的强连通分量。显然,强连通图只有一个强连通分量,即本身,非强连通图有多个强连通分量。,9.强连通图和强连通分量,10.权和网 图中每一条边都可以附有一个对应的数值,这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图,也称作网。,10.权和网,例9.1 有n个顶点的有向强连通图最多需要多少条边？最少需要多 少条边？,答：有n个顶点的有向强连通图最多有n(n-1)条边(构成一个

7、有向完全图的情况)；最少有n条边(n个顶点依次首尾相接构成一个环的情况)。,例9.1 有n个顶点的有向强连通图最多需要多,9.2 图的存储结构,9.2.1 邻接矩阵存储方法 邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n(n0)个顶点的图,顶点的顺序依次为(v0,v1,vn-1),那么G的邻接矩阵A是n阶方阵,其定义如下：(1)如果G是无向图,那么：Aij=1:假设(vi,vj)E(G)0:其他(2)如果G是有向图,那么：Aij=1:假设E(G)0:其他,9.2 图的存储结构 9.2.1 邻接矩阵存储方法,(3)如果G是带权无向图,那么：Aij=wij:假设vivj且(vi,v

8、j)E(G):其他(4)如果G是带权有向图,那么：Aij=wij:假设vivj且E(G):其他,(3)如果G是带权无向图,那么：,数据结构图(共113张)课件,邻接矩阵的特点如下：(1)图的邻接矩阵表示是惟一的。(2)无向图的邻接矩阵一定是一个对称矩阵。因此,按照压缩存储的思想,在具体存放邻接矩阵时只需存放上(或下)三角形阵的元素即可。(3)不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵,因此,当图的顶点较多时,可以采用三元组表的方法存储邻接矩阵。(4)对于无向图,邻接矩阵的第i行(或第i列)非零元素(或非元素)的个数正好是第i个顶点vi的度。,邻接矩阵的特点如下：,数据结构图(共113张)课

9、件,邻接矩阵的数据类型定义如下：#define MAXV typedef struct int no;/*顶点编号*/InfoType info;/*顶点其他信息*/VertexType;/*顶点类型*/typedef struct/*图的定义*/int edgesMAXVMAXV;/*邻接矩阵*/int vexnum,arcnum;/*顶点数,弧数*/VertexType vexsMAXV;/*存放顶点信息*/MGraph;,邻接矩阵的数据类型定义如下：,9.2.2 邻接表存储方法 图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。在邻接表中,对图中每个顶点建立一个单链表,第i个单

10、链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧)。每个单链表上附设一个表头结点。表结点和表头结点的结构如下：表结点 表头结点,9.2.2 邻接表存储方法advexnextarcinfo,其中,表结点由三个域组成,adjvex指示与顶点vi邻接的点在图中的位置,nextarc指示下一条边或弧的结点,info存储与边或弧相关的信息,如权值等。表头结点由两个域组成,data存储顶点vi的名称或其他信息,firstarc指向链表中第一个结点。,其中,表结点由三个域组成,adjvex指示与,数据结构图(共113张)课件,邻接表的特点如下：(1)邻接表表示不惟一。这是因为在每个顶点对应的

11、单链表中,各边结点的链接次序可以是任意的,取决于建立邻接表的算法以及边的输入次序。(2)对于有n个顶点和e条边的无向图,其邻接表有n个顶点结点和2e个边结点。显然,在总的边数小于n(n-1)/2的情况下,邻接表比邻接矩阵要节省空间。(3)对于无向图,邻接表的顶点vi对应的第i个链表的边结点数目正好是顶点vi的度。(4)对于有向图,邻接表的顶点vi对应的第i个链表的边结点数目仅仅是vi的出度。其入度为邻接表中所有adjvex域值为i的边结点数目。,邻接表的特点如下：,邻接表存储结构的定义如下：typedef struct ANode/*弧的结点结构类型*/int adjvex;/*该弧的终点位置

12、*/struct ANode*nextarc;/*指向下一条弧的指针*/InfoType info;/*该弧的相关信息*/ArcNode;typedef struct Vnode/*邻接表头结点的类型*/Vertex data;/*顶点信息*/ArcNode*firstarc;/*指向第一条弧*/VNode;typedef VNode AdjListMAXV;/*AdjList是邻接表类型*/typedef struct AdjList adjlist;/*邻接表*/int n,e;/*图中顶点数n和边数e*/ALGraph;/*图的类型*/,邻接表存储结构的定义如下：,假设一条路径上的开始点

13、与结束点为同一个顶点,那么此路径被称为回路或环。例如,以下图表示某工程的AOE网。p=G-adjlistu.(2)对AOE网进行拓扑排序。广度优先搜索遍历的过程是：首先访问初始点vi,接着访问vi的所有未被访问过的邻接点vi1,vi2,vit,然后再按照vi1,vi2,vit的次序,访问每一个顶点的所有未被访问过的邻接点,依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。vl(F)=vl(I)-c(a10)=16p=p-nextarc;找出关键活动的意义在于,可以适当地增加对关键活动的投资(人力、物力等),相应地减少对非关键活动的投资,从而减少关键活动的持续时间,缩短整个工程的

14、工期。(2)对AOE网进行拓扑排序。lowcostj=costkj;closestj=k;vl(A)=min(vl(B)-c(a1),vl(C)-c(a2),vl(D)-c(a3)=0,2,7=0其中,表结点由三个域组成,adjvex指示与顶点vi邻接的点在图中的位置,nextarc指示下一条边或弧的结点,info存储与边或弧相关的信息,如权值等。图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。n为图G的顶点个数,e为图G的边数。InfoType info;/*该弧的相关信息*/假设图G中的任意两个顶点vi和vj都连通,即从vi到vj和从vj到vi都存在路径,那么称图G是强连通图。

15、,例9.2 给定一个具有n个结点的无向图的邻接矩阵和邻接表。(1)设计一个将邻接矩阵转换为邻接表的算法；(2)设计一个将邻接表转换为邻接矩阵的算法；(3)分析上述两个算法的时间复杂度。解：(1)在邻接矩阵上查找值不为0的元素,找到这样的元素后创立一个表结点并在邻接表对应的单链表中采用前插法插入该结点。算法如下：,假设一条路径上的开始点与结束点为同一个顶点,那么此路径被称为,void MatToList(MGraph g,ALGraph*,void MatToList(MGraph g,ALGrap,(2)在邻接表上查找相邻结点,找到后修改相应邻接矩阵元素的值。算法如下：void ListToM

16、at(ALGraph*G,MGraph,(2)在邻接表上查找相邻结点,找到后修改相应邻接矩,(3)算法1的时间复杂度均为O(n2)。算法2的时间复杂度为O(n+e),其中e为图的边数。,(3)算法1的时间复杂度均为O(n2),9.3 图的遍历9.3.1 图的遍历的概念 从给定图中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着图的边访问图中的所有顶点,使每个顶点仅被访问一次,这个过程称为图的遍历。如果给定图是连通的无向图或者是强连通的有向图,那么遍历过程一次就能完成,并可按访问的先后顺序得到由该图所有顶点组成的一个序列。根据搜索方法的不同,图的遍历方法有两种：一种叫做深度优先搜索法(DF

17、S)；另一种叫做广度优先搜索法(BFS)。,9.3 图的遍历,9.3.2 深度优先搜索遍历 深度优先搜索遍历的过程是：从图中某个初始顶点v出发,首先访问初始顶点v,然后选择一个与顶点v相邻且没被访问过的顶点w为初始顶点,再从w出发进行深度优先搜索,直到图中与当前顶点v邻接的所有顶点都被访问过为止。显然,这个遍历过程是个递归过程。以邻接表为存储结构的深度优先搜索遍历算法如下(其中,v是初始顶点编号,visited是一个全局数组,初始时所有元素均为0表示所有顶点尚未访问过)：,9.3.2 深度优先搜索遍历,void DFS(ALGraph*G,int v)ArcNode*p;visitedv=1;

18、/*置已访问标记*/printf(%d,v);/*输出被访问顶点的编号*/p=G-adjlistv.firstarc;/*p指向顶点v的第一条弧的弧头结点*/while(p!=NULL)if(visitedp-adjvex=0)DFS(G,p-adjvex);/*假设p-adjvex顶点未访问,递归访问它*/p=p-nextarc;/*p指向顶点v的下一条弧的弧头结点*/,void DFS(ALGraph*G,int v),例如,以上图的邻接表为例调用DFS()函数,假设初始顶点编号v=2,给出调用DFS()的执行过程,见教材。,例如,以上图的邻接表为例调用DFS()函数,假设,9.3.3 广

19、度优先搜索遍历 广度优先搜索遍历的过程是：首先访问初始点vi,接着访问vi的所有未被访问过的邻接点vi1,vi2,vit,然后再按照vi1,vi2,vit的次序,访问每一个顶点的所有未被访问过的邻接点,依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。以邻接表为存储结构,用广度优先搜索遍历图时,需要使用一个队列,以类似于按层次遍历二叉树遍历图。对应的算法如下(其中,v是初始顶点编号)：,9.3.3 广度优先搜索遍历,这里用深度优先遍历方法，先给visited数组为全局变量置初值0，然后从0顶点开始遍历该图。(3)如果G是带权无向图,那么：如果给定图是连通的无向图或者是强连通的有

20、向图,那么遍历过程一次就能完成,并可按访问的先后顺序得到由该图所有顶点组成的一个序列。if(lowcostj!=0/*生成边数增1*/课程之间的先后关系可用有向图表示：采用广度优先搜索遍历非连通无向图的算法如下：,void BFS(ALGraph*G,int v)ArcNode*p;int w,i;int queueMAXV,front=0,rear=0;/*定义循环队列*/int visitedMAXV;/*定义存放结点的访问标志的数组*/for(i=0;in;i+)visitedi=0;/*访问标志数组初始化*/printf(%2d,v);/*输出被访问顶点的编号*/visitedv=1;

21、/*置已访问标记*/rear=(rear+1)%MAXV;queuerear=v;/*v进队*/,这里用深度优先遍历方法，先给visited数组为全局变,while(front!=rear)/*假设队列不空时循环*/front=(front+1)%MAXV;w=queuefront;/*出队并赋给w*/p=G-adjlistw.firstarc;/*找w的第一个的邻接点*/while(p!=NULL)if(visitedp-adjvex=0)printf(“%2d,p-adjvex);/*访问之*/visitedp-adjvex=1;rear=(rear+1)%MAXV;/*该顶点进队*/qu

22、euerear=p-adjvex;p=p-nextarc;/*找下一个邻接顶点*/printf(n);,while(front!=rear),例如,以上图的邻接表为例调用BFS()函数,假设初始顶点编号v=2,给出调用BFS()的执行过程,见教材。,例如,以上图的邻接表为例调用BFS()函数,假设初始顶点编号,9.3.4 非连通图的遍历 对于无向图来说,假设无向图是连通图,那么一次遍历能够访问到图中的所有顶点；但假设无向图是非连通图,那么只能访问到初始点所在连通分量中的所有顶点,其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点,分别进行遍历,才能够访问到图中的所有顶

23、点；,9.3.4 非连通图的遍历,对于有向图来说,假设从初始点到图中的每个顶点都有路径,那么能够访问到图中的所有顶点；否那么不能访问到所有顶点,为此同样需要再选初始点,继续进行遍历,直到图中的所有顶点都被访问过为止。,对于有向图来说,假设从初始点到图中的每个顶点都,采用深度优先搜索遍历非连通无向图的算法如下：DFS1(ALGraph*g)int i;for(i=0;in;i+)/*遍历所有未访问过的顶点*/if(visitedi=0)DFS(g,i);,采用深度优先搜索遍历非连通无向图的算法如下：,采用广度优先搜索遍历非连通无向图的算法如下：BFS1(ALGraph*g)int i;for(i

24、=0;in;i+)/*遍历所有未访问过的顶点*/if(visitedi=0)BFS(g,i);,采用广度优先搜索遍历非连通无向图的算法如下：,9.3.5 图遍历的应用,例 假设图G采用邻接表存储，设计一个算法，判断无向图G是否连通。假设连通那么返回1；否那么返回0。解：采用遍历方式判断无向图G是否连通。这里用深度优先遍历方法，先给visited数组为全局变量置初值0，然后从0顶点开始遍历该图。在一次遍历之后，假设所有顶点i的visitedi均为1，那么该图是连通的；否那么不连通。对应的算法如下：,9.3.5 图遍历的应用 例 假设图G采用邻接表,int Connect(ALGraph*G)/*

25、判断无向图G的连通性*/int i,flag=1;for(i=0;in;i+)/*visited数组置初值*/visitedi=0;DFS(G,0);/*调用DSF算法,从顶点0开始深度优先遍历*/for(i=0;in;i+)if(visitedi=0)flag=0;break;return flag;,int Connect(ALGraph*G),例 假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的长度为l的所有简单路径。,解：所谓简单路径是指路径上的顶点不重复。利用回溯的深度优先搜索方法。从顶点u开始，进行深度优先搜索，在搜索过程中，需要把当前的搜索线路记录下来。为此设立一个

26、数组path保存走过的路径，用d记录走过的路径长度。假设当前扫描到的结点u等于v且路径长度为l时，表示找到了一条路径，那么输出路径path。对应的算法如下：,例 假设图G采用邻接表存储，设计一个算法，输出图G中从,void PathAll(ALGraph*G,int u,int v,int l,int path,int d)/*d是到当前为止已走过的路径长度，调用时初值为-1*/int m,i;ArcNode*p;visitedu=1;d+;/*路径长度增1*/pathd=u;/*将当前顶点添加到路径中*/if(u=v/*恢复环境*/,void PathAll(ALGraph*G,int u,

27、void main()int pathMAXV,u=1,v=4,d=3,i,j;MGraph g;ALGraph*G;g.n=5;g.e=6;int AMAXVMAXV=0,1,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,1,0,1,0,0,1,1,0;for(i=0;ig.n;i+)/*建立图9.1(a)的邻接矩阵*/for(j=0;jg.n;j+)g.edgesij=Aij;MatToList(g,G);for(i=0;ig.n;i+)visitedi=0;printf(图G:n);DispAdj(G);/*输出邻接表*/printf(从%d到%d的所有长度为%d路径:n,

28、u,v,d);PathAll(G,u,v,d,path,-1);printf(n);,void main(),程序执行结果如下：图G:0:1 3 1:0 2 2:1 3 4 3:0 2 4 4:2 3从1到4的所有长度为3路径:1 0 3 4 1 2 3 4,1,3,2,4,0,程序执行结果如下：13240,9.4 生成树和最小生成树9.4.1 生成树的概念 一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有构成一棵树的(n-1)条边。如果在一棵生成树上添加一条边,必定构成一个环：因为这条边使得它依附的那两个顶点之间有了第二条路径。一棵有n个顶点的生成树(连通无回路图)有且仅有(

29、n-1)条边,如果一个图有n个顶点和小于(n-1)条边,那么是非连通图。如果它多于(n-1)条边,那么一定有回路。但是,有(n-1)条边的图不一定都是生成树。,9.4 生成树和最小生成树,数据结构图(共113张)课件,9.4.2 无向图的连通分量和生成树 在对无向图进行遍历时,对于连通图,仅需调用遍历过程(DFS或BFS)一次,从图中任一顶点出发,便可以遍历图中的各个顶点。对非连通图,那么需屡次调用遍历过程,每次调用得到的顶点集连同相关的边就构成图的一个连通分量。设G=(V,E)为连通图,那么从图中任一顶点出发遍历图时,必定将E(G)分成两个集合T和B,其中T是遍历图过程中走过的边的集合,B是

30、剩余的边的集合：TB=,TB=E(G)。显然,G=(V,T)是G的极小连通子图,即G是G的一棵生成树。,9.4.2 无向图的连通分量和生成树,由深度优先遍历得到的生成树称为深度优先生成树；由广度优先遍历得到的生成树称为广度优先生成树。这样的生成树是由遍历时访问过的n个顶点和遍历时经历的n-1条边组成。对于非连通图,每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树,各个连通分量的生成树组成非连通图的生成森林。,由深度优先遍历得到的生成树称为深度优先生成树；由,9.4.4 普里姆算法 普里姆(Prim)算法是一种构造性算法。假设G=(V,E)是一个具有n个顶点的带权连通无向图,T=(U,T

31、E)是G的最小生成树,其中U是T的顶点集,TE是T的边集,那么由G构造最小生成树T的步骤如下：,9.4.4 普里姆算法,(1)初始化U=v0。v0到其他顶点的所有边为候选边；(2)重复以下步骤n-1次,使得其他n-1个顶点被参加到U中：从候选边中挑选权值最小的边输出,设该边在V-U中的顶点是v,将v参加U中,删除和v关联的边；考察当前V-U中的所有顶点vi,修改候选边：假设(v,vi)的权值小于原来和vi关联的候选边,那么用(v,vi)取代后者作为候选边。,(1)初始化U=v0。v0到其他顶点的所,普里姆算法求解最小生成树的过程,普里姆算法求解最小生成树的过程,普里姆(Prim)算法如下：#d

32、efine INF 32767/*INF表示*/void Prim(int costMAXV,int n,int v)int lowcostMAXV,min;int closestMAXV,i,j,k;for(i=0;in;i+)/*给lowcost和closest置初值*/lowcosti=costvi;closesti=v;,普里姆(Prim)算法如下：,for(i=1;in;i+)/*找出n-1个顶点*/min=INF;for(j=0;jn;j+)/*在(V-U)中找出离U最近的顶点k*/if(lowcostj!=0,for(i=1;in;i+)/*找出,Prim()算法中有两重for循

33、环,所以时间复杂度为O(n2)。,Prim()算法中有两重for循环,所以时间复杂,9.4.5 克鲁斯卡尔算法 克鲁斯卡尔(Kruskal)算法是一种按权值的递增次序选择适宜的边来构造最小生成树的方法。假设G=(V,E)是一个具有n个顶点的带权连通无向图,T=(U,TE)是G的最小生成树,那么构造最小生成树的步骤如下：(1)置U的初值等于V(即包含有G中的全部顶点),TE的初值为空集(即图T中每一个顶点都构成一个分量)。(2)将图G中的边按权值从小到大的顺序依次选取：假设选取的边未使生成树T形成回路,那么参加TE；否那么舍弃,直到TE中包含(n-1)条边为止。,9.4.5 克鲁斯卡尔算法,克鲁

34、斯卡尔算法求解最小生成树的过程,克鲁斯卡尔算法求解最小生成树的过程,为了简便,在实现克鲁斯卡尔算法Kruskal()时,参数E存放图G中的所有边,假设它们是按权值从小到大的顺序排列的。n为图G的顶点个数,e为图G的边数。typedef struct int u;/*边的起始顶点*/int v;/*边的终止顶点*/int w;/*边的权值*/Edge;,为了简便,在实现克鲁斯卡尔算法Kruskal(,void Kruskal(Edge E,int n,int e)int i,j,m1,m2,sn1,sn2,k;int vsetMAXV;for(i=0;in;i+)vseti=i;/*初始化辅助数

35、组*/k=1;/*k表示当前构造最小生成树的第几条边,初值为1*/j=0;/*E中边的下标,初值为0*/while(kn)/*生成的边数小于n时循环*/m1=Ej.u;m2=Ej.v;/*取一条边的头尾顶点*/sn1=vsetm1;sn2=vsetm2;/*分别得到两个顶点所属的集合编号*/,void Kruskal(Edge E,int n,in,if(sn1!=sn2)/*属不同的集合-最小生成树的一条边*/printf(%d,%d):%dn,m1,m2,Ej.w);k+;/*生成边数增1*/for(i=0;in;i+)/*两个集合统一编号*/if(vseti=sn2)/*集合编号为sn2

36、的改为sn1*/vseti=sn1;j+;/*扫描下一条边*/,if(sn1!=sn2)/*属不同的集合-最,完整的克鲁斯卡尔算法应包括对边按权值递增排序，上述算法假设边已排序的情况下，时间复杂度为O(n2)。如果给定的带权连通无向图G有e条边,n个顶点，采用堆排序(在第11章中介绍)对边按权值递增排序，那么用克鲁斯卡尔算法构造最小生成树的时间复杂度降为O(elog2e)。由于它与n无关，只与e有关，所以说克鲁斯卡尔算法适合于稀疏图。,完整的克鲁斯卡尔算法应包括对边按权值递增排序,9.5 最短路径9.5.1 路径的概念 在一个无权的图中,假设从一顶点到另一顶点存在着一条路径,那么称该路径长度为

37、该路径上所经过的边的数目,它等于该路径上的顶点数减1。由于从一顶点到另一顶点可能存在着多条路径,每条路径上所经过的边数可能不同,即路径长度不同,我们把路径长度最短(即经过的边数最少)的那条路径叫做最短路径,其路径长度叫做最短路径长度或最短距离。,9.5 最短路径,对于带权的图,考虑路径上各边上的权值,那么通常把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度。从源点到终点可能不止一条路径,把带权路径长度最短的那条路径称为最短路径,其路径长度(权值之和)称为最短路径长度或者最短距离。,对于带权的图,考虑路径上各边上的权值,那么通常,9.5.2 从一个顶点到其余各顶点的最短路径 问

38、题：给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径,并限定各边上的权值大于或等于0。,9.5.2 从一个顶点到其余各顶点的最短路径,采用狄克斯特拉(Dijkstra)算法求解 根本思想是：设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组：第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径v,vk,就将vk参加到集合S中,直到全部顶点都参加到S中,算法就结束了)第二组为其余未确定最短路径的顶点集合(用U表示)。,采用狄克斯特拉(Dijkstra)算法求解,按最短路径长度的递增次序依次把第二组的顶点参加S中。在参加的过程中,总保持从源

39、点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。,按最短路径长度的递增次序依次把第二组的顶点参加,狄克斯特拉算法的具体步骤如下：(1)初始时,S只包含源点,即S=v,v的距离为0。U包含除v外的其他顶点,U中顶点u距离为边上的权(假设v与u有边)或(假设u不是v的出边邻接点)。(2)从U中选取一个距离v最小的顶点k,把k参加S中(该选定的距离就是v到k的最短路径长度)。(3)以k为新考虑的中间点,修改U中各顶点的距离：假

40、设从源点v到顶点u(uU)的距离(经过顶点k)比原来距离(不经过顶点k)短,那么修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。(4)重复步骤(2)和(3)直到所有顶点都包含在S中。,狄克斯特拉算法的具体步骤如下：,V到j的最小距离MIN(cvk+wkj,cvj),V到j的最小距离MIN(cvk+wkj,cvj),S U dist path 0 1 2 3 4 5 6 0 1 2 3 4 5 60 1,2,3,4,5,6 0,4,6,6,0,0,0,0,-1,-1,-1 0,1 2,3,4,5,6 0,4,5,6,11,0,0,1,0,1,-1,-10,1,2 3,4,5,6 0

41、,4,5,6,11,9,0,0,1,0,1,2,-10,1,2,3 4,5,6 0,4,5,6,11,9,0,0,1,0,1,2,-10,1,2,3,5 4,6 0,4,5,6,10,9,17 0,0,1,0,5,2,50,1,2,3,5,4 6 0,4,5,6,10,9,16 0,0,1,0,5,2,40,1,2,3,5,4,6 0,4,5,6,10,9,16 0,0,1,0,5,2,4,S,狄克斯特拉算法如下(n为图G的顶点数,v0为源点编号)：void Dijkstra(int costMAXV,int n,int v0)int distMAXV,pathMAXV;int sMAXV;i

42、nt mindis,i,j,u;for(i=0;in;i+)disti=costv0i;/*距离初始化*/si=0;/*s置空*/if(costv0iINF)/*路径初始化*/pathi=v0;else pathi=-1;sv0=1;pathv0=0;/*源点编号v0放入s中*/,狄克斯特拉算法如下(n为图G的顶点数,v0为源点编号)：,for(i=0;in;i+)/*循环直到所有顶点的最短路径都求出*/mindis=INF;u=-1;for(j=0;jn;j+)/*选取不在s中且具有最小距离的顶点u*/if(sj=0/*输出最短路径*/,for(i=0;in;i+)/*循,void Ppat

43、h(int path,int i,int v0)/*前向递归查找路径上的顶点*/int k;k=pathi;if(k=v0)return;/*找到了起点那么返回*/Ppath(path,k,v0);/*找k顶点的前一个顶点*/printf(%d,k);/*输出k顶点*/,void Ppath(int path,int i,void Dispath(int dist,int path,int s,int n,int v0)int i;for(i=0;in;i+)if(si=1)printf(“从%d到%d的最短路径长度为:%dt路径为:,v0,i,disti);printf(%d,v0);/*输

44、出路径上的起点*/Ppath(path,i,v0);/*输出路径上的中间点*/printf(%dn,i);/*输出路径上的终点*/else printf(从%d到%d不存在路径n,v0,i);,void Dispath(int dist,int pa,9.5.3 每对顶点之间的最短路径 问题：对于一个各边权值均大于零的有向图,对每一对顶点vivj,求出vi与vj之间的最短路径和最短路径长度。可以通过以每个顶点作为源点循环求出每对顶点之间的最短路径。除此之外,弗洛伊德(Floyd)算法也可用于求两顶点之间最短路径。,9.5.3 每对顶点之间的最短路径,假设有向图G=(V,E)采用邻接矩阵cost

45、存储,另外设置一个二维数组A用于存放当前顶点之间的最短路径长度,分量Aij表示当前顶点vi到顶点vj的最短路径长度。弗洛伊德算法的根本思想是递推产生一个矩阵序列A0,A1,Ak,An,其中Akij表示从顶点vi到顶点vj的路径上所经过的顶点编号不大于k的最短路径长度。,假设有向图G=(V,E)采用邻接矩阵cost存储,初始时,有A-1ij=costij。当求从顶点vi到顶点vj的路径上所经过的顶点编号不大于k+1的最短路径长度时,要分两种情况考虑：一种情况是该路径不经过顶点编号为k+1的顶点,此时该路径长度与从顶点vi到顶点vj的路径上所经过的顶点编号不大于k的最短路径长度相同；另一种情况是从

46、顶点vi到顶点vj的最短路径上经过编号为k+1的顶点。,初始时,有A-1ij=costi,Ak+1i,j=MIN(Aki,j,Aki,k+1+Akk+1,j,Ak+1i,j=MIN(Aki,j,Aki,k+1,数据结构图(共113张)课件,弗洛伊德思想可用如下的表达式来描述：A-1ij=costij Ak+1ij=MIN Akij,Akik+1+Akk+1j(0kn-1),弗洛伊德思想可用如下的表达式来描述：,采用弗洛伊德算法求解过程,采用弗洛伊德算法求解过程,考虑顶点v0,A0ij表示由vi到vj,经由顶点v0的最短路径。只有从v2到v1经过v0的路径和从v2到v3经过v0的路径,不影响v2

47、到v1和v2到v3的路径长度,因此,有：,考虑顶点v0,A0ij表示由vi到vj,考虑顶点v1,A1ij表示由vi到vj,经由顶点v1的最短路径。存在路径v0-v1-v2,路径长度为9,将A02改为9,path02改为1,因此,有：,考虑顶点v1,A1ij表示由vi到vj,经由,考虑顶点v2,A2ij表示由vi到vj,经由顶点v2的最短路径。存在路径v3-v2-v0,长度为4,将A30改为4；存在路径v3-v2-v1,长度为4,将A31改为4。存在路径v1-v2-v0,长度为7,将A10改为7。将path30、path31和path10均改为2。因此,有：,考虑顶点v2,A2ij表示由vi到v

48、j,经,考虑顶点v3,A3ij表示由vi到vj,经由顶点v3的最短路径。存在路径v0-v3-v2,长度为8比原长度短,将A02改为8；存在路径v1-v3-v2-v0,长度为6(A13+A30=2+4=6)比原长度短,将A10改为6；存在路径v1-v3-v2,长度为3,比原长度短,将A12改为3；将path02、path10后path12均改为3。因此,有：,考虑顶点v3,A3ij表示由vi到vj,从0到0路径为：0,0路径长度为：0从0到1路径为：0,1路径长度为：5从0到2路径为：0,3,2路径长度为：8从0到3路径为：0,3路径长度为：7从1到0路径为：1,3,2,0路径长度为：6从1到1

49、路径为：1,1路径长度为：0从1到2路径为：1,3,2 路径长度为：3从1到3路径为：1,3路径长度为：2,A=,Path=,从0到0路径为：0,0路径长度为：0A=Path=,从2到0路径为：2,0路径长度为：3从2到1路径为：2,1路径长度为：3从2到2路径为：2,2路径长度为：0从2到3路径为：2,3路径长度为：2从3到0路径为：3,2,0 路径长度为：4从3到1路径为：3,2,1 路径长度为：4从3到2路径为：3,2路径长度为：1从3到3路径为：3,3路径长度为：0,从2到0路径为：2,0路径长度为：3,弗洛伊德算法如下：void Floyd(int costMAXV,int n)in

50、t AMAXVMAXV,pathMAXVMAXV;int i,j,k;for(i=0;i(Aik+Akj)Aij=Aik+Akj;pathij=k;Dispath(A,path,n);/*输出最短路径*/,弗洛伊德算法如下：,9.6 拓扑排序 设G=(V,E)是一个具有n个顶点的有向图,V中顶点序列v1,v2,vn称为一个拓扑序列,当且仅当该顶点序列满足以下条件：假设是图中的边(即从顶点vi到vj有一条路径),那么在序列中顶点vi必须排在顶点vj之前。在一个有向图中找一个拓扑序列的过程称为拓扑排序。,9.6 拓扑排序,例如,计算机专业的学生必须完成一系列规定的根底课和专业课才能毕业,假设这些课