图的遍历和连通性课件

7.3图的遍历遍历：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。遍历实质：找每个顶点的邻接点的过程。图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。解决思路：可设置一个辅助数组

visited[n]，用来标记每个被访问过的顶点。它的初始状态为false，在图的遍历过程中，一旦某一个顶点i

被访问，就立即改visited[i]为true，防止它被重复访问。怎样避免重复访问？17.3图的遍历遍历：从已给的连通图中某一顶点出发，沿着一深度优先搜索和广度优先搜索图常用的遍历：一、深度优先搜索(DFS)Depth_FirstSearch基本思想：——类似于树的先根遍历过程。1、连通图的深度优先搜索遍历步骤：访问起始点v;依次从v的未被访问的邻接点出发深度优先遍历图直至图中所有和v有路径相通的顶点都被访问到。2深度优先搜索和广度优先搜索图常用的遍历：一、深度优先搜v1v1v2v3v8v7v6v4v5DFS结果：例1：→→→→→→→v2v4v8v5v3v6v7起点应退回到V8，因为V2已有标记voidDFS(GraphG,intv){//从顶点v出发，深度优先遍历Gvisited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);

//对v的尚未访问的邻接顶点w递归调用DFS}//DFS3v1v1v2v3v8v7v6v4v5DFS结果：例1：→→对于无向图，这个算法可以遍历到v顶点所在的连通分量中的所有顶点，而与v顶点不在一个连通分量中的所有顶点遍历不到；对于有向图可以遍历到起始顶点v能够到达的所有顶点。若希望遍历到图中的所有顶点，就需要在上述深度优先遍历算法的基础上，增加对每个顶点访问状态的检测。2、非连通图的深度优先搜索遍历步骤：访问起始点v及图中所有和v有路径相通的顶点。如果图中尚有顶点未被访问，则以该顶点为起始点，进行深度优先搜索遍历。重复上述过程，直至所有顶点都已被访问。4对于无向图，这个算法可以遍历到v顶点所在的连通分量中的所abchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg访问标志:访问次序:例2:0123456788123456705abchdekfgFFFFFvoid

DFSTraverse(GraphG,Status(*Visit)(intv)){

//对图G作深度优先遍历。

VisitFunc=Visit;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;

//访问标志数组初始化

for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);

//对尚未访问的顶点调用DFS}6voidDFSTraverse(GraphG,6DFS算法效率分析:（设图中有n个顶点，e条边）（1）如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。（2）如果用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。结论：稠密图适于在邻接矩阵上进行深度优先遍历；稀疏图适于在邻接表上进行深度优先遍历。7DFS算法效率分析:（设图中有n个顶点，e条边）结二、广度优先搜索(BFS)基本思想：——仿树的层次遍历过程。Breadth_FirstSearch在访问了起始点v之后，依次访问v的各个未曾访问过的邻接点；然后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。步骤：8二、广度优先搜索(BFS)基本思想：——仿树的层次遍历过v1v1v2v3v8v7v6v4v5BFS结果：例1：→→→→v2v3→v4v5→v6v7→v8v3→BFS结果：→

v4

→v5→起点起点v2→v1→v6v9→v8→v7例2：9v1v1v2v3v8v7v6v4v5BFS结果：例1：→→讨论：答:利用一个队列结构记录顶点访问顺序，将访问的每个顶点入队，然后，再依次出队，出队时访问其邻接点并将邻接点入队。（2）如何避免重复访问某个顶点？（1）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，应采用何种方式记录顶点访问顺序？答：创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来记录每个顶点是否已经被访问过。（3）广度优先搜索有回退的情况吗？10讨论：答:利用一个队列结构记录顶点访问顺序，将访问的每个顶点答：广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此广度优先搜索不是一个递归的过程，其算法也不是递归的。

void

BFSTraverse(GraphG,Status(*Visit)(intv)){for(v=0;v<G.vexnum;++v)visited[v]=FALSE;

//初始化访问标志

InitQueue(Q);

//置空的辅助队列Qfor(v=0;v<G.vexnum;++v)if(!visited[v]){//v尚未访问

…………}}//BFSTraverse11答：广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一visited[v]=TRUE;Visit(v);//访问vEnQueue(Q,v);

