《数据结构与算法》课件chap07

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 图,本章介绍另一种非线性数据结构,图,图,：是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继；,第七章 图,7.1,图的概念,7.2,图的存储结构,7.3,图的遍历,7.4,生成树,7.7,最短路径,7.6,拓扑排序,学习要点,1,熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系；,2,熟练掌握图的两种遍历：深度优先遍历和广度优先遍历的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略,;,3,理解课件中讨论的各种图的算法；,第七 章 图,7.1,图的概念,一 图的概念,二 图的应用,三 图的基本操作,四 图的基本术语,7.1,图的基本概念,一 图的概念,图的定义,图,G,由两个集合构成，记作,G=,其中,V,是顶点的非空有限集合，,E,是边的有限集合，其中边是顶点的无序对或有序对集合。,G1,=,V1,=v,0,v,1,v,2,v,3,v,4,E1,=(v,0,v,1,),(v,0,v,3,),(v,1,v,2,),(v,1,v,4,),(v,2,v,3,)(v,2,v,4,),G1,图示,无序对,(v,i,v,j,),：,用连接顶点,v,i,、,v,j,的线段,表示，称为无向边；,例,V0,V4,V3,V1,V2,G2,图示,有序对,：,用以为,v,i,起点、以,v,j,为终点,的有向线段表示，称为有向,边或弧；,无向图,：在图,G,中，若,所有边是无向边，则称,G,为无向图；,有向图,：在图,G,中，若所有边是有向边，则称,G,为有向图；,混和图,：,在图,G,中，即有无向边也有有向边，则称,G,为混合图；,7.1,图的基本概念,V0,V1,V2,V3,G2,=,V2,=v,0,v,1,v,2,v,3,E2,=, , ,图的应用举例,例,1,交通图（公路、铁路）,顶点：地点,边：连接地点的公路,交通图中的有单行道双行道，分别用有向边、无向边表示,；,例,2,电路图,顶点：元件,边：连接元件之间的线路,例,3,通讯线路图,顶点：地点,边：地点间的连线,例,4,各种流程图,如,产品的生产流程图,顶点：工序,边：各道工序之间的顺序关系,7.1,图的基本概念,V0,V4,V3,V1,V2,V0,V1,V2,V3,1,邻接点及关联边,邻接点：边的两个顶点,关联边：若边,e= (v, u),则称顶点,v,、,u,关连边,e,2,顶点的度、入度、出度,顶点,V,的度,=,与,V,相关联的边的数目,在有向图中：,顶点,V,的出度,=,以,V,为起点有向边数,顶点,V,的入度,=,以,V,为终点有向边数,顶点,V,的度,= V,的出度,+V,的入度,设图,G,的顶点数为,n,，,边数为,e,图的所有顶点的度数和,= 2*e,（,每条边对图的所有顶点的度数和,“,贡献,”,2,度）,e,图的基本术语,7.1,图的基本概念,V0,V4,V3,V1,V2,V0,V1,V2,V3,路径、回路,无向图,G,=,（,V,，,E,）,中的顶点序列,v1,v2,vk,若,(vi,vi+1),E( i=1,2,k-1), v =v1, u =,vk,则称该序列是从顶点,v,到顶点,u,的路径；若,v=u,，,则称该序列为回路；,有向图,D=,（,V,，,E,）,中的顶点序列,v1,v2,vk,若,E (i=1,2,k-1), v =v1, u =,vk,则称该序列是从顶点,v,到顶点,u,的路径；若,v=u,，,则称该序列为回路；,7.1,图的基本概念,在,图,1,中，,V0,V1,V2,V3,是,V0,到,V3,的路径；,V0,V1,V2,V3,V0,是回路；在,图,2,中，,V0,V2,V3,是,V0,到,V3,的路径；,V0,V2,V3,V0,是回路；,例,V0,V4,V3,V1,V2,无向图,G1,V0,V1,V2,V3,有向图,G2,简单路径和简单回路,在一条路径中,若除起点和终点外,所有顶点各不相同,则称该路径为简单路径；,由简单路径组成的回路称为简单回路；,在,图,1,中，,V0,V1,V2,V3,是,简单路径；,V0,V1,V2,V4,V1,不是简单路径；在,图,2,中，,V0,V2,V3,V0,是简单回路；,无向图,G1,有向图,G2,例,V0,V4,V3,V1,V2,V0,V1,V2,V3,连通图（强连通图）,在无（有）向图,G=,中，若对任何两个顶点,v,、,u,都存在从,v,到,u,的路径，则称,G,是连通图（强连通图）,非连通图,连通图,强连通图,非强连通图,V0,V1,V2,V3,V0,V4,V3,V1,V2,V0,V1,V2,V3,V0,V2,V3,V1,V7,V4,子图,设有两个图,G=,（,V,，,E,）、,G1=,（,V1,，,E1,），若,V1,V,，,E1,E,，,E1,关联的顶点都在,V1,中，则称,G1,是,G,的子图；,例,(b),、,(c),是,(a),的子图,(a),(b),(c),V0,V4,V3,V1,V2,V0,V4,V3,V1,V2,V0,V4,V3,V1,V2,连通分图（强连通分量,）,无向图,G,的极大连通子图称为,G,的连通分量,极大连通子图意思是：该子图是,G,连通子图，将,G,的任何不在该子图中的顶点加入，子图不再连通；,连通分图,非连通图,7.1,图的基本概念,V0,V2,V3,V1,V5,V4,V0,V2,V1,非连通分图,有向图,D,的极大强连通子图称为,D,的强连通分量,极大强连通子图意思是：该子图是,D,强连通子图，将,D,的任何不在该子图中的顶点加入，子图不再是强连通的；,强连通分量,V0,V1,V2,V3,V0,V2,V3,V1,7,生成树,包含无向图,G,所有顶点的的极小连通子图称为,G,的,生成树,极小连通子图意思是：该子图是,G,的连通子图，在该子图中删除任何一条边，子图不再连通，,若,T,是,G,的生成树,当且仅当,T,满足如下条件,T,是,G,的连通子图,T,包含,G,的所有顶点,T,中无回路,连通图,G1,G1,的生成树,7.1,图的基本概念,V0,V4,V3,V1,V2,V0,V4,V3,V1,V2,V0,V4,V3,V1,V2,第七 章 图,7.2,图的存储结构,一 数组表示法,二 邻接表,7.2,图的存储结构,图的存储结构,至少要保存两类信息：,1),顶点的数据,2),顶点间的关系,约定,:,G=,是图,V=,v,0,v,1,v,2, v,n-1,设顶点的,角标,为它的编号,如何表示顶点间的关系？,顶点的编号,V0,V4,V3,V1,V2,V0,V1,V2,V3,邻接矩阵,：,G,的邻接矩阵是满足如下条件的,n,阶,矩阵：,Aij=,1,若,(vi,vi+1),E,或,E,0,否则,0 1 0 1 0,0 1 0 1,0 1 0 1 1,0 1 0 0,0 1 1 0 0,0 1 1 0,0 0 0 0,0 0 0 1,0 0 0,一 数组表示法,(,邻接矩阵表示,),在数组表示法中，,用邻接矩阵表示顶点间的关系,7.2,图的存储结构,V0,V4,V3,V1,V2,V0,V1,V2,V3,无向图数组表示法特点：,1,）,无向图邻接矩阵是对称矩阵，同一条边表示了两次；,2,）,顶点,v,的度：等于二维数组对应行（或列）中,1,的个数；,3,）,判断两顶点,v,、,u,是否为邻接点：只需判二维数组对应分量是否为,1,；,4,）,顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值,1,或清,0,；,5,）,设图的顶点数为,n ,存储图用一维数组,数组元素有,m,个 （,m=n),则,G,占用存储空间：,m+n,2,；,G,占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；,对有向图的数组表示法可做类似的讨论,0 1 0 1 0,0 1 0 1,0 1 0 1 1,0 1 0 0,0 1 1 0 0,数组表示法,的空间代价,只与图的顶点数有关,7.2,图的存储结构,V0,V4,V3,V1,V2,图的基本操作：,1,）求,无向图某顶点,vi,的度,(,或有向图中,vi,的出度,),。,Ai0,到,Ain-1,中的非,0,个数，即数组,A,中第,i,行的非,0,元素的个数；,2,）求有向图某,顶点,vi,的 入度。：,A0i,到,A n-1i,中的非,0,个数，即数组,A,中第,i,列的非,0,元素的个数；,3,）检测图中的总边数。扫描整个数组,A,，,统计出数组中非,0,元素的个数。无向图的总边数为非,0,元素个数的一半，而有向图的总弧数为非,0,元素个数,；,0 1 0 1 0,0 1 0 1,0 1 0 1 1,0 1 0 0,0 1 1 0 0,7.2,图的存储结构,V0,V4,V3,V1,V2,V0,V1,V2,V3,0 1 1 0,0 0 0 0,0 0 0 1,0 0 0,邻接表,邻接表是图的链式存储结构,1,无向图的邻接表,顶点：通常按编号顺序将顶点数据存储在一维数组中；,关联同一顶点的,边：用线性链表存储,该结点表示边,（,Vi,Vj,）,其中的,1,是,Vj,在一维数组中的位置,例,7.2,图的存储结构,V0,V4,V3,V1,V2,2,0,1,2,3,4,m-1,V0,V1,V2,V3,V4,1,3,4,2,2,1,1,0,0,3,4,下标 编号,link,图的邻接表类型定义,struct,node /,边（弧）结点的类型定义,int,vertex; /,边（弧）的另一顶点在数组中的位置,struct,node *link;,/,指向下一条边（弧）结点的指针,;,typedef,struct,NODE,；,Typedef,struct,vnode,vertextype,data:,/,顶点的数据类型,NODE *,firstarc,;,/,指向第一条依附该顶点的弧的指针,VNODE;,VNODE,adjlistMAX,;,/,邻接点链表的头指针所对应的数组,7.2,图的存储结构,无向图的邻接表的特点,1,）在,G,邻接表中，同一条边对应两个结点；,2,）顶点,v,的度：等于,v,对应线性链表的长度；,3,）判定两顶点,v,，,u,是否邻接：要看,v,对应线性链表中有无对应的结点,4,）在,G,中增减边：要在两个单链表插入、删除结点；,5,）,设存储顶点的一维数组大小为,m(m,图的顶点数,n),图的边数为,e,，,G,占用存储空间为：,m+2*e,。,G,占用存储空间与,G,的顶点数、边数均有关；适用于边稀疏的图,0,1,2,3,4,m-1,V0,V1,V2,V3,V4,1,3,4,2,2,1,1,0,0,4,3,邻接表的空间代价,与图的边及顶点数均有关,7.2,图的存储结构,V0,V4,V3,V1,V2,2,2,有向图的邻接表和逆邻接表,1,）有向图的邻接表,顶点：用一维数组存储（按编号顺序）,以同一顶点为,起点,的弧,：用线性链表存储,类似于无向图的邻接表，,所不同的是：,以同一顶点为,起点,的弧,：,用线性链表存储,下标 编号,link,V0,V1,V2,V3,1,2,3,0,0,1,2,3,m-1,例,7.2,图的存储结构,V0,V1,V2,V3,2,）有向图的逆邻接表,顶点：用一维数组存储（按编号顺序）,以同一顶点为,终点,的弧,：用线性链表存储,V0,V1,V2,V3,0,1,2,3,m-1,0,0,2,3,类似于有向图的邻接表，,所不同的是：,以同一顶点为,终点,弧,：,用线性链表存储,例,7.2,图的存储结构,V0,V1,V2,V3,建立邻接表的算法,建立无向邻接表,int,create(VNODE *,adjlist, ), NODE *p;,int,num, i, v1, v2;,scanf(“%dn,”, /,读入结点数,for(i=0; inum; i+) /,初始化空关系图,adjlisti.firstarc,=NULL;,adjlisti.data,=i; ,7.2,图的存储结构,for(; ;),scanf(“%d,to %dn”, /,读入一条边,if (v10 | v2vertex=v2;,p-link=adjlistv1.firstarc;,adjlistv1.firstarc=p; /,插入在链表首部,p=(NODE *),malloc(sizeof(NODE,);,p-vertex=v1;,p-link=adjlistv2.firstarc; adjlistv2.firstarc=p;,return(num),;,/,返回图的结点数,7.2,图的存储结构,在不同的存储结构下，实现各种操作的效率可能是不同的。所以在求解实际问题时，要根据求解问题所需操作，选择合适的存储结构。,7.2,图的存储结构,第七 章 图,7.3,图的遍历,一 深度优先遍历,二 广度优先遍历,7.3,图的遍历,图的遍历：,从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组,visitMAX,作为对顶点的标记，当顶点,vi,未被访问，,visiti,值为,0,；当,vi,已被访问，则,visiti,值为,1,。,图的遍历与,树的遍历有什么不同,有两种遍历方法,（,它们对无向图，有向图都适用）,深度优先遍历,广度优先遍历,V0,V7,V6,V7,V4,V3,V2,V1,从图中某顶点,v,出发：,1,）访问顶点,v,；,2,）,依次从,v,的未被访问的邻接点出发，继续对图进行深度优先遍历；,V0,V1,V3,V7,V4,V2,V5,V6,由于没有规定,访问邻接点的顺序，,深度优先序列不是唯一的,这是序列（,1,）,在遍历过程中,所经过的路径,例,一 深度优先遍历,求图,G,以,V0,起点的,的,深度优先序列,：,V0,V1,V3,V2,V7,V6,V5,V4,V0,V1,V4,V7,V3,V2,V5,V6,7.3,图的遍历,如果将图顶点的邻接点,看作二叉树结点的左、右孩子,深度优先遍历与,先序遍历,是不是很类似？,深度优先遍历,从图中某顶点,v,出发：,（,1,）访问顶点,v,；,（,2,）,依次从,v,的未被访问的邻接点,出发，对图进行深度优先遍历；,先序遍历,（,DLR,）,若二叉树非空 （,1,）访问根结点；,（,2,）先序遍历左子树； （,3,）先序遍历右子树,；,7.3,图的遍历,V0,V7,V6,V7,V4,V3,V2,V1,结点定义,typedef,struct,node,int,vertex;,/,边（弧）的另一顶点在数组中的位置,struct,node *link;,/,指向下一条边（弧）结点的指针,;,typedef,struct,NODE,；,Typedef,struct,vnode,int,data;,NODE *,fistarc,;,VNODE;,VNODE,adjlistMAX,;,/,邻接点链表的头指针所对应的数组,辅助数组,int,visitMAX,; /,顶点标志数组,全局变量,NODE *,ptrMAX,; /,顶点链表指针数组,visit,0,1,2,3,4,m-1,0,0,0,0,0,深度优先遍历算法,7.3,图的遍历,调用深度优先遍历算法的主函数,main( ), VNODE,adjlist, MAX;,int,num;,num=,create(adjlist,);,/*,建立图,G,的邻接表 *,/,depthfirst(adjlist, num);,/*,调用对图,G,深度优先搜索算法*,/,深度优先遍历算法,7.3,图的遍历,void,depthfirst,( NODE,adjlist,int,num),int,i;,for (i=0; inum;i+),ptri,=,adjlisti.firstarc,; /,记住每个顶点链表的第一个结点的地址,visiti=0; /,给每个结点一个未访问标记,for (i=0; ivertex;,取结点的邻接顶点,w,if ( visitw= =0),dfs(w,);,ptrv,=,ptrv,-link;,/,记住顶点,v,的,邻接顶点位置，,该邻接点在,w,之后,从第,v,个顶点出发，递归地深度优先遍历图,G,。,7.3,图的遍历,7.3,图的遍历,V0,V7,V6,V5,V4,V3,V2,V1,0,1,2,3,4,5,6,7,V0,V1,V2,V3,V4,V5,V6,V7,1,2,0,1,1,5,7,7,3,0,6,4,2,6,5,2,4,3,如果将图顶点的邻接点,看作二叉树结点的左、右孩子,深度优先遍历算法与,先序遍历算法,的结构是不是很像？,深度优先遍历算法,void,dfs,(,int,v),int,w;,printf,( “%d, “, v); visitv=1;,/,访问此结点,while (,ptrv,！,=NULL,）, w=,ptrv,-vertex;,取结点的邻接顶点,w,if ( visitw= =0; ),dfs(w,);,ptrv,=,ptrv,-link; /,记住,顶点,v,的邻接点位置，,该邻接点在,w,之后,先序遍历递归算法,void,prev,(NODE *root), if (root!=NULL),printf(“%d,”, root-data),；,/,访问此结点,prev(root,-,lch,); /,访问孩子结点,prev(root,-,rch,);,比较,7.3,图的遍历,V0,V7,V6,V5,V4,V3,V2,V1,图中某未访问过的顶点,vi,出发：,1,）,访问顶点,vi,；,2,）,访问,vi,的所有未被访问的邻接点,w,1,w,2, w,k,；,3,）,依次从这些邻接点出发，访问它们的所有未被访问的邻接点,;,依此类推，直到图中所有访问过的顶点的邻接点都被访问；,二 广度优先遍历,（类似于树的按层遍历）,V0,V1,V3,V2,V7,V6,V5,V4,这是序列（,1,）,在遍历过程中,所经过的路径,由于没有规定,访问邻接点的顺序，,广度优先序列不是唯一的,例,求图,G,的以,V0,起点的,的广,度优先序列,V0,V1,V2,V3,V4,V5,V6,V7,7.3,图的遍历,从图中某顶点,vi,出发：,1,）,访问顶点,vi,；（,容易实现）,2,）,访问,vi,的所有未被访问的邻接点,w,1,w,2, w,k,；,（,容易实现）,3,）,依次从这些邻接点（在步骤,2,）访问的顶点）出发，访问它们的所有未被访问的邻接点,;,依此类推，直到图中所有访问过的顶点的邻接点都被访问；,为实现,3,），,需要保存在步骤,(2,）中访问的顶点，而且,访问这些顶点,邻接点,的顺序为：先保存的顶点，其邻接点先被访问。,广度优先遍历算法,在,广度优先遍历算法中，,需设置一队列,Q,，,保存已访问的顶点，,并控制遍历顶点的顺序。,7.3,图的遍历,V0,V7,V6,V5,V4,V3,V2,V1,Q,广度优先遍历,V0,V1,V2,V3,V4,V5,V6,V7,V1,V2,V3,V0,V4,V5,V6,V7,从图中某顶点,v,出发：,1,）,访问顶点,v,；,2,）,访问,v,的所有未被访问的邻接点,w,1,w,2, w,k,；,3,）,依次从这些邻接点出发，访问它们的所有未被访问的邻接点,;,依此类推，直到图中所有访问过的顶点的邻接点都被访问；,7.3,图的遍历,V0,V7,V6,V5,V4,V3,V2,V1,void,breadfirst(int,num),int,;,for (i=0;inum;i+) visiti=0;,/,给所有顶点一个未被访问标记,for (i=0;ivertex;,/,遍历,v,所指的整个链表,if(visitw= =0),/,如果,w,未被访问过,printf(,“,%d,”,w,);,/,访问,w,visitw=1;enter(w);,访问后，,w,入队,p=p-link;,7.3,图的遍历,7.3,图的遍历,V0,V2,V3,V1,V5,V4,V0,V2,V3,V1,V5,V4,深度优先遍历,广度优先遍历,两种遍历,的比较,7.4,生成树,1,无向图的生成树,生成树是一个连通图,G,的一个极小的连通子图。包含图,G,的所有顶点，但只有,n-1,条边，并且是连通的。生成树可由遍历过程中所经过的边组成。,深度优先遍历得到的,生成树称为,深度优先,生成树,；,广,度优先遍历得到的,生成树称为,广,度优先,生成树。,V0,V7,V6,V5,V4,V3,V2,V1,V3,V0,V7,V6,V5,V4,V2,V1,深度优先,生成树,广,度优先,生成树,7.4,生成树,7.4,生成树,要在,n,个城市间建立交通网，要考虑的问题如何在保证,n,点连通的前题下最节省经费,?,V2,V0,V3,V5,V4,V1,3,6,5,2,1,6,5,5,4,6,例,求解,:,连通,6,个城市且代价最小的交通线路,?,如何求连通图的,最小生成树,?,7.4.2,最小生成树（最小支撑树）,若有一个连通的无向图,G,，,有,n,个顶点，并且它的边是有权值的。在,G,上构造生成树,G,最小生成树,n-1,条边的权值之和最小的,G,。,普鲁姆算法基本步骤,设,G=,（,V,，,E,）,为一个具有,n,个顶点的带权的连通网络，,T=,（,U,，,TE,）,为构造的生成树。,（,1,）初始时，,U=u0,，,TE=,；,（,2,）,在所有,u,U,、,v,V-U,的边（,u,v,）,中选择一条权值最小的边，不妨设为（,u,v),；,（,3,）,(u,v),加入,TE,，,同时将,u,加入,U,；,（,4,）,重复,(2),、（,3,），直到,U=V,为止；,二 普鲁姆算法,7.4,最小的生成树,V2,V0,V3,V7,V4,V1,3,6,5,2,1,6,5,5,4,6,V,2,V,0,V,3,V,5,V,4,V,1,3,6,5,2,1,6,5,5,4,6,V,2,V,0,V,3,V,5,V,4,V,1,1,2,V,2,V,0,V,3,V,5,V,4,V,1,1,4,V,2,V,0,V,3,V,5,V,4,V,1,1,4,2,V,2,V,0,V,3,V,5,V,4,V,1,1,4,5,2,V,3,V,0,V,3,V,5,V,4,V,1,1,4,5,3,U=,V0,U=,V0,V2,U=,V0,V2,V5,U=,V0,V2,V5,V3,U=,V0,V2,V5,V3,V1,U=,V0,V2,V5,V3,V1,V4,7.4,最小的生成树,有关数据的存储结构,无向连通网络,:,G,为,选择权值最小的边,:,置一个一维数组：,closest, ,，,对,i,V-U,closest,i= j (j,U),(j,i),是一条边，且是,i,到,U,中各顶点,“,权最小边,”,Lowcosti,：,用来保存连接,i,到,U,中各顶点,“,权最小边,”,的权。,普鲁姆算法涉及的数据和操作：,数据：,无向连通网络,操作,:,选择权值最小的边，不妨设为（,u,v),(u,v),加入,TE,，,u,加入,U,U,V-U,vi,7.4,最小的生成树,V2,V0,V3,V5,V4,V1,3,6,5,2,1,6,5,5,4,6,U,V-U,vi,vj,V,2,V,0,V,3,V,5,V,4,V,1,3,6,5,2,1,6,5,5,4,6,例,0 0 0 0 0 0,0 6,1,5 max max,i,closesti,lowcosti,0 1 2 3 4 5,i,closesti,lowcosti,0 1 2 3 4 5,0 2 0 0 2 2,0 5 0 5 6,4,U= v,0,U= v,0,v,2,V,2,V,0,V,3,V,5,V,4,V,1,3,6,5,2,1,6,5,5,4,6,U,U,7.4,最小的生成树,对,i,V-U,closest,i= j (j,U),(j,i),是一条边，且是,i,到,U,中各顶点,“,权最小边,”,Lowcosti,：,用来保存连接,i,到,U,中各顶点,“,权最小边,”,的权。,V-U= v,1,V2,V3,V4,V5 ,V-U= v,1, V3,V4,V5 ,0 0 0 0 0 0,0 6,1,5 max max,lowcost,0,0 2 0 0 2 2,0 5 0 5 6,4,closest,lowcost,0,2,0 2 0 5 2 2,0 5 0,2,6,0,closest,lowcost,0,2,5,0 2 0 5 2 2,0,5,0 0 6,0,closest,lowcost,0,2,5,3,0 2 0 5 1 2,0 0 0 0,3,0,closest,lowcost,0,2,5,3,1,0 2 0 5 1 2,0 0 0 0 0,0,closest,lowcost,0,2,5,3,1,4,i,closest,0,1 2 3 4 5,U,7.4,最小的生成树,普里姆算法,图采用邻接矩阵表示，邻接矩阵所对应的二维数组是,costMAXMAX,则,(1),初始化,(,U=0),closesti=0;lowcosti=cost0i; lowcost0=0;,(i=1,2,3, n-1;),(2),每次扫描数组,lowcosti,，,找出值最小且不为,0,的,lowcostk,，,得到,最小生成树的一条边（,closestk,k),将其,输出。,（,3,）令,lowcostk,=0,将,k,并入,U,中,（,4,）修改数组,closesti,和,lowcosti,（,lowcosti,！,=0,及,i V-U,（,5,）,重复（,2,）（,3,）（,4,），直到,U=V,（,或循环,n-1,次）结束,7.4,最小的生成树,用普里姆算法,viud,PRIM(,int,costN,int,start_v ),int,closestN,lowcostN,i,j,k,min,;,for (i=0; jN; i+),lowcosti,=coststart_vi;,closesti=start_v;,for (i=1; iN; i+),/,循环,n-1,次，每次求出最小生成树的一条边, min=MAX;,for (j=0; jN; j+),if (,lowcostj,!=0 &,lowcostj,min),min=,lowcostj;k,=j;,/,找出值最小的,lowcostk,printf(“%d,%d:%dn”,closestk,k,lowcostk,);,lowcostk,=0; /,将,k,并入,U,中,for (j=0; jN; j+),/,修改,lowcost, ,和,closest ,if (costkj!=0 & costkj,lowcostj,),lowcostj,=costkj;closestj=k;,7.4,最小的生成树,基本步骤,设,G=,（,V,，,E,）,为一个具有,n,个顶点的带权的连通网络，最小生成树的初始状态为有,n,个,顶点但无边的非连通图,T=,（,V,，,）。,（,1,）将,E,中的边按权值的递增顺序排序，选择权值最小的边，若与相关的顶点落在,T,中不同的连通分量上，则将其加入,T,中，否则，将其弃舍。,（,2,）,循环至所有顶点在同一的连通分量上。,如何识别一条边所相关的顶点是否落在同一个连通分量上？可将一个连通分量的所有顶点看成一个集合，当从,E,中取出一条边（,xi,xj,）,时，若,xi,xj,在同一集合,u,中，则将该边弃舍；否则，则将该边加入到,T,中，并将,xj,所在的集合,v,并入集合,u,中。,三 克鲁斯卡尔算法,7.4,最小的生成树,V2,V0,V3,V5,V4,V1,3,6,5,2,1,6,5,5,4,6,需要引入辅助数组,sets ,（,1,）,初始化：图,G,中的,n,个顶点，构成,n,个连通分量，顶点,xi,对应的连通分量用集合,i,表示，所以,sets i =i,即表示第,i,个顶点在集合,i,中。,（,2,）,依次取出,E,中的边（按边权值递增顺序），设取出的边为（,xi,xj,）。,（,3,）,判断：若,sets i = sets j ,则,表示,xi,和,xj,在同一集合中，返回（,2,）；否则，转到（,4,）。,（,4,）将边 （,xi,xj,）并入,T,，,同时将,xj,所在的集合,v,（与,xj,连通的顶点）并入,xi,所在的集合,u,（与,xi,连通的顶点），即：由,v=setsj,和,u =setsi,，,扫描辅助数组,sets ,，,若,setsk=v,则 令,setsk=u,。,返回（,2,）。,（,7,）重复（,2,）、（,3,）、（,4,），取出,n-1,条边。,7.4,最小的生成树,V2,V0,V3,V5,V4,V1,3,6,5,2,1,6,5,5,4,6,0 1 2 3 4 5,0 1 2 3 4 5,下标,sets,。,V2,V0,V3,V5,V4,V1,3,6,5,2,1,6,5,5,4,6,0 1 2 3 4 5,0 1 2 3 4 5,下标,sets,V2,V0,V3,V5,V4,V1,0 1 2 3 4 5,0 1 2 3 4 5,下标,sets,1,2,3,4,5,克鲁斯卡尔算法中，数据结构定义为：,struct,node,int,begin, end; /,边的相关顶点编号,int,cost; ; /,边的权值,typedef,struct,node EDGE;,EDGE edgesMAX; /,存放边的数组,int,num; /,数组中实际存放的边数,int,kruskal,(EDGE edges ,int,num),int,setsN,t,i,j,k,u,v;,for(i=0; iN; i+) setsi=i; /,初始化,k=0;t=0;,7.4,最小的生成树,克鲁斯卡尔算法：,while(tN)&(knum), i=edgesk.begin; j=edgesk.end;k+;,/,按顺序取出一条边,u=setsi; v=setsj;,/ xi,在集合,u,中,xj,在集合,v,中,if(u!=v),/ xi,xj,不在同一集合中,printf(“%d,%d,: %dn”,u,v,edgesk.cost);,t+;,for (i=0; iN; i+),if(setsi= =v)seti=u;,/ xi,在集合的,v,并入在集合的,u,中,if (t= =N-1)return(1);,else return(0);,7.4,最小的生成树,7.5,最短路径,交通咨询系统、通讯网、计算机网络常要寻找两结点间最短路径,.,交通咨询系统：,A,到,B,最短路径,计算机网,:,发送,Email,节省费用,A,到,B,沿最短路径传送,路径长度,：路径上边数,路径上边的权值之和,最短路径：两结点间权值之和最小的路径,一 问题的提出,7.7,最短路径,例：,求,V0,到,V4,最短路径,V0,到,V4,路径：,V0 V4 47,V0 V1 V4 60,V0 V2 V3 V4 60,V0 V2 V3 V1 V4 55,47,50,10,20,10,15,20,5,30,35,V1,V4,V0,V2,V3,V5,从某源点到其余各点的最短路径,带权值的有向图的单源最短路径问题,如何求从某源点,到其余各点的最短路径？,7.7,最短路径,Dijkstra,算法的基本思想,按路径长度递增顺序求最短路径算法,。,与求最小生成树的普里姆算法类似,1,迪杰斯特拉算法（,Dijkstra,）,Dijkstra,算法的基本步骤,设,V0,是起始源点，,U =,已求得最短路径终点集合。,V-U =,未确定最短路径的顶点的集合,初始时,U =V0,1,）,长度最短的最短路径是边数为,1,的长度最小的路径。,2,）,下一条长度最短的路径：,Vi,V - U,，,先求出,V0,到,Vi,中间只经,U,中结点的最短路径；,上述最短路径中长度最小者即为下一条长度最短的路径；,将所求最短路径的终点加入,U,中；,3,）,重复,2,）直到求出所有的最短路径,7.7,最短路径,7.6,最短路径,100,60,10,10,5,30,50,20,V5,V4,V0,V1,V2,V3,始点 终点 最短路径,路径长度,V0,V1,无,V2,（,V0,，,V2,）,10,V3,（,V0,，,V4,，,V3,）,50,V4,（,V0,，,V4,）,30,V5,（,V0,，,V4,，,V3,，,V5,）,60,有关数据的存储结构,有向连通网络,:,G,，,采用带权邻接矩阵,cost ,存储,具体步骤：,（,1,）初始,U=v0,用辅助数组,distN,。,对,已经找到最短路径终点的顶点,vi ( i,U ),，,vi,所对应的数组分量,disti,的值,为负数；对从,v0,出发，尚未确定为最短路径终点的顶点,vj,（,j,V - U ),，,vj,所,对应的数组分量,distj,的值为,Wvj,，而,Wvj,为从,v0,出发，考虑途经已确定为终点的顶点，到达,vj,(,V - U ),的最短路径。初始时，对,j,V - U,，有,distj=costvj;,而对,U=v,则有,distv= - costvv,。,（,2,）,扫描,dist ,数组，找出非,0,、非负且最小的,distj,（,j,V - U ),，,即从,v0,出发到,vj,（,j,V - U ),的路径是最短的。,（,3,）,vj,并入,U,，则,distj=-distj.,（,4,）,调整,distk(k,V - U ),，,考虑 从,v0,出发，途经,vj,到达,vk,是否更短。比较： 若,-distj+costjkdiskk,则,distk= -diskj+ costjk,(5),重复（,2,）（,3,）（,4,）。共,n-1,次。,迪杰斯特拉算法涉及的数据和操作：,7.6,最短路径,求解步骤,dist1,路径终点,1,dist2,路径终点,2,dist3,路径终点,3,dist4,路径终点,4,dist5,路径终点,5,最短路径,的终点,U：V,辅助数组,max,100,（V0,V5）,10,（V0,V2）,max,30,（,v0,v4,）,V2,V0.V2,i=1,max,-10,（V0,V2）,60,（V0,V2,V3）,30,（V0，V4）,V4,V0,V2,V4,i=2,100,（V0,V5）,-10,（V0,v2）,50,(,V0,v4,v3）,-30,（V0,V4）,max,V3,V0,V2,V4,V3,i=3,90,（V0,V4,v5）,-30,（V0,V4）,-50,（V0,V4,v3）,-10,（V0,V2）,max,V5,V0,V2,V4,V3,V5,i=4,60,（V0,v4,v3,V5）,7.6,最短路径,i=7,max,-60,（V0,v4,v3,V5）,-30,（V0,V4）,-50,（V0,V4,v3）,-10,（V0,V2）,迪杰斯特拉,算法的求解过程,void,dijstra,(,int,costN,int,v ),int,distN,i,j,w,for (i=0; iN; i+) disti=costvi;,/,初始化,distv=-distv;,for( i=0; iN; i+), j=,mincost(dist,);,/,找非,0,、非负且最小的,distj,if( j=0);break;,distj=-distj;,/,vj,并入,U,中,for(k=0;k0),/,vk,是尚未到达的终点,if(-distj+costjkdistk),distk=-distj+costjk;,/,途经,vj,到达,vk,的距离更短,for ( i=0; iN; i+),if(distj0)printf(“%d, %d: %dn”,v,i,-disti);,Dijkstra,算法,7.6,最短路径,int,mincost,(,int,dist ),/,在,V-U,集合中找顶点,j,，,distj,是,dist ,中的最小值,int,i, min, j;,min=MAX;j=0;,for(i=0;i=0& distimin),min=disti;j=i; ,return(j);,7.6,最短路径,7.5.2,所有顶点对之间的最短路径,1, 顶点对之间的最短路径概念,所有顶点对之间的最短路径是指：对于给定的有向网,G=(V,E),要对,G,中任意一对顶点有序对,u,、,v ( u v ),找出,u,到,v,的最短距离和,v,到,u,的最短距离。,解决此问题的一个有效方法是,:,轮流以每一个顶点为源点,重复执行迪杰斯特拉算法,n,次,即可求得每一对顶点之间的最短路径,总的时间复杂度为,O(n,3,),。,下面将介绍用弗洛伊德,(Floyd),算法来实现此功能,时间复杂度仍为,O(n,3,),但该方法比调用,n,次迪杰斯特拉方法更直观一些。,2, 弗洛伊德算法的基本思想,弗洛伊德算法仍然使用前面定义的图的邻接矩阵,costNN,来存储带权有向图。算法的基本思想是,:,设置一个,NxN,的矩阵,ANN,，,其中除对角线的元素都等于,0,外，其它元素,Aij,的值表示顶点,i,到顶点,j,的最短路径长度，运算步骤为：,开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为,，此时, A,ij=costij,以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：,第一步，让所有边上加入中间顶点,0,，取,Aij,与,Ai0+A0j,中较小的值作,Aij,的值,.,因此，弗洛伊德算法可以描述为,:,A,(0),ij=costij; /cost,为图的邻接矩阵,A,(k),ij=minA,(k-1),ij, A,(k-1),ik+A,(k-1),kj,其中,k=0,1,2, n-1,第二步，让所有边上加入中间顶点,1,，取,Aij,与,Ai1+A1j,中较小的值，完成后得到,Aij ,，,如此进行下去，当第,n,步完成后，得到,Ai