Graph

既存のグラフィックは、x軸とy軸で定義される空間内の変数値の集合です.資料構造では、グラフはクモの巣です.図は、各資料が標準で接続されている.ネットはグラフともいえる.各サイトには、ハイパーリンクで相互に接続された構造があります.

Vertex(頂点)とEdge(幹線)

頭の中でネットを描き、各サイトがハイパーリンクでつながっている.データを含むサイトは各サイトの頂点であり、これらのサイトを結ぶハイパーリンクは幹線である.簡潔な可視化のために、頂点は通常体積点(実心円)で表され、幹線は各円を結ぶ線で表される.

接続が重要です!

グラフ資料構造型では,接続が重要である.他の頂点に関連付けられている頂点はどれですか?もしつながっていたら、一方向ですか、それとも双方向ですか.一方的であれば、どこからどこに接続しますか?順序が重要なStackやQueueと比較して,図形は非線形構造であり,順序ではなく接続の有無の重要な資料である.Googleで検索する場合、検索結果をクリックしてそのサイトに移動できず、検索結果だけを順番に表示してしまうと、何の意味があるのでしょうか?

むきず

双方向接続は、一定の方向がないことを意味します.方向は重要ではありません.しかし、一方向接続の方向は重要です!

入場回数

頂点には複数の接続があります.このとき進入する幹線の数を進入車数、外に出る幹線の数を進入車数と呼ぶ.無方向図では区別できません.このとき、頂点に隣接する頂点の数を頂点数と呼ぶ.

に近づく

幹線で直接接続された、隣接する頂点と呼ばれます.せってん

マグネチックリング

頂点から出発した幹線はすぐに自分の体に戻った.このとき、幹線は他の頂点を通過しません.磁気リングオブジェクトの頂点が線形構造の資料で構成されている場合,意味がある.円形のキューからなるグラフを考えるとわかります.

サイクル

1つの頂点から頂点に戻ることができる場合は、ループが存在します.

重み付け

幹線には重み付けがある.例えば、1つの頂点から同じ頂点に到達するルートが2つあり、幹線の重み付けで幹線を通過するのに要する時間を表すとすると、最短時間で到達するルートを選択するためには、この重み付けを考慮すべきである.重み付けは複数の概念を表すことができる.

グラフィックの表現

隣接行列

グラフはマトリクスで表すことができます.JavaScriptでは、2 D配列が使用されます.配列は頂点数で、配列を構成する各インデックスの内部配列は頂点数で、0と1で構成されています.

//정점이 3개인 그래프의 인접 행렬
const matrixGraph = [ 
[0, 0, 1], 
[0 ,1, 0], 
[1, 0, 0]
]

0は接続されていないことを示し、1は接続を示します.グラフでは、順序はあまり意味がありません.ただ、区別を容易にするために、インデックス番号で区別します.

MatrixGraph[0]の2番のインデックスは1です.これは、幹線が第1の頂点から第3の頂点方向に接続されていることを意味する.出場回数は1つ.

MatrixGraph[1]の1番のインデックスは1です.これは、幹線が第2の頂点から第2の頂点方向に接続されていることを意味する.隣接マトリクスでは、磁気リングも表現できます!出場回数は1つ.

MatrixGraph[2]の0番インデックスは1です.これは、幹線が3番目の頂点から1番目の頂点方向に接続されていることを意味します.頂点1と頂点3は双方向に接続されている.出場回数は1つ.

隣接行列の利点は,頂点間の関係を容易に把握できることである.

りんせつひょう

隣接マトリクスで使用する例を隣接リストで表しましょう.(頂点の配列内の各頂点の名前の順序)

頂点1→頂点3→頂点1

頂点2→頂点2→…

頂点3→頂点1→頂点3

隣接マトリクスに比べて、隣接リストで使用されるメモリは少なくなります.隣接マトリクスはすべての場合の接続数を格納するためである.簡単に言えば、隣接マトリクスは頂点個数の平方メモリ空間を必要とする.また,隣接表は周期を把握しやすい.
グラフの閲覧方法は代表的なBFS,DFSがある.ナビゲーション方法については、ツリー構造で詳しく説明してください.