JavaScriptでのグラフの実装

グラフは、一連の 頂点 (ノードとも呼ばれます) とそれらの間の関係 (またはエッジ) を表す非線形データ構造です。頂点はエンティティまたはオブジェクトを表し、edges は頂点間の関係または接続を表します。グラフを使用すると、ソーシャル ネットワーク、交通システム、情報フローなど、さまざまな種類の関係をモデル化できます。

グラフには、有向グラフ (有向グラフとも呼ばれます) と 無向グラフの 2 つの主なタイプがあります。有向グラフでは、エッジは 1 つの方向を持ち、一方向、つまり開始頂点から終了頂点までのみ移動できます。無向グラフでは、エッジに方向がなく、両方向に横断できます。

JavaScript CTU の実装

グラフは、隣接行列または隣接リストを使用して実装できます。ここでは、隣接リストを使用して JavaScript でグラフを実装します。

チャートクラスの作成

ここでは、グラフィックス クラスのブループリントを作成します。

リーリー

頂点を追加する

この関数は、adjacencyList オブジェクトに新しいキーを作成し、その値として空の配列を与えることによって、グラフに新しい頂点 (またはノード) を追加します。新しい頂点はキーとして機能し、空の配列はその近傍を格納するために使用されます。

リーリー

エッジを追加

この関数は、2 つの頂点の間に新しいエッジを追加します。これは、vertex1 と vertex2 の 2 つのパラメータを受け入れ、vertex2 を vertex1 の近傍配列に追加し、その逆も同様です。これにより、2 つの頂点間に接続が作成されます。

リーリー

チャートを印刷

この関数は、チャートをコンソールに記録します。これは、adjacencyList オブジェクト内の各頂点を反復処理し、頂点とその近傍を記録します。

リーリー ＃＃＃例＃＃＃

次の例では、グラフを定義し、グラフに頂点とエッジを追加します。最後にグラフを印刷します。

リーリー ＃＃＃出力＃＃＃ リーリー

エッジを削除

この関数は 2 つの頂点間のエッジを削除します。これは 2 つの引数、vertex1 と vertex2 を受け取り、vertex1 の近傍配列から vertex2 をフィルターで除外し、その逆も同様です。

リーリー

頂点を削除

この関数はグラフから頂点を削除します。これは頂点引数を受け取り、まずその頂点に接続されているすべてのエッジを削除します。次に、adjacencyList オブジェクトからキーを削除します。

リーリー ＃＃＃例＃＃＃

次の例では、グラフを定義し、頂点とエッジを追加してから、グラフを印刷します。グラフからエッジ AC を削除し、最後に結果のグラフを印刷します。

リーリー ＃＃＃出力＃＃＃ リーリー

グラフ走査方法

グラフ トラバーサルとは、グラフのすべての頂点 (またはノード) を訪問し、それらに関連付けられた情報を処理するプロセスを指します。グラフ トラバーサルはグラフ アルゴリズムにおける重要な操作であり、2 つのノード間の最短パスの検索、サイクルの検出、接続されたコンポーネントの検索などのタスクに使用されます。

グラフの走査には主に 2 つの方法があります:幅優先検索 (BFS) と深さ優先検索 (DFS) です。

A. 幅優先検索 (BFS)

これは、breadthFirstSearch() 関数を使用して実装されます。この関数は幅優先検索アルゴリズムを実装し、開始頂点である start パラメーターを受け取ります。訪問する頂点を追跡するためにキューを使用し、訪問した頂点を保存するために結果配列を使用し、すでに訪問した頂点を追跡するために訪問オブジェクトを使用します。この関数はまず開始頂点をキューに追加し、それを訪問済みとしてマークします。次に、キューが空でない場合、キューから最初の頂点を取得し、それを結果配列に追加し、訪問済みとしてマークします。次に、未訪問の近隣ノードをすべてキューに追加します。このプロセスは、すべての頂点が訪問され、結果の配列が BFS の結果として返されるまで続きます。

リーリー

B.深さ優先検索

深さ優先検索メソッドは、頂点を引数として受け取る再帰内部関数 dfs を使用して DFS アルゴリズムを実装します。この関数は、訪問されたオブジェクトを使用して訪問された頂点を追跡し、訪問された各頂点を結果配列に追加します。この関数はまず、現在の頂点を訪問済みとしてマークし、それを結果配列に追加します。次に、現在の頂点のすべての近傍を反復処理し、未訪問の近傍ごとに dfs 関数を再帰的に呼び出します。このプロセスは、すべての頂点が訪問され、結果の配列が DFS の結果として返されるまで続きます。

リーリー ＃＃＃例＃＃＃

次の例では、幅優先検索 (BFS) と深さ優先検索 (DFS) を示します。

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

グラフは、オブジェクト間の関係や接続を表すために使用できる便利なデータ構造です。 JavaScript でのグラフの実装は、隣接リストや隣接行列の使用など、さまざまな手法を使用して実行できます。この回答で説明されている Graph クラスは、隣接リスト表現を使用します。各頂点はオブジェクト内のキーとして保存され、対応するエッジは配列内のそのキーの値として保存されます。

Graph クラスは、グラフに頂点とエッジを追加し、グラフを印刷し、深さ優先検索と幅優先検索のトラバーサルを実行するためのメソッドを実装します。

以上がJavaScriptでのグラフの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。