JavaScriptのデータ構造とアルゴリズム グラフとグラフアルゴリズム_基礎知識

グラフの定義

グラフは、有限の空ではない頂点のセットと頂点間のエッジのセットで構成されます。通常、G(V,E) のように表されます。ここで、G はグラフを表し、V はグラフ G の頂点です。セット、E はグラフ G のエッジのセットです。

有向グラフ

有向エッジ: 頂点 Vi から Vj へのエッジに方向がある場合、このエッジは有向エッジと呼ばれ、弧 (Arc) とも呼ばれ、順序ペア で表され、Vi と呼ばれます。はアークテール、Vj はアークヘッドと呼ばれます。

順序なしグラフ

無向エッジ: 頂点 Vi と Vj の間のエッジに方向がない場合、このエッジは無向エッジ (Edge) と呼ばれ、順序のないペア (Vi, Vj) で表されます。

簡単な写真

単純グラフ: グラフ構造において、頂点から頂点までの辺がなく、同じ辺が繰り返し現れない場合、そのようなグラフを単純グラフと呼びます。

グラフィック

は頂点

を表します

グラフ クラス作成の最初のステップは、頂点とエッジを保存する Vertex クラスを作成することです。このクラスの機能は、連結リストや二分探索木の Node クラスと同じです。 Vertex クラスには 2 つのデータ メンバーがあります。1 つは頂点を識別するもの、もう 1 つは頂点が訪問されたかどうかを示すブール値です。それぞれ label と wasVisited という名前が付けられます。

コードをコピーします コードは次のとおりです:

関数頂点(ラベル){
This.label = label;
}

すべての頂点を配列に保存し、グラフ クラスでは配列内の位置によって頂点を参照できます

はエッジを表します

グラフの実際の情報は「エッジ」に格納されます。これは、「エッジ」がグラフの構造を記述するためです。バイナリ ツリーの親ノードは 2 つの子ノードのみを持つことができますが、グラフの構造はより柔軟であり、頂点には 1 つのエッジまたは複数のエッジを接続できます。

グラフのエッジを表現する方法を隣接リストまたは隣接リスト配列と呼びます。頂点の隣接する頂点のリストで構成される配列を保存します

構造図

次のように Graph クラスを定義します:

コードをコピー コードは次のとおりです:

関数グラフ(v){
This.vertices = v;//頂点の最高点
This.edges = 0;
This.adj = [];
for(var i =0;I This.adj[i] = [];
This.adj[i].push('');
}
This.addEdge = addEdge;
This.toString = toString;
}

このクラスは、グラフが表すエッジの数を記録し、長さとグラフ内の頂点の数を使用して頂点の数を記録します。

コードをコピー コードは次のとおりです:

関数 addEdge(){
This.adj[v].push(w);
This.adj[w].push(v);
This.edges ;
}

ここでは、for ループを使用して配列内の各要素にサブ配列を追加し、隣接するすべての頂点を格納し、すべての要素を空の文字列に初期化します。

グラフトラバーサル

深さ優先トラバーサル

DepthFirstSearch (深さ優先検索とも呼ばれ、DFS とも呼ばれます)。

たとえば、部屋の鍵を探す場合は、部屋の隅、ベッドサイドテーブル、ベッド、ベッドの下、ワードローブ、テレビキャビネットなどを 1 つずつ検索します。 、どれも見逃さないように、すべての引き出しと収納キャビネットを調べた後、次の部屋を探します。

深さ優先検索:

深さ優先検索では、未訪問の頂点を訪問し、訪問済みとしてマークし、最初の頂点の隣接リスト内の他の未訪問の頂点に再帰的にアクセスします

配列を Graph クラスに追加します:

コードをコピー コードは次のとおりです:

this.marked = [];//訪問した頂点を保存
for(var i=0;i This.marked[i] = false;// false に初期化されます
}

深さ優先検索関数:

コードをコピー コードは次のとおりです:

関数 dfs(v){
This.marked[v] = true;
//ここでは if ステートメントは必要ありません
If(this.adj[v] != 未定義){
print("訪問した頂点: " v );
for each(this.adj[v] の var w){
If(!this.marked[w]){
This.dfs(w);
}
}
}
}

