グラフィック

これは

頂点と頂点とを結ぶ幹線からなる非線形資料構造である.

頂点と幹線の集合で表現できます.
頂点.ノード(node)とも呼ばれ、頂点にデータが格納されます.
幹線.リンクとも呼ばれ、ノード間の関係を表します.

特長

頂点には複数の幹線があります.

は、方向図と無方向図に大きく分けることができる.

幹線は重み付けできます.

サイクル(パスの始点と終点が同じ場合)が発生する可能性があります.

実施方法

グラフィックを実現する方法としては,隣接マトリクス法と隣接リスト法がある.両実現方式にはそれぞれメリットとデメリットがあり,隣接表形式を採用することが多い.

1.隣接行列

グラフィックのノードを2 D配列に設定します.

各頂点の接続情報を0と1で表します.

const graph = Array.from(new Array(7), () => new Array(7).fill(0));

graph[1][2] = 1;
graph[1][3] = 1;
graph[2][1] = 1;
graph[2][3] = 1;
graph[2][4] = 1;
graph[3][1] = 1;
graph[3][2] = 1;
graph[3][4] = 1;
graph[3][5] = 1;
graph[4][2] = 1;
graph[4][3] = 1;
graph[4][5] = 1;
graph[4][6] = 1;
graph[5][3] = 1;
graph[5][4] = 1;
graph[6][4] = 1;

for(let i = 1; i < graph.length; i++) {
  console.log(graph[i].slice(1).join(' ')); // 0번 정점이 없으므로 제거
}

// 결과 

// 0 1 1 0 0 0
// 1 0 1 1 0 0
// 1 1 0 1 1 0
// 0 1 1 0 1 1
// 0 0 1 1 0 0
// 0 0 0 1 0 0

長所

2 D配列にはすべての頂点の幹線情報が含まれているので,配列の位置を決定すると,2つの頂点の接続情報を参照する際にO(1)の定数時間複雑度を用いることができる.

実現は比較的簡単である.

短所

すべての頂点に幹線情報を入力する必要があるため,隣接行列の作成にはO(n^2)の時間的複雑さが必要である.

無条件で2 D配列が必要で、メモリの浪費が深刻です.

2.隣接表

図面のノードを接続リストとして表示します.

主に頂点の接続リストの配列を確立することによって関係を確立することによって体現される.

const graph = Array.from(new Array(7), () => []);

graph[1].push(2);
graph[1].push(3);
graph[2].push(1);
graph[2].push(3);
graph[2].push(4);
graph[3].push(1);
graph[3].push(2);
graph[3].push(4);
graph[3].push(5);
graph[4].push(2);
graph[4].push(3);
graph[4].push(5);
graph[4].push(6);
graph[5].push(3);
graph[5].push(4);
graph[6].push(4);

console.log(graph); // 0번 정점은 없으므로 1 인덱스(정점) 배열부터 ~ 6까지의 연결정보

長所

頂点の接続情報をブラウズする場合,O(n)の時間的複雑さ.(n:幹線数)

必要なスペースしか使用しないため、スペースの無駄が少ない.

短所

隣接するマトリクスに比べて、2つの特定のポイントが接続されているかどうかをナビゲートするのに時間がかかります.(接続リストのナビゲーション速度が配列より遅い)

実施が困難である.

参考資料

https://coding-factory.tistory.com/610

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html