深さ優先探索 (DFS) と幅優先探索 (BFS) の 2 つのアルゴリズムの詳細な説明

序文

深さ優先探索 (DFS) と幅優先探索は、グラフ理論における非常に重要な 2 つのアルゴリズムです。これらは、トポロジカル ソート、パス検索 (迷路歩行)、検索エンジン、クローラーなどで広く使用されています。また、LeetCode や高頻度面接の質問にも頻繁に登場します。

この記事では、深さ優先探索と幅優先探索について、以下の観点から説明します。この記事を読めば、必ず何かが得られると思います。

• 深さ優先探索、幅優先探索の紹介
• 演習
• 検索エンジンにおけるDFSとBFSの応用

深さ優先探索と幅優先探索の紹介

深さ優先探索

主なアイデアは、グラフ内の未訪問の頂点 V から開始し、道路に沿って端まで歩き、この道路の端にあるノードから前のノードに戻り、別の道路から開始して端まで歩き、すべての頂点を通過するまでこのプロセスを再帰的に繰り返すことです。その特徴は、壁にぶつかるまで引き返さないことです。まず 1 つの道路を終了し、次に別の道路に変更して続行します。

ツリーはグラフの特殊なケースです (連結された非巡回グラフはツリーです)。次に、深さ優先走査を使用してツリーを走査する方法を見てみましょう。

1. ルート ノード 1 からトラバースを開始します。その隣接ノードは 2、3、4 です。最初にノード 2 をトラバースし、次に 2 の子ノード 5 をトラバースし、最後に 5 の子ノード 9 をトラバースします。

2. 上の図では、1 つの道路が終点に到達しています (9 はリーフ ノードであり、これ以上通過可能なノードはありません)。このとき、9 から前のノード 5 に戻り、ノード 5 に 9 以外のノードがあるかどうかを確認します。2 には戻らず、2 には 5 以外のノードはありません。1 に戻ると、1 には 2 以外のノード 3 があります。したがって、次のようにノード 3 から深さ優先の通過を開始します。

3. 同様に、10 から 6 まで遡ります。6 には 10 以外の子ノードはありません。次に、もう一度遡って、3 には 6 以外の子ノード 7 があることがわかります。そのため、今回は 7 がトラバースされます。

3. 7 から 3、1 に戻り、1 でトラバースされていないノード 4 がまだあることを確認します。そこで、4、8 に沿ってトラバースすると、トラバースが完了します。

完全なノードのトラバーサル順序は次のとおりです (ノード上の青い数字で表されます)。

上記のトラバーサルを見た後、これがツリーの事前順序トラバーサルであることを見つけるのは難しくないと思います。実際、事前順序トラバーサル、インオーダートラバーサル、またはポストオーダートラバーサルのいずれであっても、それらはすべて深さ優先トラバーサルに属します。

では、深さ優先探索をどのように実装するのでしょうか? 深さ優先探索には、再帰と非再帰の 2 つの形式があります。次に、バイナリ ツリーを例に、それぞれ再帰と非再帰を使用して深さ優先探索を実装する方法を説明します。

1. 再帰実装

再帰実装は比較的簡単です。これは事前順序のトラバーサルなので、現在のノード、左のノード、右のノードを順番にトラバースできます。左のノードと右のノードについては、左のノードと右のノードを順番にトラバースし、リーフ ノード (再帰終了条件) まで再帰を続けます。コードは次のとおりです。

パブリッククラスソリューション{
    プライベート静的クラス Node {
        /**
         * ノード値
         */
公共  int値;
        /**
         * 左ノード
         */
パブリックノードleft ;
        /**
         * 右ノード
         */
パブリックノード権限; 
 
パブリックNode( int値、ノード左、ノード右) {
            this.value = 値;
            this.left =左;
            this.right =右;
        }
    } 
 
公共 静的void dfs(ノードtreeNode) {
        ツリーノードがnullの場合
戻る;
        }
        // ノードをトラバースする
        プロセス(ツリーノード)
        //左のノードをトラバースする
        dfs(ツリーノード.left );
        //右のノードをトラバースする
        dfs(ツリーノード.right );
    }
 }

再帰は非常に表現力豊かで理解しやすいですが、レベルが深すぎるとスタック オーバーフローに簡単につながる可能性があります。したがって、非再帰的な実装に焦点を当てます。

