グラフアルゴリズム-5ステップのみで、2つのノード間のすべてのパスを取得します(再帰的ではありません).

「図」データ構造を実現する際、「2点間を取得するのはすべてのパス」というアルゴリズムの問題に直面し、ネット上の資料の多くは再帰アルゴリズムを利用して実現される(文末の参考文章を参照).
JSでは再帰アルゴリズムを用いると呼び出しスタックがオーバーフローしやすいことが知られており,生産環境で利用するためには非再帰方式で実現しなければならない.
探索を経て、実現の構想は主に文章「2点間のすべての経路を求める遍歴アルゴリズム」から来ているが、この文の中で具体的な実現の詳細を与えていないだけで、自分で実現する必要がある.最終的に本明細書の実装は、「アルゴリズム−スケジューリングフィールドアルゴリズム(Shunting Yard Algorithm)」に記載されているような二重スタックと組み合わせて達成される.

1、アルゴリズムプロセス

次の図を例にとると、ノード3からノード6までのすべてのパスの可能なパスは8つです.
この8つのパスをどのように取得するかを具体的に説明します.
まず、メインスタックとセカンダリスタックと呼ばれる2つのスタックを用意します.

メインスタック:各要素は、現在のパス上のノードを格納するための単一ノード(Vertex)である.

サブスタック:各要素は、メインスタックに対応する要素の隣接ノードリスト(Vertex Array)を格納するために使用される.このスタックはメインスタックを補助するために使用され、その長さはメインスタックと一致する.

Step 1:スタックを建てる

v3(ノード3)をメインスタックに配置し、v3ノードの隣接ノードリスト[v1, v7]をサブスタックに配置する.
メインスタックとセカンダリスタックの圧入はスタックの長さを増加させ、私の個人的にはスタック(build stack)と呼ばれています.

Step 2:スタックの建設を続ける

スタックを構築した後、ノードリスト[v1, v7]であるセカンダリスタックを確認します.
ノードリストの最初の要素v1を取り出し、メインスタックに押し込む.残りのノードリスト[v7]を同時にサブスタックに戻します.
同時にクエリv1の隣接ノードリストは[v3, v0]であり、v3ノードはすでにメインスタックにあるため、このリストから削除する必要があり(このステップは重要である)、削除後のノードリスト[v0]をサブスタックに押し込む:
このステップはメインスタックとセカンダリスタックの長さを増加させるので、スタックの構築プロセスでもあります.

Step 3:スタックを削る

Step 2のスタック構築プロセスを続行し、メインスタックトップv 7になるまで、サブスタックのスタックトップは空のリスト[]です.
サブスタックのスタックトップは空のリスト[]であるため、スタックを構築し続けることはできません.これは、このパスが突き当りまで行ってもターゲットノードv 6が見つからないことを示しています.
この道が通じない境地を歩いて、私たちは引き返して、来たときの道の他の分かれ道を見なければなりません.
メインスタックの上部のv 7をポップアップし、サブスタックの空のリスト[]もポップアップします.
この操作により、メインスタックとセカンダリスタックの長さが減少し、このプロセスは私の個人的にはカットスタック(cutdown stack)と呼ばれます.

Step 4：最初のパスを取得する

上記のStep 2、Step 3を繰り返し、ポリシーをとります.

サブスタックトップが空でないリストであれば、スタック

を構築します.

サブスタックの上部が空のリストである限り、スタック

を削ります.
メインスタックの上部ノードがターゲットノードv6であるまで:
ここまで行って、私たちは立ち止まって観察してみると、メインスタックの内容はすでにv3からv6までの完全な経路であることがわかりました.
現在のスタックが配列である['v3', 'v1', 'v0', 'v2', 'v5', 'v6']を出力します.この配列はv3 -> v1 -> v0 -> v2 -> v5 -> v6という経路を表します.
これにより,v3からv6への経路が得られた.
自分の努力のために拍手すべきで、すでに勝利の曙光を見た.次に簡単なループを加えると、すべてのパスが取得されます.

Step 5:すべてのパスを取得する

Step 2-Step 4の手順を繰り返し、次のようにします.

サブスタックトップが空でないリストであれば、スタック

を構築します.

サブスタックの上部が空のリストである限り、スタック

を削ります.

メインスタックトップがターゲットノードである限り、パスを出力し、同時にスタック

を削る.
メインスタックが空になるまで、以上の手順を繰り返します.
スタック(build stack)とカットスタック(cutdown stack)のプロセスが進むにつれて、メインスタックとセカンダリスタックは絶えず変化し、この変化の過程でv3からv6までの経路を絶えず取得することができ、最終的にはすべての経路を取得することができる.

2、コード実現

2.1、疑似コード

上記の手順の説明に従って、文字を擬似コードに変換することが多い.

BEGIN

       
       
  
      
  
  WHILE       THEN
  
          ，       
    
    IF           THEN
                  
              ，        
        
    ELSE
        
      CONTINUE
    END IF
    
    IF        ===      THEN
            ，    
        
    END IF
    
  END WHILE
  
END

以上は無方向図を例に挙げたが,実際にはこのアルゴリズムも有方向図に適している.

2.2、効果を実現する

このダブルスタックアルゴリズムのJS実装はすでにコードライブラリss-graphに書かれており、私たちは直接それを検証し、実際の実行効果は以下の通りである.
行けるhttps://runkit.com/boycgit/ss...データエクスペリエンスの変更:

3、まとめ

最近「図」というデータ構造を復習し、過程でコードを書いて中アルゴリズムを実現しようと試みている.知識を得ることができるのは、自分で考え、まとめてこそ、その後の融通の基礎を築くことができる.
本文の学習の総括の中で、2つの体得の印象は比較的に深いです:

は再帰的に解決できる問題であり,一般にサイクル+スタック(Stack)で解決できる.

アルゴリズムがどのように実現されるか分からない場合、簡単なシーンからプレゼンテーションを始め、その法則を模索してから実現に着手する学習方法をまとめるのに適している.

図関連のアルゴリズムはまだたくさんあって、多くの経典のアルゴリズムがあって、後続の暇があればいくつかの経典のアルゴリズムを実現して整理して、互いに役に立ちます.

参考記事

Find if there is a path between two vertices in a directed graph:geeks forgeeks関連面接問題、再帰的に

を実現

Print all paths from a given source to a destination:再帰実装、すべてのパス

を検索

2 2 2点の間のすべての経路の遍歴アルゴリズムを求めます:比較的に分かりやすいです;1つの保存パスのスタック、1つの保存マークされたノードの数

以下は私の公衆番号で、よくJS(Node.js)の知識と情報を更新して、コードをスキャンして交流に注目することを歓迎します.