Java教程

关于图的BFS与DFS算法的总结

本文主要是介绍关于图的BFS与DFS算法的总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

如题 自用笔记 如有错误欢迎及时指正

目录

一.广度优先搜索(BFS)

1.基本思路

2.算法描述

3.应用

二.深度优先搜索(DFS)

1.基本思路

2.算法描述

3.应用


(以下假设图G有V个结点E条边)

        图的遍历等价于寻找每个顶点的邻接点的过程,BFS与DFS在思路上仅仅是遍历策略上的区别,本质都是上述过程。

        一个图无论是有向图还是无向图,都有可能存在回路,这使得遍历操作必须防止重复访问某一结点,设置一个visited[V]数组来标记某个结点是否访问过可以解决此问题。

        下面分别给出BFS与DFS的思想、类C伪码与N-S流程图描述。

一.广度优先搜索(BFS)

*该方法类似树的层序遍历方法,要借助一个辅助队列实现

1.基本思路

         1.从图的某个顶点V0出发,访问此结点之后,依次访问V0的所有未被访问过的邻接点,然后再分别从这些邻接点出发,广度优先遍历图,直到图中所有已被访问结点的邻接点都被访问到。

        2.若此时图中还有顶点未被访问到,则另选一个图中未被访问到的顶点作为新起点,重复上述过程,直到图中所有结点都被访问到。

2.算法描述

        类似层序遍历思路,树的层序遍历算法就是由BFS启发得来。

        为便于理解,先给出伪代码实现。

bool visited[V]; 
void BFS(Graph G,v){
    //辅助队列
    InitQueue(Q);
    visited[v] = true;
    viist(v);       //访问
    EnQueue(Q, v);
    while(!QueueEmpty(Q)){
        DeQueue(Q, u);
        for (w = FisrtAdjvex(G, u); w != 0; w=NextAdjvex(G,u,w)){        
            //w为当前出队元u的第一个邻接点
            if(!visited[w]){
                visited[w] = true;
                visit(w);
                EnQueue(Q, w);
            }
        }
    }
}
void BFSTraverse(Graph G){
    for (v = 0; v < G.vexnum; ++v){
        visited[v] = false;        //初始化辅助数组
    }
    for (v = 0; v < G.vexnum; ++v){
        if(!visited[v]){
            BSF(G, v);
        }
    }
}

3.应用

        查找连通分量

        查找一个连通分量中所有结点

        查找两个结点之间最短路径

        判断偶图

二.深度优先搜索(DFS)

*该方法类似树的先序遍历方法

1.基本思路

        1.从图的某一顶点V0出发,访问此顶点,然后依次从V0未被访问的邻接点出发,深度优先遍历图,直到图中所有与V0相邻的顶点都被访问到为止。

        2.若此时图中仍有结点未被访问到,则选择图中未被访问到的结点作为起点,重复上述过程,直到图中所有顶点均被访问到为止。

2.算法描述

        类先序遍历思想

        初始时,所有顶点均被标记为未被访问;

        DFS从图的顶点v开始,考虑从v到其他顶点的边:

                如果边关联的另一个顶点已经访问过,则返回当前顶点v;

                如果边关联的另一个顶点未被访问过,转到该顶点访问并继续搜索;

        持续上述过程直到结尾,开始回溯。当回溯返回到起始顶点时,算法终止。

        为便于理解,先给出类C伪代码实现。

bool visited[V];     //标记是否已访问过某结点
void DFS(Graph G,v){
    visited[v] = true;     //置为已访问状态
    visit(v);       //操作
    for (w = FirstAdjvex(G, v); w!=0;w=NextAdjvex(G,v,w)){      //w寻找v下一未被访问的邻接点
        if(!visited[w]){
            DFS(G, w);
        }
    }
}
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
            DFS(G, v);
        }
    }
}

3.应用

        拓补排序

        查找连通分量

        查找图关节点

        查找强连通分量

        解决迷宫问题等

以上

2021.10.19

17:30

这篇关于关于图的BFS与DFS算法的总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!