第十九讲 图周游精选文档.ppt

《第十九讲 图周游精选文档.ppt》由会员分享，可在线阅读，更多相关《第十九讲 图周游精选文档.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十九第十九讲 图周游周游本讲稿第一页，共五十七页作业：堆排序作业：堆排序13468962Makeheap:2本讲稿第二页，共五十七页3本讲稿第三页，共五十七页4本讲稿第四页，共五十七页图的存储结构图的存储结构1 邻接矩阵表示法邻接矩阵表示法设图 G=(V,E)=(V,E)G=(V,E)=(V,E)是一个有 是一个有 n n个顶点的图,图的邻接矩阵是一个二维数组 edgennedgenn，定义：5本讲稿第五页，共五十七页vexs1=a,b,c,d;vexs2=v0,v1,v2,v3,v4假定不存在指向自身的弧6本讲稿第六页，共五十七页邻接矩阵表示法的特点邻接矩阵表示法的特点(1)无向图的关系矩

2、阵一定是一对称矩阵。(2)无向图的关系矩阵的第i行(或第i列)非零元素个数为第i个顶点的度D(vi)。(3)有向图的关系矩阵的第i行非零元素个数为第i个顶点的出度OD(vi)，第i列非零元素个数就是第i个顶点的入度ID(vi)。(4)从图的邻接矩阵表示，很容易确定图中任意两个顶点之间是否有边相连。添加或删除边也很方便。7本讲稿第七页，共五十七页如果G是带权的图，wij是边(vi,vj)或的权，则其关系矩阵定义为带权图的邻接矩阵表示带权图的邻接矩阵表示8本讲稿第八页，共五十七页邻接矩阵表示法结构定义邻接矩阵表示法结构定义typedefcharVexType;typedeffloatAdjType

3、;typedefstructintn;/*图的顶点个数*/VexType*vexs;/*顶点信息*/AdjType*arcs;/*边信息，二维数组*/GraphMatrix;9本讲稿第九页，共五十七页邻接表表示法邻接表表示法对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于该顶点Vi的边（或弧）10本讲稿第十页，共五十七页structEdgeNode;typedefstructEdgeNode*PEdgeNode;/edgeNode的指针typedefstructEdgeNode*EdgeList;/edgeNode链表指针structEdgeNodeintendvex;/*相邻顶点

4、在顶点表中下标*/AdjTypeweight;/*边的权，非带权图应该省略*/PEdgeNodenextedge;/*链字段*/;/*边表中的结点*/typedefstructVexTypevertex;/*顶点信息*/EdgeListedgelist;/*边表头指针*/VexNode;/*顶点表中的结点*/typedefstructintn;/*图的顶点个数*/VexNode*vexs;/*顶点表*/GraphList;/*图的邻接表表示*/邻接表表示法结构定义11本讲稿第十一页，共五十七页矩阵两种存储表示的空间开销比较矩阵两种存储表示的空间开销比较设图G有n个顶点，e条边.图的邻接矩阵表示

5、的空间代价为O(n2)；若图G是无向图，则图的邻接表表示的空间代价为O(n+2e)；若图G是有向图，则图的邻接表表示的空间代价为O(n+e);若图中eV2-V4-V8-V5-V3-V6-V7V1V2V3V4V5V8V6V719本讲稿第十九页，共五十七页20例子：已知无向图及其邻接表，求例子：已知无向图及其邻接表，求DFSDFS序列序列20本讲稿第二十页，共五十七页邻接表表示法的存储结构邻接表表示法的存储结构typedefstructVexTypevertex;/*顶点信息*/EdgeListedgelist;/*边表头指针*/VexNode;/*顶点表中的结点*/typedefstructin

6、tn;/*图的顶点个数*/VexNode*vexs;GraphList;int visitedn;21本讲稿第二十一页，共五十七页22第一步：首先访问顶点v0，将visited0置为TRUE，表示顶点v0已经被访问过由v0顶点表的edgelist字段，得到v0边表中的第一个边结点，取结点的相邻顶点信息，得知v0的第一个邻接点是v1，由于v1未被访问过，从v1出发进行深度优先搜索22本讲稿第二十二页，共五十七页第二步：访问顶点v1，将visited1置为TRUE，表示顶点v1已经被访问过，从v1边表中得知v1的第一个邻接点是v0，但v0已经被访问过由nextedge字段得到与v1相连的下一邻接点

7、是v3，由于v3未被访问过，则从v3出发进行深度优先搜索V0，V1，V323本讲稿第二十三页，共五十七页24第三步：访问顶点v3，将visited3置为TRUE，表示顶点v3已经被访问过。同第二步中方法一样，得知从v7出发再进行深度优先搜索第四步：访问顶点v7，同样方法依次访问顶点v4V0，V1，V3，V7，V424本讲稿第二十四页，共五十七页25第五步：访问顶点v4后，由于在v4的边表中得到的与v4相连的邻接点v1、v7都已被访问过，因而要退回到进入v4之前的v7；而顶点v7的所有邻接点也都被访问过，则继续退回到进入v7之前的顶点v3；同理，退回到顶点v1，再退回到顶点v0，v0的下一个邻接

8、点v2还未被访问过，因此从v2出发再进行深度优先搜索V0，V1，V3，V7，V4，V225本讲稿第二十五页，共五十七页26第六步访问顶点v2，同样方法，依次访问顶点v5、v6V0，V1，V3，V7，V4，V2，V5，V626本讲稿第二十六页，共五十七页27第七步访问完v6后，由于与v6相连的所有邻接点都被访问过，因此，退回到v5，同理退回到v2，再退回到v0，与v0相连的所有邻接点都被访问过，同时顶点v0又是出发点，因此，表明图中所有与顶点v0相通的顶点都已被访问过V0，V1，V3，V7，V4，V2，V5，V627本讲稿第二十七页，共五十七页28如果此时图中还存在未被访问过的顶点，则表明该图为

9、非连通图或非强连通图，则需要从未被访问过的顶点中再指定一个新的出发点，进行深度优先搜索所得DFS序列：v0，v1，v3，v7，v4，v2，v5，v628本讲稿第二十八页，共五十七页/*/*图的深度优先周游图的深度优先周游*/traverDFS(GraphList*pgraphlist);intvisitedMAXVEX;intn;n=pgraphlist-n;for(i=0;in;i+)visitedi=FALSE;/*初始化数组visited*/for(i=0;iV2-V3-V4-V5-V6-V7-V8访问过的结点需要特殊标志，避免回路。V1V2V3V4V5V8V6V734本讲稿第三十四页，

10、共五十七页广度优先广度优先算法的实现算法的实现voidbfs(Graphg,Vertexv)Vertexv1,v2;Queueq=createEmptyQueue();/*队列元素的类型为Vertex*/enQueue(q,v);while(!isEmptyQueue(q)v1=frontQueue(q);deQueue(q);/getanodefromqueuev1.mark=TRUE;/setstartfrommarkv2=firstAdjacent(g,v1);/getnodes,enQueuewhile(v2!=NULL)if(v2.mark=FALSE)enQueue(q,v2);v

11、2=nextAdjacent(g,v1,v2);35本讲稿第三十五页，共五十七页例子例子:已知无向图及其邻接表，求已知无向图及其邻接表，求BFSBFS序列序列36本讲稿第三十六页，共五十七页第一步：首先访问顶点v0，将v0入队，并标记visited0为TRUE，表明v0已被访问过第二步：队列pq不为空，其中第一个顶点v0出队从顶点v0的边表中搜索到两个邻接点v1和v2，顶点v1、v2都未被访问过，因此，依次访问v1、v2，将它们进队，并标记visited1和visited2为TRUEv0v1 v237本讲稿第三十七页，共五十七页38时间、空间复杂度时间、空间复杂度时间复杂度:算法bFSInMa

12、trix的时间复杂度为O(n2)算法bFSInList的时间复杂度为O(n+e)空间复杂度:两个算法的辅助空间主要是一个队列，大小不超过O(n)38本讲稿第三十八页，共五十七页广度优先周游算法广度优先周游算法1、每个顶点包含一个mark字段，在周游前所有顶点的mark字段均被置为FALSE，周游到该结点时将相应的mark字段改为TRUE。2、在bft中调用函数bfs(g,v)，从顶点v出发按广度优先周游g中能访问的各个顶点。具体实现中使用一个队列q，队列元素的类型为Vertex。39本讲稿第三十九页，共五十七页图的生成树图的生成树基本概念：针对对象-连通的无向图或强连通的有向图对于连通的无向图

13、，从任一顶点出发，可以访问到所有的顶点。周游时经过的边加上所有顶点构成了图的一个连通子图，称为图的一个生成树。它含有图中的全部n个顶点，但只有足以构成一棵树的n-1条边，是连通图的一个极小连通子图。40本讲稿第四十页，共五十七页生成树（支撑树）的概念生成树（支撑树）的概念GraphMatrixgraph=6,0,10,M,M,19,21,10,0,5,M,M,11,M,5,0,M,M,M,M,M,M,0,18,14,19,M,M,18,0,33,21,11,M,14,33,0;012345子图子图 +连通连通 +无环无环41本讲稿第四十一页，共五十七页无向图中无环的充要条件无向图中无环的充要条

14、件检查每一个连通分枝对于所有连通分枝：顶点数边的数目=1可以采用周游算法。算法复杂度：n01234542本讲稿第四十二页，共五十七页有向图判定无环的方法有向图判定无环的方法环中每个顶点入度、出度都不为0将入度、出度为0的顶点及关联边删除，如果还有顶点留下，则必有环。01234543本讲稿第四十三页，共五十七页最小生成树最小生成树 Minimum-cost Spanning Tree网络（带权图）的生成树中生成树各边的权值加起来称为生生成成树的权树的权，把权值最小的生成树称为最小生成树。最小生成树。(简称为MST)。等价与许多实际问题：如：在n个村庄的救援道路修复问题。44本讲稿第四十四页，共五

15、十七页构造生成树（构造生成树（例子）从无向图G7的顶点v0出发分别进行深度优先周游和广度优先周游，得到的DFS及BFS生成树右图所示。45本讲稿第四十五页，共五十七页最小生成树及其性质最小生成树及其性质网络（带权图）的生成树中生成树各边的权值加起来称为生生成成树树的的权权，把权值最小的生成树称为最最小小生生成成树树(MinimumSpanningTree，简称为MST)。等价与许多实际问题：在n个城市小区之间供水网络，如何在最节省经费的前提下建立这个供水网？其中小区以及供水厂之间的距离为权重。46本讲稿第四十六页，共五十七页设G=(V，E)是一个网络，U是顶点集合V的一个真子集。如果uU，vV

16、-U，且边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边，则一定存在G的一棵最小生成树包括此边(u,v)。MST性质性质47本讲稿第四十七页，共五十七页MST性质证明（反证法）性质证明（反证法）uuvvUV-Uvv边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边。假设：存在G的一棵最小生成树不包括此边。48本讲稿第四十八页，共五十七页Prim算法算法prim算法的基本思想是首先从集合V中任取一顶点(例如取顶点v0)放入集合U中这时U=v0，TE=NULL然后在所有一个顶点在集合U里，另一个顶点在集合V-U里的边中，找出权值最小的边(u,v

17、)(uU，vV-U)，将边加入TE，并将顶点v加入集合U重复上述操作直到U=V为止。这时TE中有n-1条边，T=(U，TE)就是G的一棵最小生成树49本讲稿第四十九页，共五十七页最小生成树的构造最小生成树的构造准备工作：设图采用邻接矩阵表示法表示，用一对顶点的下标(在顶点表中的下标)表示一条边，定义如下在构造最小生成树的过程中定义一个类型为Edge的数组mstEdgemstn-1;其中n为网络中顶点的个数，算法结束时，mst中存放求出的最小生成树的n-1条边。typedef structint start_vex,stop_vex;/*边的起点和终点*/AdjType weight;/*边的权

18、*/Edge;50本讲稿第五十页，共五十七页例子例子已知带权图G及其邻接矩阵如图所示请构造该图的最小生成树033141121330181914180666051165010211910051本讲稿第五十一页，共五十七页n=6，只有顶点v0在最小生成树中。mst5=0,1,10,0,2,0,3,0,4,19,0,5,21在mst0到mst4中找出权值最小的边mst0，即(v0,v1)，将顶点v1及边(v0,v1)加入最小生成树。03314112133018191418066605116501021191001n-152本讲稿第五十二页，共五十七页n=6，只有顶点v0在最小生成树中。mst5=0,

19、1,10,0,2,0,3,0,4,19,0,5,21在mst0到mst4中找出权值最小的边mst0，即(v0,v1)，将顶点v1及边(v0,v1)加入最小生成树。调整：mst5=0,1,10,1,2,5,1,3,6,0,4,19,1,5,1103314112133018191418066605116501021191002n-253本讲稿第五十三页，共五十七页mst5=0,1,10,1,2,5,1,3,6,3,4,18,1,5,11mst5=0,1,10,1,2,5,1,3,6,3,4,18,1,5,1103314112133018191418066605116501021191003n-354本讲稿第五十四页，共五十七页mst5=0,1,10,1,2,5,1,3,6,1,5,11,3,4,1855本讲稿第五十五页，共五十七页56Prim算法时间复杂度算法时间复杂度Prim算法的时间主要花费在选择最小生成树的n-1条边上。外循环执行n-1次，内循环两个，时间耗费为：整个算法的时间复杂度为O(n2)56本讲稿第五十六页，共五十七页作业：作业：上机布置。57本讲稿第五十七页，共五十七页