掌握图的两种遍历算法深度优先搜索和广度优先搜索算.doc

掌握图的两种遍历算法深度优先搜索和广度优先搜索算.doc

ID:55894570

大小:99.00 KB

页数:5页

时间:2020-06-13

掌握图的两种遍历算法深度优先搜索和广度优先搜索算.doc_第1页
掌握图的两种遍历算法深度优先搜索和广度优先搜索算.doc_第2页
掌握图的两种遍历算法深度优先搜索和广度优先搜索算.doc_第3页
掌握图的两种遍历算法深度优先搜索和广度优先搜索算.doc_第4页
掌握图的两种遍历算法深度优先搜索和广度优先搜索算.doc_第5页
资源描述:

《掌握图的两种遍历算法深度优先搜索和广度优先搜索算.doc》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、第五章图第十七讲图的遍历1.掌握图的两种遍历算法:深度优先搜索和广度优先搜索算法,2.求解连通性问题的方法。Ø教学重点:图的两种遍历算法:深度优先搜索和广度优先搜索算法Ø教学难点:图的两种遍历算法:深度优先搜索和广度优先搜索算法Ø授课内容5.3图的遍历和树的遍历类似,在此,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次。这一过程就叫做图的遍历(TraversingGraph)。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。然而,图的遍历要比树的遍历复杂得多。因为图的任一

2、顶点都可能和其余的顶点相邻接。所以在访问了某个顶点之后,可能沿着某条路径搜索之后,又回到该顶点上。[例如]图7.1(b)中的G2,由于图中存在回路,因此在访问了v1,v2,v3,v4之后,沿着边(v4,v1)又可访问到v1。为了避免同一顶点被访问多次,在遍历图的过程中,必须记下每个已访问过的顶点。为此,我们可以设一个辅助数组visited[0..n-1],它的初始值置为“假”或者零,一旦访问了顶点vi,便置visited[i]为“真”或者为被访问时的次序号。   通常有两条遍历图的路径:深度优先搜索和广度优先搜索。

3、它们对无向图和有向图都适用。5.3.1深度优先搜索深度优先搜索(Depth-FirstSearch)遍历类似于树的先根遍历,是树的先根遍历的推广。其基本思想如下:假定以图中某个顶点vi为出发点,首先访问出发点,然后选择一个vi的未访问过的邻接点vj,以vj为新的出发点继续进行深度优先搜索,直至图中所有顶点都被访问过。显然,这是一个递归的搜索过程。现以图5-3-1第五章图中G为例说明深度优先搜索过程。假定v0是出发点,首先访问v0。因v0有两个邻接点v1、v2均末被访问过,可以选择v1作为新的出发点,访问v1之后,再

4、找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

5、→v3→v7→v4→v2→v5→v7。(a)无向图G(b)G的深度优先搜索过程图5-3-1深度优先搜索遍历过程示例因为深度优先搜索遍历是递归定义的,故容易写出其递归算法。下面的算法5.3是以邻接矩阵作为图的存储结构下的深度优先搜索遍历算法;算法5.4是以邻接表作为图的存储结构下的深度优先搜索遍历算法。算法5.3intvisited[NAX_VEX]={0};voidDfs_m(Mgraph*G,inti){/*从第i个顶点出发深度优先遍历图G,G以邻接矩阵表示*/printf("%3c",G->vexs[i]);v

6、isited[i]=1;for(j=0;jarcs[i][j]==1)&&(!visited[j]))Dfs_m(G,j);}/*Dfs_m*/算法5.4intvisited[VEX_NUM]={0};voidDfs_L(ALgraphG,inti){/*从第i个顶点出发深度优先遍历图G,G以邻接表表示*/printf("%3c",G[i].data);visited[i]=1;p=G[i].firstarc;while(p!=NULL){if(visited[p->adjv

7、ex]==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的时间复

8、杂度为>O(n+e)。5.3.2广度优先搜索连通图的广度优先搜索(Breadth_FirstSearch)遍历图类似于树的按层次遍历。其基本思想是:首先访问图中某指定的起始点Vi并将其标记为已访问过,然后由Vi出发访问与它相邻接的所有顶点Vj、Vk……,并均标记为已访问过,然后再按照Vj、Vk……的次序,访问每一个顶点的所有未被访问过的邻接顶点,并均标记为已

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。