2. 非再帰実装

深さ優先走査の特徴を注意深く観察してください。バイナリ ツリーの場合、これは事前順序走査 (最初に現在のノードを走査し、次に左のノードを走査し、最後に右のノードを走査する) であるため、次の考え方があります。

各ノードについて、最初に現在のノードをトラバースし、次に右側のノードをスタックにプッシュし、最後に左側のノードをプッシュします (スタックをポップするときに、左側のノードが最初にトラバースされ、深さ優先のトラバーサル要件が満たされます)。

スタックをポップし、スタックの一番上のノードを取得します。ノードが空でない場合は、手順 1 を繰り返します。空の場合は、トラバーサルを終了します。

スタックを使用して DFS を実装する方法を確認するために、次のバイナリ ツリーを例に挙げてみましょう。

全体的なアニメーションは次のとおりです。

全体的な考え方は非常に明確です。スタックを使用してトラバースするノードをプッシュし、スタックをポップした後、トラバースされていないノードがあるかどうかを確認します。ある場合は、スタックにプッシュします。ない場合は、バックトラックを続けます (スタックをポップします)。この考え方を使用すると、スタックによって実装されたバイナリツリーの次の深さ優先トラバーサルコードを書くのは難しくありません。

 /**
 * スタックを使用して dfs を実装する
 * @param ルート
 */
公共 静的void dfsWithStack(ノードルート) {
    ルートがnullの場合
戻る;
    } 
 
    Stack<Node> スタック = new Stack<>();
    // まずルートノードをスタックにプッシュします
    スタックをプッシュします(ルート);
    スタックが空である間
        ノード treeNode = stack.pop();
        // ノードをトラバースする
        プロセス(ツリーノード) 
 
        // 最初に右のノードを押します
        treeNode.rightがnullの場合
            スタックをプッシュします( treeNode.right );
        } 
 
        // 左のノードをもう一度押す
        treeNode.leftがnullの場合
            スタックをプッシュします( treeNode.left );
        }
    }
 }

スタックを使用して深さ優先トラバーサルを実装するコードは複雑ではなく、再帰のレベルが深すぎるために発生するスタック オーバーフローを心配する必要がないことがわかります。

幅優先探索

幅優先走査とは、グラフ内の未走査ノードから開始し、最初にこのノードの隣接ノードを走査し、次に各隣接ノードの隣接ノードを順に走査することを意味します。

上で説明したツリーの幅優先トラバーサルアニメーションは次のようになり、各ノードの値はトラバーサル順序になります。そのため、幅優先トラバーサルはレイヤー順トラバーサルとも呼ばれます。最初に第 1 レイヤー (ノード 1) をトラバースし、次に第 2 レイヤー (ノード 2、3、4)、第 3 レイヤー (5、6、7、8)、第 4 レイヤー (9、10) をトラバースします。

深さ優先トラバーサルはスタックを使用し、幅優先トラバーサルはキューを使用して実装されます。下の図のバイナリ ツリーを例に、キューを使用して幅優先トラバーサルを実装する方法を見てみましょう。

アニメーション画像は次のとおりです。

上記のアニメーションを見た後では、次のコードを書くのは難しくないと思います。

 /**
 * キューを使用してBFSを実装する
 * @param ルート
 */
プライベート静的void bfs(ノードルート) {
    ルートがnullの場合
戻る;
    }
    キュー<Node> スタック = 新しい LinkedList<>();
    スタックを追加します(ルート); 
 
    スタックが空である間
        ノード node = stack.poll();
        システム.out.println ( "value = " + node.value);
        ノード左= node.left ;
        if (左!= null ) {
            stack.add (左);
        }
        ノード右= node.right ;
        if (右!= null ) {
            stack.add (右);
        }
    }
 }

演習

次に、DFS と BFS を使用して問題を解決する LeetCode の問題をいくつか見てみましょう。

 Leetcode 104、111: バイナリ ツリーが与えられた場合、その最大/最小の深さを見つけます。

例えば、二分木[3,9,20,null,null,15,7]が与えられた場合、

 3
  / \
 9 20
   / \
  15 7

すると、最小深度は 2、最大深度は 3 になります。

