BFSとDFSの違い

本ブログ作成文は、講義を目指して製作されました。 また、作成された文章の情報も間違っている可能性がありますので、ご注意ください。

グラフを探索する代表的な方法にはBFSとDFSがある。 どちらも訪れていない頂点をたどるが、順番が違う。

BFS

Breadth-First Searchは始点から近い頂点から広く探索する。 Queueを使用してください。

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

Depth-First Searchは1つのルートを最後まで降りた後に戻ります。 再帰呼び出しまたはStackを使用してください。

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

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

接続要素、サイクル検出、バックトラッキング構造によく使用されます。 グラフが非常に深い場合は、再帰スタックがあふれる可能性があるため、明示的なスタック実装を検討してください。

BFSが無条件で良いか、DFSが無条件に高速ではありません。 近い答えが必要か、パスを深くテストする必要があるか、メモリとグラフの深さがどれかによって選択します。