［アルゴリズム］DFSとBFS

7797 ワード

アルゴリズム#アルゴリズム# DFS TIL BFS テキストリンク

ナビゲーショングラフ＃グラフ＃の方法としては、幅優先ナビゲーション(BFS)と深さ優先ナビゲーション(DFS)がある.
上記のリンクの位置付けでは簡単に述べたが,両方式の違いといつどの方式を使用するかについて詳細に議論する.

2つのアルゴリズムの動作は次のとおりです.

DFS

は、1つのルート上を探索する、特定の状況下でできるだけ深く確認してから、別のルート上を探索する方法

に戻る.

校正、スタック実施

バックグラウンド追跡用

    static void DFS(int x) {
        visit[x] = true;
        sb.append(x).append(' ');
        for (int y: adj[x]) {
            if (visit[y]) continue;
            dfs(y);
        }
    }

BFS

開始点の隣接頂点を順番に参照する方法

キュー実装

の検索速度はDFSより

速い

static void BFS(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        visit[x] = true;

        while(!q.isEmpty()) {
            x = q.poll();
            sb.append(x).append(' ');
            for (int y: adj[x]) {
                if (visit[y]) continue;
                q.add(y);
                visit[y] = true;
            }
        }
    }

時間の複雑さ、空間の複雑さ

パターンを巡回する時間的複雑度DFS,BFSは同じであり,パターンを保存する方法で隣接行列を使用するか隣接リストを使用するかによって異なる.

隣接行列

グラフィック接続関係の2 D配列

両頂点が接続する場合は1、重み付け時は

となる.

は、

を容易に実施する.

が占有する空間に比べて、

が占有する空間は非常に少ない.

りんせつひょう

パターンの2次元ArrayList接続方式:

の基準頂点に関連する頂点のみが

を記録する.

各頂点に記録する要素の数は、その頂点の回数

に等しい.

頂点Aの回数(DEG(A):頂点Aに接続する幹線数

すべての頂点の回数の和==すべての幹線の個数*2

頂点の個数がV、幹線の個数がEのとき
隣接行列隣接リスト時間複雑度O(V^2)O(V+E)空間複雑度O

AとBの接続や重みをチェックすると、隣接行列はadj[A][B]を直接チェックし、隣接リストチェックAのArrayList要素は全て

をチェックする.

Aで到達可能な頂点が決定すると、隣接行列はA行のすべての列を検査し、隣接リストはA中のすべてのArrayList要素

を検査する.
->隣接テーブルを主に使用するが,接続の有無を確認する際には,隣接マトリクスを使用する時間的複雑さが高い.つまり、状況によって使い方が違うので、どちらの場合もはっきりしている.
->ただし、接続の有無を決める問題でも、幹線数が多いと隣接行列の空間的複雑度がO(V^2)を超える可能性があるので、空間的複雑度を考慮しなければなりません!