図の定義
グラフは、頂点間の有限でない頂点のセットと頂点間のエッジのセットで構成されています。通常、それは次のように表されます：g（v、e）はグラフを表し、vはグラフgの頂点のセットであり、eはグラフgのエッジのセットです。
指示グラフ
指向エッジ：Vertex VIからVJへのエッジに方向がある場合、このエッジは方向のエッジと呼ばれ、これもARC（ARC）になります。注文<vi、vj>で表されます。 VIはアークテールと呼ばれ、VJはアークヘッドと呼ばれます。
乱れた図
無向エッジ：VIからVJへの頂点の間のエッジに方向がない場合、このエッジは無向エッジ（エッジ）と呼ばれ、順序付けられていないペア（VI、VJ）で表されます。
簡単な写真
簡単な図：グラフ構造では、それ自体の端に頂点がなく、同じエッジが繰り返し表示されない場合、この写真は単純な図と呼ばれます。
画像クラス
頂点を示します
グラフクラスを作成する最初のステップは、頂点とエッジを保存する頂点クラスを作成することです。このクラスは、リンクされたリストおよびバイナリ検索ツリーのノードクラスと同じように機能します。頂点クラスには2つのデータメンバーがあります。1つは頂点を識別し、もう1つはアクセスしたかどうかを示します。それらはラベルという名前で、それぞれ訪問されました。
コードコピーは次のとおりです。
関数頂点（ラベル）{
this.label = label;
}
すべての頂点を配列に保存し、グラフクラスでは、配列内の位置でそれらを参照できます
エッジを示します
グラフの実際の情報は、グラフの構造を記述するため、「エッジ」に保存されます。バイナリツリーの親ノードには2つの子ノードしかありませんが、グラフの構造ははるかに柔軟です。頂点には、1つのエッジまたは複数のエッジが接続できます。
グラフのエッジを表す方法を使用して、隣接テーブルまたは隣接テーブルアレイになります。頂点の隣接する頂点のリストで構成される配列を保存します
グラフを作成します
次のグラフクラスを定義します。
コードコピーは次のとおりです。
関数グラフ（v）{
this.vertices = v; //ハイポイントへの頂点
this.edges = 0;
this.adj = [];
for（var i = 0; i <this.vertices; ++ i）{
this.adj [i] = [];
this.adj [i] .push（ ''）;
}
this.addedge = addidge;
this.toString = toString;
}
このクラスは、グラフがいくつのエッジを表し、グラフの頂点を使用して使用して、頂点の数を記録する数を記録します。
コードコピーは次のとおりです。
function addegge（）{
this.adj [v] .push（w）;
this.adj [w] .push（v）;
this.edges ++;
}
ここでは、forループを使用して、配列内の各要素のサブアレイを追加して、すべての隣接する頂点を保存し、すべての要素を空の文字列に初期化します。
写真のトラバーサル
深さ優先度トラバーサル
DepthFirstSearchは、DepthFirstSearchとしても知られていますが、略してDFSと呼ばれます。
たとえば、部屋でキーを探して、どの部屋を開始しても、部屋の角、ナイトスタンド、ベッドサイドテーブル、ベッドの下、ワードローブ、テレビキャビネットなどを検索できます。すべての引き出しと収納キャビネットを検索した後、次の部屋を検索します。
深さの優先検索：
深度検索とは、訪問されていない頂点にアクセスし、アクセスとしてマークする頂点にアクセスし、最初の頂点の隣接テーブルで訪問されていない他の頂点に再帰的にアクセスすることを意味します。
グラフクラスに配列を追加します。
コードコピーは次のとおりです。
this.marked = []; //訪問した頂点を保存します
for（var i = 0; i <this.vertices; ++ i）{
this.marked [i] = false; // falseに初期化
}
深さfirst検索関数：
コードコピーは次のとおりです。
関数dfs（v）{
this.marked [v] = true;
//ここではステートメントが必要ない場合
if（this.adj [v]！= undefined）{
print（ "訪問頂点：" + v）;
それぞれ（this.adj [v]のvar w）{
if（！this.marked [w]）{
this.dfs（w）;
}
}
}
}
幅広い検索
Browness-First Search（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 == undefined）{
print（ "訪問頂点：" + v）;
}
それぞれ（this.adj [v]のvar w）{
if（！this.marked [w]）{
this.edgeto [w] = v;
this.marked [w] = true;
queue.push（w）;
}
}
}
}
最短パス
幅最初の検索を実行すると、ある頂点から別の頂点までの最短パスが自動的に見つかります
パスを決定します
最短のパスを見つけるには、幅最初の検索アルゴリズムを変更して、ある頂点から別の頂点へのパスを記録する必要があります。次の頂点のすべてのエッジを1つの頂点から保存するための配列が必要です。この配列Edgetoに名前を付けます
コードコピーは次のとおりです。
this.edgeto = []; //この行をグラフクラスに追加します
// BFS関数
関数bfs（s）{
var queue = [];
this.marked = true;
queue.push（s）; //キューの最後に追加します
while（queue.length> 0）{
var v = queue.shift（）; //チームリーダーから削除します
if（v == undefined）{
print（ "訪問頂点：" + v）;
}
それぞれ（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（）関数
function topsort（）{
var stack = [];
var visited = [];
for（var i = 0; i <this.vertices; i ++）{
訪問[i] = false;
}
for（var i = 0; i <this.vertices; i ++）{
if（訪問[i] == false）{
this.topsorthelper（私、訪問、スタック）;
}
}
for（var i = 0; i <stack.length; i ++）{
if（stack [i]！= undefined && stack [i]！= false）{
print（this.vertexlist [stack [i]]）;
}
}
}
// topsorthelper（）関数
function topsorthelper（v、訪問、スタック）{
訪問[v] = true;
それぞれ（this.adj [v]のvar w）{
if（！訪問[w]）{
this.topsorthelper（訪問[w]、訪問、スタック）;
}
}
stack.push（v）;
}