1掌握图的两种遍历算法:深度优先搜索和广度优先搜索算...
第五章 图
第十七讲 图的遍历
1(掌握图的两种遍历算法:深度优先搜索和广度优先搜索算法，
2(求解连通性问题的方法。
, 教学重点:
图的两种遍历算法:深度优先搜索和广度优先搜索算法
, 教学难点:
图的两种遍历算法:深度优先搜索和广度优先搜索算法
, 授课
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
5.3 图的遍历
和树的遍历类似，在此，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做图的遍历(TraversingGraph)。图的遍历算法是求解图 的连通性问题、拓扑排序和求关键路径等算法的基础。
然而，图的遍历要比树的遍历复杂得多。因为图的任一顶点都可能和其余的顶点相邻接。所以在访问了某个顶点之后，可能沿着某条路径搜索之后，又回到该顶点上。[例如]图7.1(b)中的G2，由于图中存在回路，因此在访问了v1,v2,v3,v4之后，沿着边(v4 , v1)又可访问到v1。为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。为此，我们可以设一个辅助数组visited[0..n-1]，它的初始值置为“假”或者零，一旦访问了顶点vi，便置visited[i]为“真”或者为被访问时的次序号。
通常有两条遍历图的路径:深度优先搜索和广度优先搜索。它们对无向图和有向图都适用。
5.3.1 深度优先搜索
深度优先搜索(Depth-First Search)遍历类似于树的先根遍历，是树的先根遍历的推广。
其基本思想如下:假定以图中某个顶点vi为出发点，首先访问出发点，然后选择一个vi的未访问过的邻接点vj，以vj为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。显然，这是一个递归的搜索过程。
第五章 图
现以图5-3-1中G为例说明深度优先搜索过程。假定v0是出发点，首先访问v0。因v0有两个邻接点v1、v2均末被访问过，可以选择v1作为新的出发点，访问v1之后，再找v1的末访问过的邻接点。同v1邻接的有v0、v3和v4，其中v0已被访问过，而v3、v4尚未被访问过，可以选择v3作为新的出发点。重复上述搜索过程，继续依次访问v7、v4 。访问v4之后，由于与v4相邻的顶点均已被访问过，搜索退回到v7。由于v7、v3和v1都是没有末被访问的邻接点，所以搜索过程连续地从v7退回到v3，再退回v1，最后退回到v0。这时再选择v0的末被访问过的邻接点v2，继续往下搜索，依次访问v2、v5和v6，止此图中全部顶点均被访问过。遍历过程见图5-3-1(b)，得到的顶点的访问序列为:v0 ? v1 ? v3 ? v7 ? v4 ? v2 ? v5 ? v7。
(a)无向图G (b) G的深度优先搜索过程
图5-3-1 深度优先搜索遍历过程示例
因为深度优先搜索遍历是递归定义的，故容易写出其递归算法。下面的算法5.3是以邻接矩阵作为图的存储结构下的深度优先搜索遍历算法;算法5.4是以邻接
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
作为图的存储结构下的深度优先搜索遍历算法。
算法5.3
int visited[NAX_VEX]={0};
void Dfs_m( Mgraph *G,int i){
/* 从第i个顶点出发深度优先遍历图G，G以邻接矩阵表示*/
printf("%3c",G->vexs[i]);
visited[i]=1;
for (j=0;j
arcs[i][j]==1)&& (!visited[j])) Dfs_m(G,j);
} /*Dfs_m */
算法5.4
int visited[VEX_NUM]={0};
void Dfs_L(ALgraph G,int i){
/* 从第i个顶点出发深度优先遍历图G，G以邻接表表示 */
printf("%3c",G[i].data);
visited[i]=1;
p=G[i].firstarc;
while (p!=NULL)
{ if(visited[p->adjvex]==0)
第五章 图
Dfs_L(G,p->adjvex);
p=p->nextarc;
}
} /*dfs_L*/
分析上述算法得知，遍历图的过程实质上是对每个顶点搜索其邻接点的过程。其耗费的时间取决于所采用的存储结构。假设图有>n个顶点，那么，当用邻接矩阵表示图时，搜索一个顶点的所有邻接点需花费的时间为>O(n)，则从>n个顶点出发搜索的时间应为>O(n2)，所以算法>5.1的时间复杂度是>O(n2);如果使用邻接表来表示图时，需花费时间为>O(n+e)， 其中>e为无向图中边的数目或有向图中弧的数目。算法>5.4的时间复杂度为>O(n+e)。
5.3.2 广度优先搜索
连通图的广度优先搜索(Breadth_FirstSearch)遍历图类似于树的按层次遍历。其基本思想是:首先访问图中某指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、 Vk„„，并均标记为已访问过，然后再按照Vj、Vk„„的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止。
在广度优先搜索中，若对顶点V1的访问先于顶点V2的访问，则对V1邻接顶点的访问也先于V2邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。
[例如]，下面以图5-3-1种G为例说明广度优先搜索的过程。假设从起点v0出发，那么首先访问vo和行动两个未访问的邻接点v1和v2;然后依次访问v1的邻接点v3和v4以及v2的邻接点v5和v6;最后访问v3的未曾访问的邻接点v7。此图中所有顶点均已被访问过，由此完成了图的遍历。遍历过程见图5-3-2，得到的顶点访问序列为:
v0?v1?v2?v3?v4?v5?v6?v7
在广度优先搜索中，若顶点v在顶点u之前访问，则v的邻接点也将在u的邻接点之前访问。由此，可采用对列qu来暂存那些刚访问过并且可能还有未访问的邻接点的顶点。
v0
V1V2
V3 V4V5V6
V7
图5,3,2 广度优先搜索遍历过程 算法5.5
int visited[VEX_NUM]={0};
void Bfs(Mgraph G,int k){
int qu[20],f=0,r=0;
第五章 图
printf(“%3c”,G.vexs[k]);
visited[k]=1;
r++;qu[r]=k;
while (r!=f)
{ f++;i=qu[f];
for(j=p;jarcs[i][j]==1&&(!visitec[j])){
printf(“%3c”,G.vexs[j]);
visited[j]=I;
r++;qu[r]=j;
}
}
} /*Bfs*/
分析上述算法，一个有n个顶点、e条边的图，在广度优先搜索图的过程中，每个顶点至多进一次队列，所以算法中的内外循环次数均为n次，故算法Bfs的时间复杂度为O(n2);若采用邻接链表存储结构，广度优先搜索遍历图的时间复杂度与深度优先搜索是相同的。 5.5.3 求图的连通分量
求图的连通分量是图的遍历的一种简单应用。当无向图是连通图是，只需要调用一次Dfs(或Bfs)算法，便可访问图中的所有顶点。但无向图是非连通图时，从图中某顶点V出发遍历图，不能访问到图的所有顶点，而只能访问到包含V所在的最大连通子图(连通分量)中的所有顶点。若从非连通图中每一个连通分量中的一个顶点出发遍历图，则可求出无向图的所有连通分量。
为了求得非连通图的所有的连通分量，只需要调用Dfs或Bfs，并对图中每个顶点进行检测。若某顶点已被访问，则该顶点落在图中已求得的连通分量上;若某顶点未被访问，则从该顶点出发遍历图，便可求得图的另已连通分量，调用Dfs或Bfs的次数就是连通分量的个数。下面以临界矩阵为存储结构，给出通过深度优先搜索算法实现求非连通图的连通分量的算法。
算法5.6
Int visited[vex_num]={0}
Void component(mgraph g){
/*求图的连通分量，G以邻接矩阵表示*/
Count=0; /*统计连通分量的个数*/
For(j=0;j
本文档为【1掌握图的两种遍历算法:深度优先搜索和广度优先搜索算...】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483