BFS 和 DFS 的区别

该博客上撰写的文章是出于教学目的而创建的。 另外，文章中的信息可能不正确，请谨慎。

探索图的代表性方法包括 BFS 和 DFS。 两者都遵循未访问的顶点，但顺序不同。

BFS

广度优先搜索从最接近起点的顶点开始广泛搜索。 使用队列。

std::queue<int> Open;
std::vector<bool> Visited(NodeCount, false);

Open.push(Start);
Visited[Start] = true;

while (!Open.empty())
{
    const int Current = Open.front();
    Open.pop();

    for (int Next : Graph[Current])
    {
        if (!Visited[Next])
        {
            Visited[Next] = true;
            Open.push(Next);
        }
    }
}

如果所有边的代价相同，BFS就能找到从起点开始边数最少的路径。

DFS

深度优先搜索沿着一条路径一直进行，然后返回。 使用递归调用或堆栈。

void DFS(int Current)
{
    Visited[Current] = true;

    for (int Next : Graph[Current])
    {
        if (!Visited[Next])
        {
            DFS(Next);
        }
    }
}

它常用于连接元素、循环检测和回溯结构。 如果图很深，递归Stack可能会溢出，所以考虑实现一个显式Stack。

BFS不一定更好，或者DFS不一定更快。 您的选择取决于您是否需要一个接近的答案、是否需要深入测试路径以及您的内存和图形深度。