解決策: この問題は比較的単純です。これは深さ優先探索の単なるバリエーションです。左と右のサブツリーの最大/最小の深さを再帰的に見つけるだけです。深さは、関数が再帰的に呼び出されるたびに 1 を加算して計算されます。次のコードを書くのは難しくありません。

 /**
 * Leetcode 104: ツリーの最大深さを見つける
 * @param ノード
 * @戻る 
 */
公共 静的  int getMaxDepth(ノードノード) {
    if (ノード == null ) {
 0を返します。
    }
左の深さをgetMaxDepth (node.left ) + 1 に設定します。
右の深さを getMaxDepth(node.right ) + 1 に設定します。
 Math.max (leftDepth, rightDepth)を返します。
 } 
 
 /**
 * Leetcode 111: ツリーの最小深さを見つける
 * @param ノード
 * @戻る 
 */
公共 静的  int getMinDepth(ノードノード) {
    if (ノード == null ) {
 0を返します。
    }
最小深度を取得するには、 node.leftの左辺に1 を代入します。
右の深さを getMinDepth(node.right ) + 1 に設定します。
 Math.min (leftDepth, rightDepth)を返します。
 }

Leetcode 102: バイナリ ツリーが与えられた場合、レベル順にトラバースして取得したノード値を返してください。 (つまり、すべてのノードを左から右へ、レイヤーごとに訪問します)。たとえば、バイナリツリーが与えられます: [3,9,20,null,null,15,7]。

 3
  / \
 9 20
   / \
  15 7

レベルトラバーサルの結果を返します:

 [
  [3]、
  [9,20]、
  [15,7]
 ]

解決策: 明らかに、この問題は幅優先トラバーサルの変形です。幅優先トラバーサル中に、各レイヤーのノードを同じ配列に追加するだけで済みます。この問題の鍵となるのは、同じレイヤーのノードをトラバースする前に、同じレイヤーのノードの数 (つまり、キュー内の要素の数) を事前に計算する必要があることです。BFS はキューによって実装されるため、トラバーサル プロセス中に、左と右の子ノードがキューに継続的に追加されます。これを覚えておいてください。アニメーション画像は次のとおりです。

上記のアニメーションのアイデアによれば、次のようにコードを導き出すのは難しくありません。

Javaコード

/**
 * leetcdoe 102: bfs を使用したバイナリ ツリーのレベル順トラバーサル
 * @param ルート
 */
プライベート静的List<List< Integer >> bfsWithBinaryTreeLevelOrderTraversal(ノードルート) {
    ルートがnullの場合
        // ルートノードは空で、バイナリツリーが存在しないことを示しています。空の配列が直接返されます。
 Arrays.asList()を返します。
    } 
 
    // 最終的なレイヤー順序のトラバーサル結果
    List<List< Integer >> 結果 = new ArrayList<>(); 
 
    キュー<Node> キュー = new LinkedList<>();
    キュー.offer(ルート); 
 
    キューが空の場合
        // 各レイヤーを記録する
        リスト<整数>レベル= 新しい ArrayList<>();
キューのサイズ。
        // 現在のレイヤーのノードを走査する
( int i = 0; i < レベル数; i++) {
            ノード node = queue.poll();
            // 最初のノードの左と右の子ノードがキューに追加されます。キューに追加する前に levelNum が計算されるため、キューに追加された左と右のノードは現在のレイヤーでは走査されません。
            （ノード.left != null ）の場合 {
                キューに追加します( node.left );
            }
            （ node.right != null ）の場合 {
                キューに追加します( node.right );
            }
レベル.add (ノード.値) ;
        }
        result.add (レベル);
    } 
 
結果を返します。
 }

Pythonコード

クラスソリューション:
    定義レベル順序(自己、ルート):
 「」 「 」
        :type root: ツリーノード
        :rtype: リスト[リスト[ int ]]
 「」 「 」
        res = [] #ネストされたリスト、最終結果を保存する
        ルートがNoneの場合:
戻り値
         
コレクションからdeque をインポート
        que = deque([root]) #キューに入れ、処理するノードを保存します
        len(que)!=0の場合:
            lev = [] #list、このレイヤーのノードの値を保存します
            thislevel = len(que) #このレイヤー内のノードの数
            thislevel!=0 の場合:
                head = que.popleft() #チームの最初のノードをポップアップします
                #最初のノードの左と右の子がチームに参加します
                頭が左の場合 は なしではない:
                    que.append(ヘッド.left )
                頭が右の場合 は なしではない:
                    que.append(ヘッド.right )
                lev.append(head.val) #最初のノードの値がこのレイヤーにプッシュされます
                このレベル-=1
            res.append(lev)