幅優先検索

幅優先検索 (BFS) は、結果を見つけるためにグラフ内のすべてのノードを体系的に拡張して検査することを目的としたブラインド検索方法です。言い換えれば、結果が存在する可能性のある場所は考慮されず、結果が見つかるまでグラフ全体が徹底的に検索されます。

幅優先検索は、以下に示すように、最初の頂点から開始し、その頂点にできるだけ近い頂点を訪問しようとします。

その動作原理は次のとおりです:

1. まず、現在の頂点に隣接する未訪問の頂点を見つけて、それらを訪問済みの頂点リストとキューに追加します。
2. 次に、グラフから次の頂点 v を取得し、それを訪問頂点リストに追加します
3. 最後に、v に隣接するすべての未訪問の頂点をキューに追加します
以下は幅優先検索関数の定義です:

コードをコピー コードは次のとおりです:

関数 bfs(s){
var queue = [];
This.marked = true;
Queue.push(s);//キューの最後に追加
While(queue.length>0){
var v = queue.shift();//キューの先頭から削除
If(v == 未定義){
print("訪問した頂点: " v);
}
for each(this.adj[v] の var w){
If(!this.marked[w]){
This.edgeTo[w] = v;
This.marked[w] = true;
queue.push(w);
}
}
}
}

最短パス

幅優先検索を実行すると、ある頂点から接続された別の頂点への最短パスが自動的に見つかります

パスを決定する

最短パスを見つけるには、ある頂点から別の頂点までのパスを記録するために幅優先検索アルゴリズムを変更する必要があります。これを 1 つの頂点から次の頂点までのすべてのエッジを保存するために必要です。配列edgeTo

コードをコピー コードは次のとおりです:

this.edgeTo = [];//この行を Graph クラスに追加します

//bfs 関数
関数 bfs(s){
var queue = [];
This.marked = true;
Queue.push(s);//キューの最後に追加
While(queue.length>0){
var v = queue.shift();//キューの先頭から削除
If(v == 未定義){
print("訪問した頂点: " v);
}
for each(this.adj[v] の var w){
If(!this.marked[w]){
This.edgeTo[w] = v;
This.marked[w] = true;
queue.push(w);
}
}
}
}

トポロジカルソートアルゴリズム

トポロジカルソートは、有向エッジが前の頂点から後の頂点を指すように、有向グラフのすべての頂点をソートします。
トポロジカル ソート アルゴリズムは BFS と似ていますが、違いは、トポロジカル ソート アルゴリズムは、訪問した頂点をすぐに出力しないことです。代わりに、現在の頂点の隣接リスト内のすべての隣接頂点を参照します。リストがスタック内で使い果たされています。

トポロジカル ソート アルゴリズムは 2 つの関数に分割されます。最初の関数は topSort() で、ソート プロセスを設定し、補助関数 topSortHelper() を呼び出して、ソートされた頂点リストを表示します。

トポロジカル ソート アルゴリズムの主な作業は、再帰関数 topSortHelper() で完了します。この関数は、現在の頂点を訪問済みとしてマークし、現在の頂点隣接リスト内の各頂点に再帰的にアクセスして、これらの頂点を訪問済みとしてマークします。最後に、現在の頂点がスタックにプッシュされます。

コードをコピーします コードは次のとおりです:

//topSort() 関数
関数topSort(){
var stack = [];
訪問した変数 = [];
for(var i =0;i 訪問[i] = false;
}
for(var i = 0;i If(visited[i] == false){
This.topSortHelper(i,visited,stack);
}
}
for(var i = 0;i If(スタック[i] !=未定義 && スタック[i] != false){
print(this.vertexList[stack[i]]);
}
}
}

//topSortHelper() 関数
関数 topSortHelper(v,visited,stack){
訪問[v] = true;
for each(this.adj[v] の var w){
If(!visited[w]){
This.topSortHelper(visited[w],visited,stack);
}
}
stack.push(v);
}