深度优先搜索

20
五月
2021

深度优先搜索类似于树的先序遍历。
思想:首先访问图中某一起始顶点v,然后由v出发,访问与v邻接且未被访问的任一顶点w1,再访问与w1邻接且未被访问的任一顶点w2·····重复上述过程。当不能再继续向下访问时,依次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,直到图中所有顶点均被访问过为止。

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G)
{
    for(v=0; v<G.vexnum; ++v)
        visited[v] = FALSE;
    for(v=0; v<G.vexnum; ++v)
        if(!visited[v])
           DFS(G, v);
}
void DFS(Graph G, int v)
{
    visit(v);
    visited[v] = TRUE;
    for(w=FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w))
        if(!visited[w])
        {  
            DFS(G, w);
        }
}

以下图为例,
首先访问a,并置a已访问标记;然后访问与a邻接且未被访问的顶点b,置b已访问标记;然后访问与b邻接且未被访问的顶点d,置d已访问标记。此时d已没有未被访问过的邻接点,故返回上一个访问过的顶点b,访问与其邻接且未被访问的顶点e,置e访问标记·····以此类推,直到图中所有的顶点访问一次且仅访问一次。遍历结果为abdehcfg。

注意:图的邻接矩阵表示是唯一的,但对于邻接表来说,若边的输入次序不同,生成的邻接表也不同。因此,对于同样一个图,基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的,基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

DFS算法的性能分析
DFS算法是一个递归算法,需要借助一个递归栈,故其空间复杂度为O(|V|)。

遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所用的存储结构。以邻接矩阵表示时,查找每个顶点的邻接点所需的时间为O(|V|),故总的时间复杂度为O(|V|2)。以邻接表表示时,查找所有顶点的邻接点所需的时间为O(|E|),访问顶点所需的时间为O(|V|),此时,总的时间复杂度为O(|V|+|E|)。

深度优先的生成树和生成森林
对连通图调用DFS才能产生深度优先生成树,否则产生的将是深度优先生成森林。与BFS类似,基于邻接表存储的深度优先生成树是不唯一的。

TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员