DBS第十章s图PPT课件

内容提要1、图的基本概念2、图的存储结构包括图的邻接矩阵表示和邻接表表示法及其实现3、图的遍历：深度优先和宽度优先遍历4、最小代价生成树：普里姆算法,.,1,10.1图的基本概念,与线性表、树和集合不同，在图结构中，每个数据元素都可以与任何其它数据元素相关。图在许多方面都有所应用。,课堂提要第10章图10.1图的基本概念10.2图的存储结构10.3图的遍历10.5最小代价生成树,.,2,(b)(a)的图表示,(a)电路示例,图10-1电路示例及对应的图表示,.,3,图(graph)：是数据结构G=(V,E)，其中V(G)是G中结点的有限非空集合,结点的偶对称为边(edge)；E(G)是G中边的有限集合。图中的结点又称为顶点(vertex)。,10.1.1图的定义与术语,1,0,2,3,4,(a)图G1,图中:V(G1)=0,1,2,3,4E(G1)=(0,1),(0,2),(0,4),(1,2),(2,3),(2,4),(3,4),.,4,有向图(directedgraph)：指图中代表边的偶对是有序的。用代表一条有向边（又称为弧），则u称为该边的始点（尾），v称为边的终点（头）。无向图(undirectedgraph)：指图中代表边的偶对是无序的在无向图中边(u，v)和(v，u)是同一条边。,1,0,2,3,4,(b)有向图G2,1,0,2,3,4,(a)无向图G1,.,5,1,0,2,3,4,1,0,2,3,4,(a)无向图G1,(b)有向图G2,图中V(G1)=V(G2)=0,1,2,3,4E(G1)=(0,1),(0,2),(0,4),(1,2),(2,3),(2,4),(3,4)E(G2)=,.,6,自回路：如果图中存在无向边(u,u)或有向边，则称这样的边为自回路。多重图：指图中两个顶点间允许有多条相同的边。,自回路和多重图的例子,.,7,邻接:如果(u,v)是无向图中的一条边，则称顶点u和v相邻接，并称边(u,v)与顶点u和v相关联。例如：顶点1和2是相邻接的。,完全图：如果一个图有最多的边数，称为完全图。无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边。例如：左图是一个完全图。有6条边。,无向完全图,如果是有向图中的一条边，则称顶点u邻接到v；称顶点v邻接自u,并称边与顶点u和v相关联。,.,8,子图：图G的一个子图是图G=(V,E)，其中V(G)V(G),E(G)E(G).,1,0,2,3,4,1,0,2,3,4,G1,G2,.,9,路径：在无向图G中，一条从s到t的路径是存在一个顶点序列(s,v1,v2,vk,t),使得(s,v1),(v1,v2),(vk,t)都是图G中的边。对于有向图顶点序列s,v1,v2,vk,t,应使,都是图G中的边。,路径长度:指路径上边的数目。,简单路径:除起点和终点可以相同外，路径上其余顶点各不相同。,回路:起点和终点相同的简单路径。,(0,1,2,3)；(0,1,2,3,4,2,0)；(0,1,2,3,4,0)都是路径，它们的路径长度分别为3,6,5。其中(0,1,2,3)和(0,1,2,3,4,0)是简单路径，(0,1,2,3,4,0)又是回路。,.,10,无向图中如果两个顶点u和v之间存在一条路径，则称顶点u和v是连通的，否则是不连通的。连通图:无向图中如果任意两个顶点之间是连通的。连通分量:无向图的极大连通子图。,0和3是连通的。实际上该图任意两个顶点都是连通的，故该图是连通图。,.,11,0和6是不连通的。该图是非连通图，但它存在两个连通分量。,注意极大的含义：如果某个连通子图再加上一个顶点后，仍然是连通的，则它不是连通分量。,3,.,12,强连通图：有向图中如果任意两个顶点u和v之间，存在一条从u到v的路径，同时存在一条从v到u的路径，则称该有向图为强连通图。强连通分量：有向图的极大强连通子图。,3,4,4,3,.,13,例如左图中，顶点1,2度分别为2和4。右图中，顶点0的入度和出度分别为3和1，顶点0的度为4,顶点2的入度和出度分别为？,顶点的度：与该顶点相关联的边的数目。入度：有向图中顶点v的入度指以v为头的弧的数目；出度：有向图中顶点v的出度指以v为尾的弧的数目。有向图中，顶点的度=入度+出度。,.,14,生成树：无向图的生成树是一个极小连通子图，它包含图中所有顶点，但只有足以构成一棵树的(n-1)条边。去掉一条就不连通，再加上一条边将构成回路。,有向图的生成森林：是一个子图，由若干棵互不相交的有根有向树组成，包含图中所有的顶点。,1,0,2,3,4,图G1的生成树,图G1,.,15,有根有向树：是一个有向图，它恰有一个顶点的入度为0，其余顶点的入度为1。如果略去边的方向，处理成无向图后，则图是连通的。,网：在图的每条边上加上一个数字称为权，也称代价,带权的图称为网。,有向无环图（DAG图）：不包含回路的有向图。自由树：不包含回路的连通图。,.,16,ADT101Graph数据：顶点的非空集合V和边的集合E，每条边由V中顶点的偶对表示。运算：voidCreateGraph(Graph*g,intn,Tnoedge)后置条件:已构造一个只有n个结点，不包含任何边的有向图。BOOLAdd(Graph*g,intu,intv,Tw)后置条件:向图中添加权值为w(若边上没有权，则w0)的边，若插入成功，则函数返回TRUE，否则返回FALSE。BOOLDelete(Graph*g,intu,intv)后置条件：从图中删除边，若删除成功，则函数返回TRUE，否则返回FALSE。BOOLExist(Graphg,intu,intv)后置条件：如果图中存在边，则函数返回TRUE，否则返回FALSE。intVerticesGraphg)后置条件：函数返回图中顶点数目。,.,17,上面列出的只是图的最基本的运算。在以后的各小节中，我们将通过添加新运算，陆续扩充ADT101的图抽象数据类型。主要包括以下图运算：(1)深度优先搜索图：voidDFS(Graphg)；(2)宽度优先搜索图：voidBFS(Graphg)；(3)拓扑排序：voidTopoSort(Graphg)；(4)关键路径：voidCriticalPath(Graphg)；(5)普里姆算法求最小代价生成树：voidPrim(Graphg，intk)；(6)克鲁斯卡尔算法求最小代价生成树：voidKruskal(Graphg，intedges)；(7)迪杰斯特拉算法求单源最短路径：voidDijkstra(Graphg，intk,Td,intp)；(8)弗洛伊德算法求所有顶点之间的最短路径：voidFloyd(Graphg，T*/两结点间无边时的值(0或)intVertices;/图中顶点数T*A;/指向存储邻接矩阵的二维数组的指针Graph;,.,24,建立邻接矩阵（【程序101】）。voidCreateGraph(Graph*g,intn,Tnoedge)inti,j;g-NoEdge=noedge;g-Vertices=n;g-A=(T*)malloc(n*sizeof(T*);for(i=0;iAi=(T*)malloc(n*sizeof(T);for(j=0;jAij=noedge;g-Aii=0;,a,L,O,M,M,O,L,L,0,0,0,0,noedge,noedge,noedge,noedge,noedge,noedge,.,25,BOOLExist(Graphg,intu,intv)if(un-1|vn-1|u=v|auv=noEdge)returnfalse;returntrue;,3、边的搜索、插入和删除,/判边是否存在,3,1是否有边？,1,3是否有边？,有边!,无边!,.,26,BOOLAdd(Graph*g,intu,intv,Tw)intn=g-Vertices;if(un-1|vn-1|u=v|g-Auv!=g-NoEdge)printf(BadInputn);returnFALSE;g-Auv=w;returnTRUE;,/边的插入,1,插入0,2边,.,27,/边的删除BOOLDelete(Graph*g,intu,intv)intn=g-Vertices;if(un-1|vn-1|u=v|g-Auv=g-NoEdge)printf(BadInputn);returnFALSE;g-Auv=g-NoEdge;returnTRUE;,1,删除0,2边,.,28,10.2.3邻接表表示法,要点：1、为图中每一个顶点建立一个单链表；2、顶点u的单链表中的每一个结点指示u的一个邻接点v，即代表一条边(u,v)或顶点u的单链表记录了与u相邻接(邻接自u)的所有顶点。每个单链表相当于邻接矩阵的一行,它指示了该行中的非零的元素。,0123,1,3,0,0,2,.,29,3、边结点的结构,指示顶点u的一个邻接点,指向u的下一个边结点,边上的权值,u,1,3,v,0,2,.,30,存放顶点的名称及其他信息,指向u的第一个边结点,u,1,3,v,0,2,4、每个单链表可设立一个存放顶点u的有关信息的表头结点，也称顶点结点。顶点结点存入一个一维数组。,.,31,0123,(a)图G1的邻接表,.,32,0123,1,3,0,0,2,(b)图G2的邻接表,.,33,typedefstructenodeintAdjVex;TW;structenode*NextArc;ENode;typedefstructgraphintVertices;ENode*A;Graph;,边结点的结构类型,图中的顶点数,.,34,3.建立邻接表函数CreateGraph构造一个有n个顶点，但不包含边的有向图。由于图的顶点数事先并不知道，所以我们使用动态存储分配的一维指针数组。,voidCreateGraph(Graph*g,intn)inti;g-Vertices=n;g-A=(ENode*)malloc(n*sizeof(ENode*);for(i=0;iAi=NULL;,.,35,搜索、插入或删除从顶点u发出的边，只在Au所指向的单链表中操作。程序如下：,3、边的搜索、插入和删除,3,2,0,1,2是否有边？,/搜索边的函数BOOLExist(Graphg,intu,intv)intn;ENode*p;n=g.Vertices;if(un-1)returnFALSE;for(p=g.Au;p,.,36,/插入边的函数BOOLAdd(Graph*g,intu,intv,Tw)intn;ENode*p;n=g-Vertices;if(un-1|vn-1|u=v|Exist(*g,u,v)printf(BadInputn);returnFALSE;p=NewENode(v,w,g-Au);g-Au=p;returnTRUE;,1,3,0,p,3,插入邻接表中由指针Au所指示的单链表的最前面,.,37,ENode*NewENode(intvex,Tweight,ENode*nextarc)ENode*p;p=(ENode*)malloc(sizeof(ENode);p-AdjVex=vex;p-W=weight;p-NextArc=nextarc;returnp;,.,38,/删除边的函数BOOLDelete(Graph*g,intu,intv)intn=g-Vertices;ENode*p,*q;if(u-1,0123,1,3,0,P,q=NULL,在由指针Au所指示的单链表中，搜索AdjVex域的值为v的边结点,.,39,10.3图的遍历,图的遍历:指从图G的任意一个顶点v出发，访问图中所有结点且每个结点仅访问一次的过程。,图遍历的方法:深度优先搜索（类似于树的先序遍历）和宽度优先搜索（类似于树的按层次遍历）,课堂提要第10章图10.1图的基本概念10.2图的存储结构10.3图的遍历10.5最小代价生成树,.,40,10.3.2深度优先遍历,图遍历与树遍历的差异:1、从图中任意一个顶点出发未必能到达其它所有顶点；2、图中存在回路时，又可能多次经过同一个顶点。为了避免发生上述两种情况，图的搜索算法通常为图的每个顶点保留一个标志位(markbit)。算法开始时，所有顶点的标志位清零。在遍历过程中，当某个顶点被访问时，其标志位被标记。在搜索中遇到被标记过的顶点则不再访问它。搜索结束后，如果还有未标记过的顶点，遍历算法可以选一个未标记的顶点，从它出发开始继续搜索。,.,41,1、深度优先搜索算法,从图G中某个顶点v出发,深度优先搜索图的DFS算法如下：1、访问顶点v并打上标记。2、依次从v的未访问过的邻接点出发，深度优先搜索图G.,.,42,从A出发,将访问走过的边保留，去掉访问时未走过的边，就得到以A为根的DFS生成树。,如果是连通的无向图或强连通的有向图，上述DFS算法必定可以系统地访问图中的全部顶点。,一条无向边被视作两条有向边，被查看两次。,.,43,(a)有向图G,B,F,D,E,A,C,G,对有向图G，从A出发DFS，访问的次序是A,B,D,C；遍历了所有从A出发可到达的顶点，即A的可达集。另选一个顶点出发搜索图G的其余部分。,(b)图G的邻接表,1,A,B,D,C,F,G,E,.,44,(a)有向图G,B,F,D,E,A,C,G,(c)图G深度优先搜索的生成森林,思考:图的DFS序列是否惟一？(指从同一顶点出发),A,B,D,C,F,G,E,图中所有顶点，以及在遍历时经过的边构成的子图，称为图的深度优先搜索生成树(dfsspanningtree)(或生成森林)。,.,45,DFS递归算法（【程序105】）。voidDFS(Graphg,intv,BOOL*visited)ENode*w;visitedv=TRUE;printf(%d,v);for(w=g.Av;w;w=w-NextArc)if(!visitedw-AdjVex)DFS(g,w-AdjVex,visited);voidTraversal_DFS(Graphg)BOOLvisitedMaxSize;inti,n=g.Vertices;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+)if(!visitedi)DFS(g,i,visited);,对V未标记的邻接点嵌套调用DFS函数,对尚未标记的顶点调用DFS函数,.,46,3、时间分析：深度优先搜索算法对有向图的每条边只查看1次，而对于无向图，查看2次。n个顶点、e条边的图采用邻接表存储，DFS算法的时间为O(n+e),而采用邻接矩阵表示，时间为O(n2)。,.,47,10.3.3宽度优先遍历,从图中任一顶点v出发遍历图的BFS算法的描述:1访问顶点v并打上标记;2依次访问顶点v的未访问的邻接点，再访问与这些邻接点相邻接且未访问的顶点。3若图中还有顶点未被访问，则另选一个未访问的顶点，重新开始上述过程。,1、宽度优先搜索,宽度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,.,48,6,2,7,0,9,8,3,5,4,10,1,11,(a)无向图G,例：对下图，从顶点0出发BFS遍历，其遍历序列是：0,1,11,10,2,5,6,9,3,4,7,8。,0,1,11,10,2,5,6,9,3,4,7,8,图中顶点以及遍历时生成的边所构成的子图称为宽度优先搜索生成树。,.,49,2,0,5,10,1,11,(a)无向图G,0,1,11,10,2,5,0,1,11,10,2,5,宽度优先搜索算法要实现按层次访问，需要一个队列来保存已访问过但其邻接点尚未考察的顶点。（1）访问顶点v的所有未访问过的邻接点时，需将这些邻接点保存在队列中。,（2）当顶点v的所有邻接点全部访问完毕后，从队列中取出一个顶点，接着访问这个顶点的邻接点，并依次进队列。,.,50,2、BFS算法,采用邻接表作为图的存储结构，其宽度优先搜索的程序如下：,#includequeue.hvoidBFS(Graphg,Tv,BOOL*visited)ENode*w;Tu;Queueq;CreateQueue(,入队,.,51,while(!IsEmpty(q)QueueFront(q,u的邻接顶点入队,.,52,voidTraversal_BFS(Graphg)BOOLvisitedMaxSize;inti,n=g.Vertices;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+)if(!visitedi)BFS(g,i,visited);,.,53,BFS算法的特点：1、每个顶点进出队列各一次。2、对于每个出队的顶点，都要检查其所有的邻接点，对于无向图每条边被检查2次。3、n个顶点，e条边的图采用邻接表存储，BFS算法的时间为O(n+e),而采用邻接矩阵表示，时间为O(n2)。如同二叉树的遍历算法，图的DFS和BFS算法是最重要、最基本的算法，许多有关图的算法都可以对它们稍加修改得到。例如，求无向图的连通分量、有向图的强连通分量、生成树(森林)等。,.,54,已知一有向图的邻接表存储结构如下图所示，请问：每个顶点的入度和出度，并给出从顶点1出发的深度优先遍历和宽度优先遍历序列。,1,01234,ABCDE,3,1,3,3,2,4,ABCDE,出度：,30202,ABCDE,入度：,02131,A,B,C,D,E,顶点1出发的深度优先遍历：,A,C,D,E,B,顶点1出发的宽度优先遍历：,A,C,B,D,E,.,55,10.4最小代价生成树,问题的引入：在n个城市之间架设通信线路。已知每两个城市间架设线路的代价，问如何选择n-1条线路，可以使总代价最小？,10.4.1基本概念,0,1,3,2,3,5,1,2,7,8,构造一个连通图的最小代价生成树。,.,56,一个连通图的生成树是：（1）一个极小连通子图（2）它包括图中全部顶点（3）有尽可能少的边，只有足以构成一棵树的n1条边。一棵生成树的代价是各条边上的代价之和。一个网络的生成树中具有最小代价的生成树称为该网络的最小代价生成树。,构造最小代价生成树的两种算法：普里姆算法（Prim)克鲁斯卡尔算法(Kruskal),.,57,0,1,3,2,3,5,1,2,7,8,.,58,设G=(V,E)是带权的连通图，T=(V,E)是正在构造中的生成树。初始状态下，这棵生成树只有一个顶点，没有边，即V=u0，E=，u0是任意选定的起始顶点。从初始状态开始，重复执行下列运算：在所有uV，vV-V的边(u,v)，(u,v)E中找一条代价最小的边(u,v)，边(u,v)并入集合E，将顶点v并入集合V。直到V=V为止。这时E中必有n-1条边，T=(V,E)是图G的一棵最小代价生成树。,1.普里姆算法（Prim),10.4.2普里姆算法,(u,v)的含义是：一端在树上，另一端不在树上的最小权值边,.,59,图10-15普里姆算法构造最小代价生成树的过程,0,3,1,2,4,5,3,6,6,6,5,5,5,4,2,1,图G,构造中的最小代价生成树T,普里姆算法演示,.,60,2.实现普里姆算法,为实现Prim算法,定义两个一维数组,用于存放中间构造过程和最终结果。nearestlowcost,设v是当前尚未选入生成树的顶点，nearestv中保存边(u,v)在生成树上的那个顶点u，边(u,v)是所有uV的边中权值最小的边。,u,v,u,1,0,3,8,7,6,5,5,V,nearestv,.,61,定义一个一维数组mark，用于表示某个顶点是否在生成树上。如果markv=false,表示v未加入生成树，反之，v已选入。初始时：nearestv=-1,lowcostv=MaxNum,markv=FALSE,(nearestv,v,lowcostv)代表一条权值为lowcostv，两个顶点分别为nearestv和v的一条边(nearestv,v)。如（2，1，5）:边(2,1)的代价为5，其中nearest1=2；lowcost1=5它记录当前对v而言，与生成树上顶点