侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

图的遍历(下)—— 广度优先搜索

kaixindeken
2021-04-23 / 0 评论 / 0 点赞 / 74 阅读 / 1,030 字

广度优先搜索定义

广度优先搜索(Breadth First Search),简称 BFS,我们以在家里房间里找钥匙为例来对比说明深度优先搜索和广度优先搜索,深度优先搜索好比我们从某个房间(顶点)开始,先把一个房间的所有角落找遍,再从下一个相邻房间开始继续找,依次类推,但这有时候并不是最佳方案,我们可以换一种思路,先大致扫一下每个房间的常见位置,如果都没有的话才继续更深入的寻找,这种遍历方式就是广度优先搜索。

还可以通过树的遍历来类比图的遍历,前序遍历类似深度优先搜索,层序遍历类似广度优先搜索,下面我们以一个图为例来说明,这样更加形象:

1.png

左图是我们要遍历的图,右图是以广度优先搜索对图进行遍历,我们把 A 作为第一层,B、F 作为第二层,C、I、G、E 看作第三层,D、H 看作第四层,每次遍历一层。

这与我们上一篇讲述的深度优先搜索显然不同,深度优先搜索会把某个顶点的所有相邻顶点访问完才继续下一个顶点的访问,广度优先搜索则不然,它是按照「层级」遍历图的节点,最终也能够遍历完所有节点。

//定义图的存储方式为邻接矩阵
typedef struct {
    VertexType vex[100];
    EdgeType edge[100];
    int vexNum, edgeNum;
}MGraph;
bool visited[100];
void BFSTravel(MGraph g) {
    int v;
    for ( v = 0; v < g.vexNum; ++v) {
        visited[v] = false;
    }
    for (v = 0; v < g.vexNum; v++) {
        if (!visited[v]) {
            BFS(G,v)
        }
    }
}
void DFS(MGraph g, int v) {
    std::cout<<v<<std::endl;
    visited[v] = true;
    for (int i = FirstNeighbor(G, v); i >= 0 ; i = NextNeighbor(G, v, i)) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
}
  • FirstNeighbor(G, v)表示顶点 v 在图 G 中的一个邻接点
  • NextNeighbor(G, v, i) 表示顶点 v 在图 G 中除 i 之外的其他邻接点

广度优先搜索的时间复杂度和深度优先搜索一样,也是 O(v+e),其中 v 表示顶点数,e 表示边数,需要额外的数组存储已访问顶点和前驱顶点,对应的空间复杂度是 O(v)。

广度优先搜索和深度优先搜索的复杂度完全一样,没有优劣之分,具体使用哪种搜索方式,以实际情况为准。

0

评论区