前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >图的遍历之深度优先搜索(DFS)

图的遍历之深度优先搜索(DFS)

作者头像
llhthinker
发布2018-01-24 16:31:04
1.7K0
发布2018-01-24 16:31:04
举报

深度优先搜索depth-first search)是对先序遍历preorder traversal)的推广。”深度优先搜索“,顾名思义就是尽可能的搜索一个图。想象你是身处一个迷宫的入口,迷宫中的路每一个拐点有一盏灯是亮着的,你的任务是将所有灯熄灭,按照DFS的做法如下:

1. 熄灭你当前所在的拐点的灯

2. 任选一条路向前(深处)走,每经过一个拐点将灯熄灭直到与之相邻的拐点的灯全部熄灭后,原路返回到某个拐点的相邻拐点灯是亮着的,走到灯亮的拐点,重复执行步骤1

3. 当所有灯熄灭时,结束

将上面的例子抽象出来的DFS的算法描述(C伪代码)如下:

代码语言:javascript
复制
//布尔型数组Visited[]初始化成false
void DFS(Vetex v)
{
    Visited[v] = true;
    for each w adjacent to v
        if (!Visited[w])
            DFS(w);
}

 可以看出上述的DFS为递归算法,可以利用将其转为非递归。C伪代码如下:

代码语言:javascript
复制
//布尔型数组Visited[]初始化成false
void DFS(Vertex v)
{
    Visited[v] = true;    
    Stack  sta = MakeStack(MAX_SIZE);
    Push(sta, v);
    while (!Empty(sta))
    {
        Vertex w = Pop(sta);
        for each u adjacent to w
        {            
            if (!Visited[u]) 
            {
                Push(sta, u);
                Visited[u] = true;            
            }
        }
    }
}

引理: 若图G是连通的,则通过深度优先搜索可以对它的所有顶点进行标记,并且在算法的执行过程中,它的每一条边至少被查看过一次。

证明: 假设结论不成立,令U表示算法最终未被标记过的顶点的集合。由于G是连通的,因此在U中至少有一个顶点与一个被标记过的顶点相连。但是这种情况不可能成立,因为一旦一个顶点被访问过了,则所有与它相连的未被标记过的顶点也会被访问(从而也被标记)。故所有顶点都会被访问而标记,并且一旦某个顶点被访问,它相连的边就会被查看,所以每条边都将被查看过。

然而,如果一个图G不是连通的,要标记所有顶点,需对DFS稍作修改:若在第一次尝试所有顶点都被标记过,则图是连通的,否则,从任意一个未被标记的顶点开始,再次执行DFS。所以我们可以利用DFS确定一个图是否连通。C伪代码描述上述算法如下:

代码语言:javascript
复制
/*返回连通成分的数目*/
int ConnectedComponents ( Graph G )
{ 
    int componentNum = 0;
    for ( each v in G )
        if ( !visited[V] ) 
        {
            DFS( v );
            componentNum += 1;
        }
    return componentNum;
} 

上述算法的复杂度:

若有N个顶点、 E条边,时间复杂度是   用邻接表存储图,有O(N+E)   用邻接矩阵存储图,有O(N^2)

深度优先搜索的相关练习:

poj-1979 Red and Black

poj-2386 Lake Counting

列出连通集

06-图2 Saving James Bond - Easy Version

poj-2488 A Knight's Journey

拓展阅读:

深度优先生成树及其应用

参考资料:

《数据结构与算法分析-C语言描述》

《算法引论》

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015-09-28 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档