第十九讲 图周游

第十九讲图周游第一页，共五十七页，编辑于2023年，星期五作业：堆排序13468962Makeheap:2第二页，共五十七页，编辑于2023年，星期五3第三页，共五十七页，编辑于2023年，星期五4第四页，共五十七页，编辑于2023年，星期五图的存储结构1——邻接矩阵表示法设图G=(V,E)G=(V,E)是一个有是一个有n个顶点的图,图的邻接矩阵是一个二维数组edge[n][n]，定义：

5第五页，共五十七页，编辑于2023年，星期五vexs1[]={‘a’,‘b’,‘c’,‘d’};vexs2[]={v0,v1,v2,v3,v4}假定不存在指向自身的弧6第六页，共五十七页，编辑于2023年，星期五邻接矩阵表示法的特点(1)无向图的关系矩阵一定是一对称矩阵。

(2)无向图的关系矩阵的第i行(或第i列)非零元素个数为第i个顶点的度D(vi)。

(3)

有向图的关系矩阵的第i行非零元素个数为第i个顶点的出度OD(vi)，第i列非零元素个数就是第i个顶点的入度ID(vi)。

(4)从图的邻接矩阵表示，很容易确定图中任意两个顶点之间是否有边相连。添加或删除边也很方便。7第七页，共五十七页，编辑于2023年，星期五如果G是带权的图，wij是边(vi,vj)或<vi,vj>的权，则其关系矩阵定义为∶带权图的邻接矩阵表示8第八页，共五十七页，编辑于2023年，星期五邻接矩阵表示法结构定义typedefcharVexType;typedeffloatAdjType;typedefstruct{ intn; /*图的顶点个数*/VexType*vexs; /*顶点信息*/ AdjType*arcs[]; /*边信息，二维数组*/}GraphMatrix;9第九页，共五十七页，编辑于2023年，星期五邻接表表示法——对图中每个顶点建立一个单链表，

第i个单链表中的结点表示依附于该顶点Vi的边（或弧）10第十页，共五十七页，编辑于2023年，星期五structEdgeNode;typedefstructEdgeNode*PEdgeNode;//edgeNode的指针typedefstructEdgeNode*EdgeList;//edgeNode链表指针structEdgeNode{ intendvex; /*相邻顶点在顶点表中下标*/ AdjTypeweight; /*边的权，非带权图应该省略*/ PEdgeNodenextedge; /*链字段*/}; /*边表中的结点*/typedefstruct{ VexTypevertex; /*顶点信息*/ EdgeListedgelist; /*边表头指针*/}VexNode; /*顶点表中的结点*/typedefstruct{ intn; /*图的顶点个数*/ VexNode*vexs; /*顶点表*/}GraphList; /*图的邻接表表示*/邻接表表示法结构定义11第十一页，共五十七页，编辑于2023年，星期五矩阵两种存储表示的空间开销比较设图G有n个顶点，e条边.图的邻接矩阵表示的空间代价为O(n2)；若图G是无向图，则图的邻接表表示的空间代价为O(n+2e)；若图G是有向图，则图的邻接表表示的空间代价为O(n+e);若图中e<<n2，则用邻接表表示图比较节省空间，如果e达到n2数量级时，由于邻接表中增加了辅助的链域，采用邻接矩阵表示图更节省空间。特别对于无权图而言，关系矩阵的每个元素实际上只要一个二进制位就可以表示。

12第十二页，共五十七页，编辑于2023年，星期五ADTGraphisoperationsGraphcreateGraph(void)//创建一个空图intisNullGraph(Graphg)//判断图g是否空图VertexfirstVertex(Graphg)//找图中的一个顶点VertexnextVertex(Graphg,vi)//找图中顶点vi的下一个连通顶点VertexsearchVertex(Graphg,DataTypevalue)

//查找图中值为value的顶点GraphaddVertex(Graphg,DataTypevalue)

