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不一定比較快。 您的選擇取決於您是否需要一個接近的答案、是否需要深入測試路徑以及您的記憶體和圖形深度。