//v入队列while(!QueueEmpty(Q)){

DeQueue(Q,u);

//队头元素出队并置为ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE;Visit(w);

EnQueue(Q,w);

//访问的顶点w入队列

}//if}//while12visited[v]=TRUE;Visit(v);BFS算法效率分析:如果使用邻接表来表示图，则BFS循环的总时间代价为

d0+d1+…+dn-1=O(e)，其中的

di是顶点

i的度。如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（

n个元素），总的时间代价为O(n2)。（设图中有n个顶点，e条边）空间复杂度相同，都是O(n)(借用堆栈或队列装n个顶点）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。DFS与BFS之比较：13BFS算法效率分析:如果使用邻接表来表示图，则BFS循环的生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。（对有向或无向图均适用）思考1：若对连通图进行遍历，得到的是什么？一个极小连通子图，即图的生成树！由深度优先搜索得到的生成树，为深度优先生成树。由广度优先搜索得到的生成树，为广度优先生成树。思考2：若对非连通图进行遍历，得到的是什么？各连通分量的生成树，即图的生成森林！7.4图的连通性1.求无向图的生成树（或生成森林）14生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1例1：画出下图的生成树。DFS生成树v0v1v2v4v4v3邻接表01234^1334^142^0v4v3v2v1v023^142^0v0v2v1v4v3BFS生成树v0v1v3v2v4v0v1v2v4v4v3v0v1v2v4v4v315例1：画出下图的生成树。DFS生成树v0v1v2v4v4vDEABCFJLMGHIK例2：画出下图的生成森林（或极小连通子图）下面选用邻接表方式来求深度优先生成森林16DEABCFJLMGHIK例2：画出下图的生成森林（或极小连1155M12L11K10J9I8H7G6F5E4D3C2B1A012^^0^120^0^4^378^106^6^1011^126^709^1219^111^1229^47^10811DFS结果：ABMJLCFDEGHKI171155M12L11K10J9I8H7G6F5E4D3C2BDEGHIK子图1：子图2：子图3：AFCMLBJDEGHIKAFCMLBJ生成森林注：图的生成树（生成森林）不唯一！18DEGHIK子图1：子图2：子图3：AFCMLBJDEGHI2.求无向网的最小生成树目标：在网络的多个生成树中，寻找一个各边权值之和最小的生成树。即在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2条线路，那么，如何选择n–1条线路使总费用最少？典型用途：最小生成树（MST）的性质如下：V是顶点集，U是V的一个非空子集，若(u0,v0)是一条最小权值的边，其中u0

U，v0

V-U；则：(u0,v0)必在最小生成树上。192.求无向网的最小生成树目标：在网络的多个生成树中，寻找求MST有多种算法，但最常用的是以下两种：Prim（普里姆）算法Kruskal（克鲁斯卡尔）算法Prim算法特点:顶点归并，与边数无关，适于稠密网。Kruskal算法特点：边归并，适于求稀疏网。对边操作对顶点操作普里姆算法的基本思想:在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。如图所示：20求MST有多种算法，但最常用的是以下两种：Prim（普里姆）abcdegf例如:195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=67集合U集合V-Uu0v021abcdegf例如:195141827168213ae12d方法：设置一个辅助数组，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边。对每个属于V-U的顶点vi，在辅助数组中存在一个相应的分量closedge[i-1]，它包含两个域，其中lowcost存储该边上的权。显然，closedge[i-1].lowcost＝Min{cost(u,vi)|u€U}存储方式：struct{VertexTypeadjvex;//U集中的顶点序号

VRTypelowcost;//边的权值}closedge[MAX_VERTEX_NUM];22方法：设置一个辅助数组，对当前V－U集中的每个顶点，记录和顶abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd721