第15讲图的遍历

1EssentialofLectureFifteen

：

一、图的遍历（深度、广度）二、最小生成树三、普里姆算法四、克鲁斯卡尔算法第十五讲图的遍历难点2

图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。 在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。 为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个标识域tag作为对顶点的标记，当顶点vi未被访问，tag初始值为UNVISITED；当vi已被访问，则tag值为VISITED。

一、图的遍历TraversingGraph3图的遍历与树的遍历有什么不同？

有两种遍历方法（它们对无向图，有向图都适用）深度优先遍历Depth_FirstSearch

广度优先遍历Breadth_FirstSearch一、图的遍历4一、图的遍历算法：从图中某顶点v出发：（1）访问顶点v；

（2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历；1、深度优先遍历5深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5

V5一、图的遍历6深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5V8

V8一、图的遍历7深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5V8一、图的遍历8深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1

V7V2V4V5V8V3

V3V6

V6V7一、图的遍历9template<classElemType>voidDFSTraverse(constAdjMatrixDirGraph<ElemType>&g,void(*Visit)(constElemType&)){ intv; for(v=0;v<g.GetVexNum();v++) { g.SetTag(v,UNVISITED); } for(v=0;v<g.GetVexNum();v++) { if(g.GetTag(v)==UNVISITED) DFS<ElemType>(g,v,Visit); }}图的深度优先遍历算法10template<classElemType>voidDFS(constAdjMatrixDirGraph<ElemType>&g,intv,void(*Visit)(constElemType&)){ g.SetTag(v,VISITED); ElemTypee=g.GetVexData(v); Visit(e); for(intw=g.FirstAdjVex(v);w!=-1; w=g.NextAdjVex(v,w)) {if(g.GetTag(w)==UNVISITED) { DFS<ElemType>(g,w,Visit); } }}图的深度优先遍历算法11一、图的遍历

A

H

G

F

E

D

C

B图的深度优先遍历算法

01234567ABCDEFGH12673011045362523412算法分析图中有n个顶点，e条边。如果用邻接表表示图，沿adjLink链到next链可以找到某个顶点v的所有邻接顶点w。由于总共有2e个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。13考研题分析有向图的邻接表如下，要求（1）画出其邻接矩阵存储；（2）写出图的所有强连同分量；（3）写出顶点a到顶点i的全部简单路径；（4）写出以A为出发点开始深度优先遍历得到的顶点序列。

123456789ABEDHICGF27634528739614考研题分析已知一个有向图如下，则从顶点a出发进行深度优先遍历，不可能够得到的DFS序列为？AadbefcBadcefbCadcbfeDadefbcacefdb15一、图的遍历算法：从图中某未访问过的顶点vi出发：（1）访问顶点vi；（2）访问vi的所有未被访问的邻接点w1,w2,…wk

；（3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；2、广度优先遍历（类似于树的层次遍历）16为实现(3)，需要保存在步骤(2)中访问的顶点，而且访问这些顶点邻接点的顺序为：先保存的顶点，其邻接点先被访问。一、图的遍历2、广度优先遍历在广度优先遍历算法中，需设置一队列Q，保存已访问的顶点，并控制遍历顶点的顺序。

V1

V8

V7

V6

V5

V4

V3

V217广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V1一、图的遍历18广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V2V3V3一、图的遍历19广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V3V4V4V5V5一、图的遍历20广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V4V5V5V6V6V7V7一、图的遍历21广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V8一、图的遍历22template<classElemType>voidBFSTraverse(constAdjListDirGraph<ElemType>&g,void(*Visit)(constElemType&)){ intv; for(v=0;v<g.GetVexNum();v++) { g.SetTag(v,UNVISITED); } for(v=0;v<g.GetVexNum();v++) { if(g.GetTag(v)==UNVISITED) { BFS<ElemType>(g,v,Visit); } }}图的广度优先遍历算法23template<classElemType>voidBFS(constAdjListDirGraph<ElemType>&g,intv,void(*Visit)(constElemType&)){ g.SetTag(v,VISITED); ElemTypee; g.GetElem(v,e); Visit(e); LinkQueue<int>q; q.InQueue(v);

图的广度优先遍历算法24 while(!q.Empty()) { //队列q非空,进行循环 intu,w; q.OutQueue(u); for(w=g.FirstAdjVex(v);w>=0;w=g.NextAdjVex(v,w)) { if(g.GetTag(w)==UNVISITED) { g.SetTag(w,VISITED); g.GetElem(w,e); Visit(e); q.InQueue(w); } }}}图的广度优先遍历算法25

V0

V2

V3

V1

V5

V4

V0

V2

V3

V1

V5

V4深度优先遍历广度优先遍历两种遍历的比较一、图的遍历两者遍历的时间复杂度相同，不同之处仅仅在于对顶点访问的顺序。26二、图的连通性问题无向图的连通分量和生成树

生成树是一个连通图G的一个极小的连通子图。包含图G的所有顶点，但只有n-1条边，并且是连通的。生成树可由遍历过程中所经过的边组成。深度优先遍历得到的生成树称为深度优先生成树；广度优先遍历得到的生成树称为广度优先生成树。生成森林：非连通图每个连通分量的生成树一起组成非连通图的生成森林。27V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V828ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林例29二、图的连通性问题说明一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路

含n个顶点n-1条边的图不一定是生成树1、生成树和生成森林GHKI30

要在n个城市间建立交通网，要考虑的问题如何在保证n点连通的前题下最节省经费?V2V0V3V5V4

求解:连通6个城市且代价最小的交通线路?如何求连通图的最小生成树?？

若有一个连通的无向图G，有n个顶点，并且它的边是有权值的。在G上构造生成树G’,最小生成树是n-1条边的权值之和最小的G’

。二、图的连通性问题31①普里姆算法Prim②克鲁斯卡尔算法Kruskal二、图的连通性问题2、最小代价生成树MinimumCostSpanningTree32例1654328613688526131163151643152116432152616543215263①普里姆算法Prim33

普里姆算法基本步骤设N=（V，E）为一个具有n个顶点的带权的连通网络，T=（U，TE）为构造的生成树。

(1)初始时，U={U0}，TE={}；

(2)在所有u

U、v

V-U的边(u,v)E中选择一条权值最小的边(u0,v0)；

(3)(u0,v0)加入集合TE，同时将v0加入U；

(4)重复(2)、(3)，直到U=V为止；二、图的连通性问题34abcdegf195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=67再如：35template<classElemType,classWeightType>voidMiniSpanTreePrim(constAdjMatrixUndirNetwork<ElemType,WeightType>&net,intu0){ if(u0<0||u0>=net.GetVexNum())

throwError(“u0不合法1!”);

//抛出异常

int*adjVex;

intu,v,w;

adjVex=newint[net.GetVexNum()];

//分配存储空间

普鲁姆算法adjVex数组用于存储V-U中的顶点到U最小权值的边当vV-U时,adjVex[v]U,且<v,adjVex[v]>是v到U的最小权值边0123456adjVex数组36 for(v=0;v<net.GetVexNum();v++) {//初始化辅助数组adjVex，并对顶点作标志，此时U={u0} if(v!=u0) { //对于v∈V-U adjVex[v]=u0; net.SetTag(v,UNVISITED); } else { //对于v∈U net.SetTag(v,VISITED); adjVex[v]=u0; } }

普鲁姆算法37adjVex0123456net.tag000000010000001:VISITED0:UNVISITEDU0=038for(u=1;u<net.GetVexNum();u++){ w=MinVertex(net,adjVex); if(w==-1) return; cout<<"edge:("<<adjVex[w]<<","<<w<<")weight:"<<net.GetWeight(w,adjVex[w])<<endl; net.SetTag(w,VISITED);

for(intv=net.FirstAdjVex(w);v>=0;v=net.NextAdjVex(w,v)) { if(net.GetTag(v)==UNVISITED&& (net.GetWeight(v,w)<net.GetWeight(v,adjVex[v])|| net.GetWeight(v,adjVex[v])==0)) { adjVex[v]=w; } }}delete[]adjVex; //释放存储空间}39template<classElemType,classWeightType>intMinVertex(constAdjMatrixUndirNetwork<ElemType,WeightType>&net,int*adjVex) { intw=-1; intv; for(v=0;v<net.GetVexNum();v++) { //查找第一个满足条件的V-U中顶点v if(net.GetTag(v)==UNVISITED &&net.GetWeight(v,adjVex[v])>0) { w=v; break; } }

普鲁姆算法40for(v++;v<net.GetVexNum();v++) if(net.GetTag(v)==UNVISITED&&net.GetWeight(v,adjVex[v])>0&& net.GetWeight(v,adjVex[v])<net.GetWeight(w,adjVex[w])) w=v; returnw;}

普鲁姆算法41

克鲁斯卡尔算法二、图的连通性问题Kruskal的基本思想：设有一个有n个顶点的连通网络N={V,E},最初先构造一个只有n个顶点,没有边的非连通图T={V,

},图中每个顶点自成一个连通分量。在E中选到一条具有最小权值的边,若该边的两个顶点落在不同的连通分量上，则将此边加入到T中;否则将此边舍去，重新选择一条权值最小的边。如此重复下去,直到所有顶点在同一个连通分量上为止。42应用克鲁斯卡尔算法构造最小生成树的过程5046132281025142422161812原图二、图的连通性问题

克鲁斯卡尔算法5046132(a)105046132(b)43504612281025142422161812原图3(f)50461321014221612504613210141612(e)5046121025142216123(g)10125046132(c)5046132101412(d)441.初始化：U=V；TE={}；2.循环直到T中的连通分量个数为12.1在E中寻找最短边(u，v);2.2如果顶点u、v位于T的两个不同连通分量，则

2.2.1将边(u，v)并入TE；

2.2.2将这两个连通分量合为一个；

2.3在E中标记边(u，v)，使得(u，v)不参加后续最短边的选取；Kruskal算法——伪代码二、图的连通性问题作业:请编程用克鲁斯卡尔算法求最小生成树。45Prim与Kruskal算法的性能比较:

(1)时间复杂性:Prim:O(n*n)Kruskal:O(eloge)(2)适用场合:Prim:稠密图

Kruskal:稀疏图

二、图的连通性问题46【ACM】【ZOJ1406】最小生成树问题【问题描述】47如上图所示，给出结点数量N，以及每个结点到相邻结点的距离，要求给出一条最短连通路径，连通所有结点（结点的字