//在图g中增加一个值为value的顶点intfindEdge(Graphg,Vertexvi,Vertexvj)//返回顶点v相关联的第一条、下一条边。VertexfirstAdjacent(Graphg,Vertexv)/*v与返回顶点构成的边也称为与v相关联的第一条边。*/找图g中与vi相邻的，相对相邻顶点vj的，下一个相邻顶点VertexnextAdjacent(Graphg,Vertexvi,Vertexvj)/*vi与返回值构成的边也称为是vi与vj构成的边的下一条边。*/图的操作与抽象数据类型…13第十三页，共五十七页，编辑于2023年，星期五基于抽象数据类型的图的周游算法图的周游是一种按某种方式系统地访问图中的所有结点的过程，它使每个结点都被且只被访问一次。图的周游也称图的遍历。若图是连通（无向）图或强连通（有向）图，则从图中任意一顶点出发，都可以延某一路径找到图中所有顶点。否则就不然。深度优先：类似于二叉树的深度优先。广度优先：类似于二叉树的广度优先。14第十四页，共五十七页，编辑于2023年，星期五深度优先周游先访问图中某个（未访问过的）结点V，然后选择一个V邻接到的未被访问过的结点W，再访问W，并按同样方法前进；当遇到一个所有邻接于它的结点都被访问过了的结点时，退回到已访问结点序列中最后—个拥有相邻结点未被访问过的结点，访问它的一个未被访问过的相邻结点U，再从U出发按同样方法前进。当所有已被访问过的结点的相邻结点都被访问时，如果图中还有未被访问的顶点，则从另一未被访问过的顶点出发重复上述过程，直到图中所有顶点都被访问过时，周游结束。。15第十五页，共五十七页，编辑于2023年，星期五深度优先周游算法从顶点v0出发进行深度优先周游，得到的一个DFS序列为∶