戻り値

この質問にはBFSを使うのが当然ですが、DFSも使えます。面接でDFSを使って対応できれば大きなアピールになります。

DFS の使い方は? DFS は再帰的に実装できることはわかっています。実際、再帰関数に「レイヤー」変数を追加するだけで済みます。ノードがこのレイヤーに属している限り、ノードを対応するレイヤーの配列に配置します。コードは次のとおりです。

プライベート静的最終List<List< Integer >> TRAVERSAL_LIST = new ArrayList<>();
 /**
 * leetcdoe 102: dfs を使用したバイナリ ツリーのレベル順トラバーサル
 * @param ルート
 * @戻る 
 */
プライベート静的void dfs(ノードルート、 int  レベル） {
    ルートがnullの場合
戻る;
    } 
 
    （TRAVERSAL_LIST.size （ ）<レベル+ 1）の場合{
        TRAVERSAL_LISTを追加します(新しい ArrayList<>());
    } 
 
    リスト<整数> levelList = TRAVERSAL_LIST.get(レベル);
    レベルリストに(ルートの値)を追加します。 
 
    //左のノードをトラバースする
    dfs(ルート.左、レベル+1 ); 
 
    //右のノードをトラバースする
    dfs(ルート.right 、レベル+1 );
 }

検索エンジンにおける DFS と BFS の応用 私たちは、Google や Baidu などの検索エンジンをほぼ毎日使用しています。これらの検索エンジンがどのように機能するかご存知ですか? 簡単に言えば、3 つのステップがあります。

1. ウェブクローリング

検索エンジンはクローラーを通じてウェブページをクロールし、ページのHTMLコードを取得してデータベースに保存します。

2. 前処理

インデックスプログラムは、ランキングプログラムで使用するために、キャプチャしたページデータに対してテキスト抽出、中国語の単語分割、（逆）インデックス作成などの処理を実行します。

3. ランキング

ユーザーがキーワードを入力すると、ランキング プログラムはインデックス データベース データを呼び出し、関連性を計算し、特定の形式で検索結果ページを生成します。

最初のステップである Web クロールに焦点を当てましょう。

このステップの一般的な操作は次のとおりです。開始 Web ページのセットをクローラーに割り当てます。Web ページには実際には多くのハイパーリンクが含まれていることがわかっています。クローラーは Web ページをクロールした後、Web ページ内のすべてのハイパーリンクを解析して抽出し、これらのハイパーリンクを順番にクロールして、Web ページのハイパーリンクを抽出します。 。 。このプロセスを何度も繰り返すことで、ハイパーリンクに基づいて Web ページを継続的に抽出できます。以下のように表示されます。

上に示したように、最終的にグラフが形成されるので、このグラフをどのようにトラバースするかが問題になります。明らかに、深さ優先または幅優先の方法でトラバースできます。

幅優先のトラバーサルの場合は、まず開始 Web ページの最初のレイヤーをクロールし、次に各 Web ページ内のハイパーリンクをクロールします。深さ優先のトラバーサルの場合は、まず開始 Web ページ 1 をクロールし、次にこの Web ページ内のリンクをクロールします... クロール後、開始 Web ページ 2 をクロールします...

実際、クローラーは深さ優先戦略と幅優先戦略の両方を併用します。たとえば、開始 Web ページの中には、より重要な (重みが高い) Web ページがあるため、最初にこの Web ページを深さ優先でトラバーサルし、次に他の開始 Web ページ (重みは同じ) を幅優先でトラバーサルします。

要約する

DFS と BFS は、習得しなければならない 2 つの非常に重要なアルゴリズムです。便宜上、この記事ではツリーに対してのみ DFS と BFS を実行します。グラフを使用する場合は、コードを記述してみてください。原理は実際には同じですが、グラフとツリーの表現は異なります。DFS は一般に接続問題を解決し、BFS は一般に最短経路問題を解決します。union-find、Dijkstra、Prism アルゴリズムなどについては、後ほど学習する機会があります。お楽しみに!