同济大学计算机编程课件：C++ds08.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图的基本概念,图的存储表示,图的遍历与连通性,最小生成树,最短路径,活动网络,第八章 图,图的基本概念,图定义,图是由顶点集合,(,vertex),及顶点间的关系集合组成的一种数据结构,：,Graph(,V,E,),其中,V,=,x,|,x,某个数据对象,是顶点的有穷非空集合；,E,=(,x,y,)|,x,y,V,或,E,=,|,x,y,V,&,Path,(,x,y,),是顶点之间关系的有穷集合，也叫做边(,edge),集合。,Path,(,x,y,),表示从,x,到,y,的一条单向通路,它是有方向的。,有向图与无向图,在有向图中，顶点对,是有序的。在无向图中，顶点对(,x,y),是无序的。,完全图,若有,n,个顶点的无向图有,n,(,n,-1)/2,条边,则此图为完全无向图。有,n,个顶点的有向图有,n,(,n-,1),条边,则此图为完全有向图。,0,0,0,0,1,1,1,1,2,2,2,2,6,5,4,3,3,邻接顶点,如果,(,u,v,),是,E,(G),中的一条边，则称,u,与,v,互为邻接顶点,。,子图,设有两个图,G(,V,E,),和,G(,V,E,)。,若,V,V,且,E,E,则称 图,G,是 图,G,的子图。,权,某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。,0,1,2,3,子图,0,1,3,0,1,2,3,0,2,3,顶点的度,一个顶点,v,的度是与它相关联的边的条数。记作,TD(,v,)。,在有向图中,顶点的度等于该顶点的入度与出度之和。,顶点,v,的入度,是以,v,为终点的有向边的条数,记作,ID(,v,),;,顶点,v,的出度,是以,v,为始点的有向边的条数,记作,OD(,v,),。,路径,在图,G(,V,E,),中,若从顶点,v,i,出发,沿一些边经过一些顶点,v,p,1,v,p,2,v,pm,，,到达顶点,v,j,。,则称顶点序列,(,v,i,v,p,1,v,p,2,.,v,pm,v,j,),为从顶点,v,i,到顶点,v,j,的路径,。它经过的边(,v,i,v,p,1,)、(,v,p,1,v,p,2,)、.、(,v,pm,v,j,),应是属于,E,的边。,路径长度,非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。,简单路径,若路径上各顶点,v,1,v,2,.,v,m,均不 互相重复,则称这样的路径为简单路径。,回路,若路径上第一个顶点,v,1,与最后一个顶点,v,m,重合,则称这样的路径为回路或环。,0,1,2,3,0,1,2,3,0,1,2,3,连通图与连通分量,在无向图中,若从顶点,v,1,到顶点,v,2,有路径,则称顶点,v,1,与,v,2,是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。,强连通图与强连通分量,在有向图中,若对于每一对顶点,v,i,和,v,j,都存在一条从,v,i,到,v,j,和从,v,j,到,v,i,的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,生成树,一个连通图的生成树是其极小连通子图，在,n,个顶点的情形下，有,n,-1,条边。,图的抽象数据类型,class Graph,public:,Graph(),;,void,InsertVertex,(,Type&,vertex),;,void,InsertEdge,(,int,v1,int,v2,int,weight),;,void,RemoveVertex,(,int,v),;,void,RemoveEdge,(,int,v1,int,v2),;,int,IsEmpty,(),;,Type,GetWeight,(,int,v1,int,v2),;,int,GetFirstNeighbor,(,int,v),;,int,GetNextNeighbor,(,int,v1,int,v2),;,图的存储表示,在图的邻接矩阵表示中，有一个记录各个顶点信息的,顶点表,，,还有一个表示各个顶点之间关系的,邻接矩阵,。,设图,A=(V,E),是一个有,n,个顶点的图,图的邻接矩阵是一个二维数组,A,.,edge,n,n,，,定义：,邻接矩阵,(,Adjacency Matrix),无向图的邻接矩阵是对称的;,有向图的邻接矩阵可能是不对称的。,0,1,2,3,0,1,2,在有向图中,统计第,i,行 1 的个数可得顶点,i,的,出度,，统计第,j,列 1 的个数可得顶点,j,的,入度,。,在无向图中,统计第,i,行(列)1 的个数可得顶点,i,的,度,。,网络的邻接矩阵,8,6,3,1,2,9,5,4,2,0,3,1,用邻接矩阵表示的图的类的定义,const,int MaxValue,=;,const,int,MaxEdges,=50,;,const,int,MaxVertices,=10,;,template,class,Graph,private:,Type,VerticesList,MaxVertices,;,float,Edge,MaxVertices,MaxVertices,;,int,numberEdges,;,int,numberVertices,;,int,GetVertexPos,(,const Type,vertex),for,(,int,i=0,;,i=0,&,i=,numberVertices,?,VerticesList,i,:,NULL,;,float,GetWeight,(,int,u,int,v),if,(u!=,-,1,&,v!=,-,1),return,Edgeuv,;,else return,0,;,int,GetFirstNeighbor,(,int,v),;,int,GetNextNeighbor,(,int,v,int,w),;,void,InsertVertex,(,const,Type,vertex),;,void,InsertEdge,(,int,u,int,v,float,weight),;,void,RemoveVertex,(,int,v),;,void,RemoveEdge,(,int,u,int,v),;,邻接矩阵实现的部分图操作,template,Graph,:,Graph(,int,sz,),/,构造函数,for,(,int,i=0,;,i,sz,;,i+),for,(,int,j=0,;,j,sz,;,j+)Edgeij=0,;,NumberEdges,=0,;,template,int,Graph,:,GetFirstNeighbor,(,const,int,v),/,给出顶点位置为,v,的第一个邻接顶点的位置,if,(v!=,-,1),for,(,int,j=0,;,j 0,&,Edgevj,MaxValue,),return,j,;,else return,-,1,;,template,int,Graph,:,GetNextNeighbor,(,int,v,int,w),/,给出顶点,v,的某邻接顶点,w,的下一个邻接顶点,if,(v!=,-,1,&,w!=,-,1),for,(,int,j=w+1,;,j 0,&,Edgevj,MaxValue,),return,j,;,return,-,1,;,邻接表(,Adjacency List),无向图的邻接表,同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边(边结点),结点中有另一顶点的下标,dest,和指针,link,。,A,B,C,D,data,adj,A,B,C,D,0,1,2,3,dest,link,dest,link,1,3,0,2,1,0,有向图的邻接表和逆邻接表,A,B,C,data,adj,A,B,C,0,1,2,dest,link,dest,link,邻接表(出边表),data,adj,A,B,C,0,1,2,dest,link,逆邻接表(入边表),1,0,2,0,1,1,网络(带权图)的邻接表,B,A,C,D,6,9,5,2,8,data,adj,A,B,C,D,0,1,2,3,dest,cost link,1,5,3,6,2,8,3,2,1,9,(出边表),(,顶点表),带权图的边结点中保存该边上的权值,cost,。,顶点,i,的边链表的表头指针,adj,在顶点表的下标为,i,的顶点记录中，该记录还保存了该顶点的其它信息。,在邻接表的边链表中，,各个边结点的链入顺序任意，视边结点输入次序而定。,设图中有,n,个顶点，,e,条边，则,用邻接表表示无向图时,，需要,n,个顶点结点，2,e,个边结点；用,邻接表表示有向图时,，若不考虑逆邻接表，只需,n,个顶点结点，,e,个边结点。,邻接表表示的图的类定义,#,define,DefaultSize,10,template class,Graph,;,template,struct,Edge,/,边结点,friend class,Graph,;,int,dest,;,/,目标顶点下标,float,cost,;,/,边上的权值,Edge*link,;,/,下一边链接指针,Edge(),/,构造函数,Edge(,int,D,float,C),:,dest,(D),cost(C),link(NULL),int,operator,!=(Edge,&,E),const return,dest,!=E.,dest,;,template,struct,Vertex,/,顶点,friend class,Graph,;,Type,data,;,/,顶点数据,Edge*,adj,;,/,边链表头指针,template class,Graph,/,图类,private:,Vertex,*,NodeTable,;,/,顶点表,int,numberVertices,;,/,当前顶点个数,int,MaxVertices,;,/,最大顶点个数,int,numberEdges,;,/,当前边数,int,GetVertexPos,(,const Type,vertex),;,public:,Graph(,int,sz,),;,Graph(),;,int,GraphEmpty,(),const,return,numberEdges,=0,;,int,GraphFull,(),const,return,numberVertices,=,MaxVertices,;,Type,GetValue,(,int,i),return,i=0,&,i,numberVertices,;,/,输入顶点个数,for,(,int,i=0,;,i name,;,InsertVertex,(name),;,/,输入各顶点信息,cin,e,;,/,输入边条数,for,(i=0,;,i tail head weight,;,k=,GetVertexPos,(tail),;,j=,GetVertexPos,(head),;,InsertEdge,(k,j,weight),;,/,插入边,template,Graph,:,Graph(),for,(,int,i=0,;,i,link,;,delete,p,;,p=,NodeTable,i.,adj,;,delete,NodeTable,;,/,释放顶点表,邻接表部分成员函数的实现,template,int,Graph,:,GetVertexPos,(,const Type,vertex),/,根据顶点名,vertex,查找它在邻接表中位置,for,(,int,i=0,;,i,dest,;,return,-,1,;,/,若顶点不存在,template,int,Graph,:,GetNextNeighbor,(,int,v,int,w),/,查找顶点,v,在邻接顶点,w,后下一个邻接顶点,if,(v!=,-,1),Edge,*p=,NodeTable,v.,adj,;,while,(p!=NULL),if,(p,-,dest,=,w,&,p,-,link!=NULL),return,p,-,link,-,dest,;,/,返回下一个邻接顶点在邻接表中位置,else,p=p,-,link,;,return,-,1,;,/,没有查到下一个邻接顶点,template float,Graph,:,GetWeight,(,int,u,int,v),if,(u!=,-,1,&,v!=,-,1),Edge,*p=,NodeTable,u.,adj,;,while,(p!=NULL),if,(p,-,dest,=v),return,p,-,cost,;,else,p=p,-,link,;,return,0,;,邻接多重表(,Adjacency,Multilist,),在邻接多重表中,每一条边只有一个边结点。为有关边的处理提供了方便。,无向图的情形,边结点的结构,mark vertex1 vertex2 path1 path2,其中,mark,是记录是否处理过的标记;,vertex1,和,vertex2,是该边两顶点位置。,path1,域是链接指针,指向下一条依附顶点,vertex1,的边；,path2,是指向下一条依附顶点,vertex2,的边链接指针。,顶点结点的结构,存储顶点信息的结点表,以顺序表方式组织,每一个顶点结点有两个数据成员：其中，,data,存放与该顶点相关的信息，,Firstout,是指示第一条依附该顶点的边的指针。在邻接多重表中,所有依附同一个顶点的边都链接在同一个单链表中。,data,Firstout,需要时还可设置一个存放与该边相关的权值的域,cost,。,邻接多重表的结构,mark vtx,1,vtx,2,path,1,path,2,0 1,0 2,1 3,e,1,e,2,e,3,data,Fout,A,B,C,D,0,1,2,3,e,1,e,2,e,3,A,B,C,D,从,顶点,i,出发,可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。,有向图的情形,在用邻接表表示有向图时,有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重表(十字链表)可把两个表结合起来表示。,边结点的结构,mark vertex1 vertex2 path1 path2,其中，,mark,是处理标记；,vertex1,和,vertex2,指明该有向边始顶点和终顶点的位置。,path1,是指向始顶点与该边相同的下一条边的指针；,path2,是指向终顶点与该边相同的下一条边的指针。需要时还可有权值域,cost,。,顶点结点的结构,每个顶点有一个结点，它相当于出边表和入边表的表头结点：其中，数据成员,data,存放与该顶点相关的信息，指针,Firstin,指示以该顶点为始顶点的出边表的第一条边，,Firstout,指示以该顶点为终顶点的入边表的第一条边。,data,Firstin Firstout,邻接多重表的结构,mark vtx,1,vtx,2,path,1,path,2,0 1,0 3,1 2,2 3,3 4,4 0,e,1,e,2,e,3,e,4,e,5,e,6,data Fin,Fout,A,B,C,D,E,0,1,2,3,4,e,1,e,2,e,3,e,4,e,5,e,6,A,B,C,D,E,图的遍历与连通性,从已给的连通图中某一顶点出发，沿着一 些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历(,Graph Traversal)。,图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组,visited ,。,辅助数组,visited ,的初始状态为 0,在图的遍历过程中,一旦某一个顶点,i,被访问,就立即让,visited i,为 1,防止它被多次访问。,图的遍历的分类:,深度优先搜索,DFS(Depth First Search),广度优先搜索,BFS(Breadth First Search),深度优先搜索,DFS,(Depth First Search),深度优先搜索的示例,A,C,D,E,G,B,F,I,H,A,C,D,E,G,B,F,I,H,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,前进,回退,深度优先搜索过程 深度优先生成树,DFS,在访问图中某一,起始顶点,v,后,由,v,出发,访问它的任一,邻接顶点,w,1,;,再从,w,1,出发,访问,与,w,1,邻,接,但还,没有访问过的顶点,w,2,;,然后再从,w,2,出发,进行类似的访问,如此进行下去,直至到达所有的邻接顶点都被访问过的顶点,u,为止,。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。,如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。,图的深度优先搜索算法,template,void,DFS(,Graph,&,G,),int,n=G.,NumberOfVertices,(),;,static,int,*visited=,new,int,n,;,for,(,int,i=0,;,i n,;,i+),/,访问数组,visited i=0,;,/,visited,初始化,DFS(G,0,visited),;,/,开始搜索,delete,visited,;,/,释放,visited,template,void,DFS(Graph,&,G,int,v,int,visited ),cout,G.,GetValue,(v),;,/,访问顶点,v,visitedv=1,;,/,顶点,v,作访问标记,int,w=G.,GetFirstNeighbor,(v),;,while,(w!=,-,1),/,若邻接顶点,w,存在,if,(!visitedw)DFS(G,w,visited),;,/,若,顶点,w,未访问过,递归访问顶点,w,w=G.,GetNextNeighbor,(v,w),;,/,取顶点,v,排在,w,后的下一个邻接顶点,广度优先搜索,BFS,(Breadth First Search,),广度优先搜索的示例,A,C,D,E,G,B,F,I,H,A,C,D,E,G,B,F,H,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,广度优先搜索过程 广度优先生成树,I,BFS,在访问了,起始顶点,v,之后,由,v,出发,依次访问,v,的各个,未被访问过的邻接顶点,w,1,w,2,w,t,然后再顺序访问,w,1,w,2,w,t,的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，如此做下去，直到图中所有顶点都被访问到为止。,广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程。,为了实现逐层访问,算法中使用了一个,队列,以记忆正在访问的这一层和上一层的顶点,以便于向下一层访问。,为避免重复访问,需要一个辅助数组,visited ,，,给被访问过的顶点加标记。,图的广度优先搜索算法,template,void,BFS(Graph,&,G,int,v),int,n=G.,NumberOfVertices,(),;,int,*,visited=,new,int,n,;,for,(,int,i=0,;,i n,;,i+)visitedi=0,;,cout,G.,GetValue,(v),;,visitedv=1,;,Queue q,;,q.,EnQueue,(v),;,/,进队列,while,(!q.,IsEmpty,(),/,队空搜索结束,q.,GetFront,(v),;,q.,DeQueue,(),;,int,w=G.,GetFirstNeighbor,(v),;,while,(w!=,-,1),/,若邻接顶点,w,存在,if,(!visitedw),/,未访问过,cout,G.,GetValue,(w),;,visitedw=1,;,q.,EnQueue,(w),;,w=G.,GetNextNeighbor,(v,w),;,/,重复检测,v,的所有邻接顶点,/,外层循环，判队列空否,delete,visited,;,连通分量(,Connected component),当无向图为非连通图时,从图中某一顶点出发,利用深度优先搜索算法或广度优先搜索算法,不可能遍历到图中的所有顶点,只能访问到该顶点所在的最大连通子图(连通分量)的所有顶点,。,若从无向图的每一个连通分量中的一个顶点出发进行遍历,可求得无向图的所有连通分量。,在算法中,需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。,对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林,。,A,C,D,E,I,B,F,O,G,H,J,N,M,L,K,非连通无向图,A,H,K,C,D,E,I,B,F,O,G,J,N,M,L,非连通图的连通分量,确定连通分量的算法,template,void,Components(,Graph,&,G),int,n=G.,NumberOfVertices,(),;,static,int,*visited=,new,int,n,;,for,(,int,i=0,;,i n,;,i+)visitedi=0,;,for,(i=0,;,i n,;,i+),if,(!visitedi),/,检测顶点是否访问过,DFS(G,i,visited),;,/,未访问,出发访问,OutputNewComponent,(),;,/,连通分量,【,例,】,以深度优先搜索方法从顶点 出发遍历图,建立深度优先生成森林。,A,B,C,D,E,F,G,A,A,B,D,E,C,F,G,有向图,深度优先生成森林,delete,visited,;,template,void,DFS_Forest,(,Graph,&,G,Tree,&,T),TreeNode,*,rt,*,subT,;,int,n=G.,NumberOfVertices,(),;,static,int,*visited=,new,int,n,;,/,访问数组,for,(,int,i=0,;,i n,;,i+)visited i=0,;,for,(i=0,;,i n,;,i+),/,遍历所有顶点,if,(!visitedi),/,顶点,i,未访问过,if,(T.,IsEmpty,(),/,原为空森林,建根,subT,=,rt,=T.,BuildRoot,(G.,GetValue,(i),;,/,顶点,i,的值成为根,rt,的值,else,subT,=T.,InsertRightSibling,(,subT,G.,GetValue,(i),;,/,顶点,i,的值成为,subT,右兄弟的值,DFS_Tree(G,T,subT,i,visited,),;,/,从顶点,i,出发深度优先遍历,建子树,template,void,DFS_Tree(,Graph,&,G,Tree,&,T,TreeNode,*,rt,int,v,int,visited ),TreeNode,*p,;,visitedv=1,;,/,顶点,v,作访问过标志,int,w=G.,GetFirstNeighbor,(v),;,/,取顶点,v,的第一个邻接顶点,w,int,FirstChild,=1,;,/,第一个未访问子女应是,v,的左子女,while,(w!=,-,1),/,邻接顶点,w,存在,if,(!visited w),/,w,未访问过,将成为,v,的子女,if,(,FirstChild,),p=T.,InsertLeftChild,(,rt,G.,GetValue,(w),;,/,p,插入为,rt,的左子女,FirstChild,=0,;,/,建右兄弟,else,p=T.,InsertRightSibling,(p,G.,GetValue,(w),),;,/,p,插入为,p,的左子女,DFS_Tree(G,T,p,w,visited,),;,/,递归建立,w,的以,p,为根的,子树,/,邻接顶点,w,处理完,w=G.,Get,Next,Neighbor,(v,w,),;,/,取,v,的下一个邻接顶点,w,/,回到,while,判邻接顶点,w,存在,重连通分量(,Biconnected,Component),在无向连通图,G,中,当且仅当删去,G,中的顶点,v,及,所有依附于,v,的所有边,后,可将图分割成两个或两个以上的连通分量，则称顶点,v,为,关节点,。,没有,关节点,的连通图叫做重连通图。,在重连通图上,任何一对顶点之间至少存在有两条路径,在删去某个顶点及与该顶点相关联的边时,也不破坏图的连通性。,一个连通图,G,如果不是重连通图，那么它可以包括几个重连通分量。,在一个无向连通图,G,中,重连通分量可以利用深度优先生成树找到,。,在图中各,顶点旁标明的深度优先数,给出进行深度优先搜索时各顶点访问的次序。,深度优先生成树的根是,关节点,的充要条件是,它至少有两个子女,。,其它顶点,u,是,关节点,的充要条件是,它至少有一个子女,w,从,w,出发,不能通过,w,、,w,的子孙及一条回边所组成的路径到达,u,的祖先,。,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,J,A,B,C,D,E,F,G,H,J,I,I,1,2,3,4,5,6,7,8,9,10,根有两 个子女,关节点,关节点,关节点,在图,G,的每一个顶点上定义一个,low,值，,lowu,是从,u,或,u,的子孙,出发通过,回边,可以到达的,最低深度优先数,。,lowu=min,dfn,u,min loww|w,是,u,的一个子女,min,dfn,x|(u,x),是一条回边,u,是关节点的充要条件是：,u,是具有两个以上子女的生成树的根,u,不是根，但它有一个子女,w，,使得,loww,dfn,u,这时,w,及其子孙不存在指向顶点,u,的祖先的回边。,计算,dfn,与,low,的算法(1),template,void,DfnLow,(,Graph,&,G,int,x),/,从顶点,x,开始深度优先搜索,int,num=1,;,/,num,是访问计数器,int,n=G.,NumberOfVertices,(),;,static,int,*,dfn,=,new,int,n,;,static,int,*low=,new,int,n,;,/,dfn,是深度优先数,low,是最小祖先访问顺序号,for,(,int,i=0,;,i 1,时输出重连通分量,（1）,template void,Biconnected,(Graph,&,G),/,从顶点,0,开始深度优先搜索,int,num=1,;,/,访问计数器,num,int,n=G.,NumberOfVertices,(),;,static,int,*,dfn,=,new,int,n,;,static,int,*low=,new,int,n,;,/,dfn,是深度优先数,low,是最小祖先号,for,(,int,i=0,;,i 1,时输出重连通分量（2）,template void,Biconnected,(Graph,&,G,int,u,int,v),/,计算,dfn,与,low,根据其重连通分量输出,Graph,的,/,边。在产生的生成树中,v,是,u,的双亲结点,S,是,/一个初始为空的栈,。,int,x,y,w,;,Stack,S,;,dfn,u=lowu=num+,;,w=G.,GetFirstNeighbor,(u),;,/,找顶点,u,的第一个邻接顶点,w,while,(w!=,-,1),if,(v!=w,&,dfn,w=,dfn,u),/,无回边,原来的重连通分量结束,cout,“,新重连通分量,:,”,end1;,do,S.Pop(x,y),;,cout,x ,y,endl,;,while,(,(x,y),与,(,u,w),不是同一条边,),;,/,输出该重连通分量的各边,else if,(w!=v,),/,有回边,计算,lowu=min2(lowu,dfn,w),;,/,根据回边另一顶点,w,调整,lowu,w=G.,GetNextNeighbor,(u,w),;,/,找顶点,u,的邻接顶点,w,的下一个邻接顶点,算法,Biconnected,的时间代价是,O(n+e),。,其中,n,是该连通图的顶点数，,e,是该连通图的边数。,此算法的前提条件是连通图中至少有两个顶点,因为正好有一个顶点的图连一条边也没有。,最小生成树(,minimum cost spanning tree),使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。,按照生成树的定义，,n,个顶点的连通网络的生成树有,n,个顶点、,n-1,条边。,构造最小生成树的准则,必须使用且仅使用该网络中的,n,-,1,条边来联结网络中的,n,个顶点；,不能使用产生回路的边；,各边上的权值的总和达到最小。,克鲁斯卡尔(,Kruskal,),算法,克鲁斯卡尔算法的基本思想：,设有一个有,n,个顶点的连通网络,N,=,V,E,最初先构造一个只有,n,个顶点,没有边的非连通图,T,=,V,图中每个顶点自成一个连通分量。当在,E,中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到,T,中,;否则将此边舍去，重新选择一条权值最小的边。,如此重复下去,直到所有顶点在同一个连通分量上为止。,算法的框架,利用,最小堆,(,MinHeap,),和,并查集,(,DisjointSets,),来实现,克鲁斯卡尔算法,。,首先,利用,最小堆,来存放,E,中的所有的边,堆中每个结点的格式为,在构造最小生成树过程中,利用,并查集,的运算检查依附一条边的两顶点,tail,、,head,是否在同一连通分量(即,并查集的同一个子集合,)上,是则舍去这条边；否则将此边加入,T,同时将这两个顶点放在同一个连通分量上。,tail head cost,边的两个顶点位置,边的权值,10,随着各边逐步加入到最小生成树的边集合中,各连通分量也在逐步合并,直到形成一个连通分量为止。,应用克鲁斯卡尔算法构造最小生成树的过程,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,5,0,4,6,1,3,2,5,0,4,6,1,3,2,原图,(,a)(b),10,12,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,5,0,4,6,1,3,2,5,0,4,6,1,3,2,10,14,12,原图,(,c)(d),5,0,4,6,1,3,2,10,14,16,12,(e)(f)(g),5,0,4,6,1,3,2,10,14,22,16,12,5,0,4,6,1,2,10,25,14,22,16,12,3,最小生成树类定义,class,MinSpanTree,;,class,MSTEdgeNode,/,生成树边结点类,friend class,MinSpanTree,;,private:,int,tail,head,;,/,生成树各边的两顶点,float,cost,;,/,生成树各边的权值,public:,MSTEdgeNode,(),/,构造函数,:,tail(,-,1),head(,-,1),cost(0),;,class,MinSpanTree,protected:,MSTEdgeNode,*,edgevalue,;,int,MaxSize,n,;,public:,MinSpanTree,(,int,sz,=,NumVertices,-,1),:,MaxSize,(,sz,),n(0),edgevalue,=,new,MSTEdgeNode,MaxSize,;,int,Insert(,MSTEdgeNode,&item),;,利用克鲁斯卡尔算法建立最小生成树,void,Kruskal,(Graph,&,G,MinSpanTree,&,T),MSTEdgeNode,ed,;,/,边结点辅助单元,int,n=G.,NumberOfVertices,(),;,/,顶点数,int,e=G.,NumberOfEdges,(),;,/,边数,MinHeap,H(e),;,/,最小堆,UFSets,F(n),;,/,并查集,for,(,int,u=0,;,u n,;,u+),for,(,int,v=u+1,;,v n,;,v+),if,(G.,GetWeight,(u,v)!=,MaxValue,),ed.tail=u,;,ed.head=v,;,/,插入堆,ed.cost=,GetWeight,(u,v),;,H.Insert(ed),;,int,count=1,;,/,最小生成树加入边数计数,while,(count n),H.,RemoveMin,(ed),;,/,从堆中退出一条边,u=F.Find(ed.tail),;,v=F.Find(ed.head),;,if,(u!=v),/,两端不在同一连通分量,F.Union(u,v),;,/,合并,T.Insert(ed),;,/,该边存入最小生成树,count,+;,出堆顺序,(0,5,10),选中,(2,3,12),选中,(1,6,14),选中,(1,2,16),选中,(3,6,18),舍弃,(3,4,22),选中,(4,6,24),舍弃,(4,5,25),选中,并查集,邻接矩阵表示,-2,-2,-2,-2,-,1,-,1,-,1,-,1,-,1,-,1,-,1,-,1,-,1,-,1,-,1,-,1,0,2,-,1,-,1,-,1,0,-2,2,0,0,0,0,0 1 2 3 4 5 6,-2,1,-,1,1,-2,-,1,-4,2,1,-2,-5,1,2,1,1,-7,1,1,2,1,1,F,0 1 2 3 4 5 6,0,28,10 ,0,28,0,16 14,1,16,0,12 ,2,12,0,22 18,3,22,0,25 24,4,10 25,0,5,14 18 24 ,0,6,普里姆(,Prim),算法,普里姆算法的基本思想：,从连通网络,N,=,V,E,中的某一顶点,u,0,出发,选择与它关联的具有最小权值的边,(,u,0,v,),将其顶点加入到,生成树顶点集合,U,中。,以后每一步从,一个顶点在,U,中,而,另一个顶点不在,U,中,的各条边中选择,权值最小的边,(,u,v,),把它的顶点加入到,集合,U,中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合,U,中为止。,采用邻接矩阵作为图的存储表示。,25,25,10,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,5,0,4,6,1,3,2,5,0,4,6,1,3,2,10,原图,(,a)(b),5,0,4,6,1,3,2,10,(c)(d)(e)(f),5,0,4,6,1,3,2,10,22,12,5,0,4,6,1,2,10,25,14,22,16,12,3,25,22,12,在构造过程中，还设置了两个辅助数组：,lowcost,存放,生成树顶点集合内顶点,到,生成树外各顶点,的各边上的当前最小权值；,nearvex,记录,生成树顶点集合外各顶点,距离,集合内哪个顶点,最近(即权值最小)。,例子,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,若选择从顶点0出发，即,u,0,=0，,则两个辅助数组的初始状态为：,然后反复做以下工作：