v0，v1，v3，v7，v4，v2，v5，v6intmarked[8];16第十六页，共五十七页，编辑于2023年，星期五深度优先周游算法需要对已访问的顶点作标记。在顶点中增设一个标记字段mark。需要用到栈结构或采用递归算法。从一个顶点出发的搜索不一定能够访问到图中所有顶点。17第十七页，共五十七页，编辑于2023年，星期五从节点v出发，dfs（g,v）voiddfs(Graphg,Vertexv){Vertexv1;v.mark=TRUE;//标记字段mark for(v1=firstAdjacent(g,v);v1!=NULL;v1=nextAdjacent(g,v,v1)) dfs(g,v1);/*递归调用*/}voiddft(Graphg){Vertexv;for(v=firstVertex(g);v!=NULL;v=nextVertex(g,v)) if(v.mark==FALSE)dfs(g,v);//尝试所有结点，图g不一定连通}18第十八页，共五十七页，编辑于2023年，星期五深度优先搜索序列对图进行深度优先周游时，按访问顶点的先后次序所得到的顶点序列，称为该图的深度优先搜索序列，简称DFS序列。V1出发深度优先：V1->V2->V4->V8->V5->V3->V6->V7V1V2V3V4V5V8V6V719第十九页，共五十七页，编辑于2023年，星期五20例子：已知无向图及其邻接表，求DFS序列20第二十页，共五十七页，编辑于2023年，星期五邻接表表示法的存储结构

typedefstruct{ VexTypevertex; /*顶点信息*/ EdgeListedgelist; /*边表头指针*/}VexNode; /*顶点表中的结点*/typedefstruct{ intn; /*图的顶点个数*/VexNode*vexs;}GraphList;intvisited[n];21第二十一页，共五十七页，编辑于2023年，星期五22第一步：首先访问顶点v0，将visited[0]置为TRUE，表示顶点v0已经被访问过由v0顶点表的edgelist字段，得到v0边表中的第一个边结点，取结点的相邻顶点信息，得知v0的第一个邻接点是v1，由于v1未被访问过，从v1出发进行深度优先搜索22第二十二页，共五十七页，编辑于2023年，星期五第二步： 访问顶点v1，将visited[1]置为TRUE，表示顶点v1已经被访问过，从v1边表中得知v1的第一个邻接点是v0，但v0已经被访问过由nextedge字段得到与v1相连的下一邻接点是v3，由于v3未被访问过，则从v3出发进行深度优先搜索V0，V1，V323第二十三页，共五十七页，编辑于2023年，星期五24第三步： 访问顶点v3，将visited[3]置为TRUE，表示顶点v3已经被访问过。同第二步中方法一样，得知从v7出发再进行深度优先搜索第四步： 访问顶点v7，同样方法依次访问顶点v4V0，V1，V3

，V7

，V424第二十四页，共五十七页，编辑于2023年，星期五25第五步：访问顶点v4后，由于在v4的边表中得到的与v4相连的邻接点v1、v7都已被访问过，因而要退回到进入v4之前的v7；而顶点v7的所有邻接点也都被访问过，则继续退回到进入v7之前的顶点v3；同理，退回到顶点v1，再退回到顶点v0，v0的下一个邻接点v2还未被访问过，因此从v2出发再进行深度优先搜索V0，V1，V3

，V7

，V4

，V225第二十五页，共五十七页，编辑于2023年，星期五26第六步 访问顶点v2，同样方法，依次访问顶点v5、v6V0，V1，V3

，V7

，V4

，V2，V5，V626第二十六页，共五十七页，编辑于2023年，星期五27第七步访问完v6后，由于与v6相连的所有邻接点都被访问过，因此，退回到v5，同理退回到v2，再退回到v0，与v0相连的所有邻接点都被访问过，同时顶点v0又是出发点，因此，表明图中所有与顶点v0相通的顶点都已被访问过V0，V1，V3

，V7

，V4

，V2，V5，V627第二十七页，共五十七页，编辑于2023年，星期五28如果此时图中还存在未被访问过的顶点，则表明该图为非连通图或非强连通图，则需要从未被访问过的顶点中再指定一个新的出发点，进行深度优先搜索所得DFS序列：

v0，v1，v3，v7，v4，v2，v5，v628第二十八页，共五十七页，编辑于2023年，星期五/*图的深度优先周游*/traverDFS(GraphList*pgraphlist);{

intvisited[MAXVEX]; intn; n=pgraphlist->n; for(i=0;i<n;i++) visited[i]=FALSE;/*初始化数组visited*/ for(i=0;i<n;i++) if(visited[i]==FALSE) dFSInList(pgraphlist,visited,i); }说明:设图有n个顶点，e条边，若图是连通图，则只需调用dFSInList一次，就可完成图的深度优先周游；否则调用几次则表明图中有几个连通分量29第二十九页，共五十七页，编辑于2023年，星期五算法的时间、空间复杂度时间复杂度：采用邻接矩阵表示－O(n2)

得到一个顶点的所有邻接点需要检查矩阵相应行中的n个元素采用邻接表表示－O(n+e)

检查一个顶点的所有邻接点是对其边表中边结点扫描一遍空间复杂度：算法所用的辅助空间都是标志数组及实现递归所用的栈，算法的辅助空间为O(n)30第三十页，共五十七页，编辑于2023年，星期五广度优先周游广度优先周游的策略又称为广度优先搜索（Breadth_FirstSearch）具体的思想：从图的指定顶点v出发，先访问顶点v，并将其标记为已访问过接着依次访问v的所有邻接点w1，w2，…，wx然后，再依次访问与w1，w2，…，wx邻接的所有未被访问过的顶点以此类推，直到所有已访问顶点的邻接点都被访问过为止如果图中还有未被访问过的顶点，则从另一未被访问过的顶点出发进行广度优先搜索，直到所有顶点都被访问过为止31第三十一页，共五十七页，编辑于2023年，星期五广度优先周游算法从顶点v0出发的一个BFS序列为∶v0,v1,v2,v3,v4,v5,v6,v7queue32第三十二页，共五十七页，编辑于2023年，星期五广度优先搜索算法对于广度优先周游，关键在于怎么保证“先被访问的顶点的邻接点”要先于“后被访问的顶点的邻接点”被访问(队列控制）。设立一个队列pq，将访问过的顶点依次进队列，按顶点进队列先后顺序访问它们的邻接点。33第三十三页，共五十七页，编辑于2023年，星期五广度优先搜索序列广度优先周游得到的顶点序列称为广度优先搜索序列，简称BFS序列V1出发广度优先：V1->V2->V3->V4->V5->V6->V7->V8访问过的结点需要特殊标志，避免回路。V1V2V3V4V5V8V6V734第三十四页，共五十七页，编辑于2023年，星期五广度优先算法的实现voidbfs(Graphg,Vertexv){ Vertexv1,v2; Queueq=createEmptyQueue(); /*队列元素的类型为Vertex*/ enQueue(q,v); while(!isEmptyQueue(q)){ v1=frontQueue(q);deQueue(q);//getanodefromqueue v1.mark=TRUE;//setstartfrommarkv2=firstAdjacent(g,v1);//getnodes,enQueue while(v2!=NULL){ if(v2.mark==FALSE)enQueue(q,v2); v2=nextAdjacent(g,v1,v2); } }}35第三十五页，共五十七页，编辑于2023年，星期五例子:已知无向图及其邻接表，求BFS序列36第三十六页，共五十七页，编辑于2023年，星期五第一步： 首先访问顶点v0，将v0入队，并标记visited[0]为TRUE，表明v0已被访问过第二步： 队列pq不为空，其中第一个顶点v0出队 从顶点v0的边表中搜索到两个邻接点v1和v2，顶点v1、v2都未被访问过，因此，依次访问v1、v2，将它们进队，并标记visited[1]和visited[2]为TRUEv0v1v237第三十七页，共五十七页，编辑于2023年，星期五38时间、空间复杂度时间复杂度:

算法bFSInMatrix的时间复杂度为O(n2)

算法bFSInList的时间复杂度为O(n+e)空间复杂度:

两个算法的辅助空间主要是一个队列，大小不超过O(n)38第三十八页，共五十七页，编辑于2023年，星期五广度优先周游算法1、每个顶点包含一个mark字段，在周游前所有顶点的mark字段均被置为FALSE，周游到该结点时将相应的mark字段改为TRUE。 2、在bft中调用函数bfs(g,v)，从顶点v出发按广度优先周游g中能访问的各个顶点。具体实现中使用一个队列q，队列元素的类型为Vertex。39第三十九页，共五十七页，编辑于2023年，星期五图的生成树基本概念：针对对象-连通的无向图或强连通的有向图对于连通的无向图，从任一顶点出发，可以访问到所有的顶点。周游时经过的边加上所有顶点构成了图的一个连通子图，称为图的一个生成树。它含有图中的全部n个顶点，但只有足以构成一棵树的n-1条边，是连通图的一个极小连通子图。40第四十页，共五十七页，编辑于2023年，星期五生成树（支撑树）的概念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} }};

0

1

2

3

4

5子图+连通+无环41第四十一页，共五十七页，编辑于2023年，星期五无向图中无环的充要条件检查每一个连通分枝对于所有连通分枝：顶点数–边的数目=1可以采用周游算法。算法复杂度：n

0

1

2

3

4

542第四十二页，共五十七页，编辑于2023年，星期五有向图判定无环的方法环中每个顶点入度、出度都不为0将入度、出度为0的顶点及关联边删除，如果还有顶点留下，则必有环。

0

1

2

3

4

543第四十三页，共五十七页，编辑于2023年，星期五最小生成树Minimum-costSpanningTree网络（带权图）的生成树中生成树各边的权值加起来称为生成树的权，把权值最小的生成树称为最小生成树。(简称为MST)。等价与许多实际问题：如：在n个村庄的救援道路修复问题。

44第四十四页，共五十七页，编辑于2023年，星期五构造生成树（例子）从无向图G7的顶点v0出发分别进行深度优先周游和广度优先周游，得到的DFS及BFS生成树右图所示。

45第四十五页，共五十七页，编辑于2023年，星期五最小生成树及其性质网络（带权图）的生成树中生成树各边的权值加起来称为生成树的权，把权值最小的生成树称为最小生成树(MinimumSpanningTree，简称为MST)。等价与许多实际问题：

在n个城市小区之间供水网络，如何在最节省经费的前提下建立这个供水网？其中小区以及供水厂之间的距离为权重。46第四十六页，共五十七页，编辑于2023年，星期五设G=(V，E)是一个网络，U是顶点集合V的一个真子集。如果u∈U，v∈V-U，且边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边，则一定存在G的一棵最小生成树包括此边(u,v)。MST性质47第四十七页，共五十七页，编辑于2023年，星期五MST性质证明（反证法）uu´vv´UV-Uvv边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边。假设：存在G的一棵最小生成树不包括此边。48第四十八页，共五十七页，编辑于2023年，星期五Prim算法prim算法的基本思想是∶首先从集合V中任取一顶点(例如取顶点v0)放入集合U中这时U={v0}，TE=NULL然后在所有一个顶点在集合U里，另一个顶点在集合V-U里的边中，找出权值最小的边(u,v)(u∈U，v∈V-U)，将边加入TE，并将顶点v加入集合U重复上述操作直到U=V为止。这时TE中有n-1条边，T=(U，TE)就是G的一棵最小生成树49第四十九页，共五十七页，编辑于2023年，星期五最小生成树的构造准备工作： 设图采用邻接矩阵表示法表示，用一对顶点的下标(在顶点表中的下标)表示一条边，定义如下∶在构造最小生成树的过程中定义一个类型为Edge的数组mst∶Edgemst[n-1];其中n为网络中顶点的个数，算法结束时，mst中存放求出的最小生成树的n-1条边。typedefstruct{ intstart_vex,stop_vex;/*边的起点和终点*/ AdjTypeweight; /*边的权*/}Edge;50第五十页，共五十七页，编辑于2023年，星期五例子已知带权图G及其邻接矩阵如图所示请构造该图的最小生成树úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥033141121330181914180666051165010211910051第五十一页，共五十七页，编辑于2023年，星期五n=6，只有顶点v0在最小生成树中。

mst[5]={{0,1,10},{0,2,∞},{0,3,∞},{0,4,19},{0,5,21}}在mst[0]