私以外にこの文章を読む人がいるかどうか分かりません...ほほほ...修正が必要な箇所があればコメントでお知らせください🙇🏻‍♀️

Graph

グラフといえば、まずExcelでよく使われる表、x軸、y軸が存在する割合反比例図などが考えられます.しかし、資料構造図によると、下図のように複数の点が線で複雑に接続されている.
1と5、あるいは1と2のように1と直接つながっている点も、1と4のように5を通ってつながっている点もあります.ここで、数値点は頂点(頂点)となり、直線は辺(幹線)となる.

グラフィック用語

undirected graph & directed graph

undirected? 方向がないの?こんなふうに混同したつもりで双方向かどうか(?)そう思うのは分かりやすいためです.付加的なイメージでは,2と3が互いにつながっている.これを無方向図と呼ぶ.しかし、1と2から見ると、1から2には幹線がありますが、2から1までの幹線はありません.このように、双方向の幹線がなく、一方向のみのものを有向図(単方向図)と呼ぶ.一方向図は完全に単行です.

self loop & cycle

self loopとは、頂点から入った幹線が直接自分に入る場合のこと.他の頂点を通らず、直接自分の身に戻る場合.上記の画像では、1はself loopを有する.
cycleは、一つの頂点から再び戻ることができれば、cycleがあると言います.

in-degree & out-degree

1つの頂点に入る、入る回数(入る回数)、退出回数(入る回数)の幹線が何本あるかを表します.

グラフィック表現

✅Adjanity(隣接):2つの頂点の間に直接の幹線がある場合、この2つの頂点は隣接する頂点です.

Adjancency matrix

隣接行列
隣接する頂点間の隣接(幹線)を表す行列は、2次元配列の様子です.つながっていれば1、つながっていなければ0で表します.上のパターンは隣接行列で表され、以下のようになります.頂点はadjMatrix[i]になり、各配列要素内で0と1で表される要素が幹線になります.
表の形式に似ていて、隣接していない情報もすべて確認できるので、便利そうに見えますが、不要な情報を読む必要があるという欠点があるかもしれません.

let adjMatrix = [
              To
     	     0  1  2   
From      0 [0, 1, 0]
	  1 [0, 0, 1]
 	  2 [1, 1, 0]
]

隣接マトリクス-JSコード実装

function createMatrix(edges) {
  // 1) 가장 큰 수를 갖는 정점 찾기
  let max = edges.flat().filter((el) => typeof el === 'number');
  max = Math.max(...max);
  // 2) 0 ~ 1)에서 찾은 정점까지의 크기를 갖는 매트릭스 만들기
  let matrix = Array(max + 1).fill(0).map((row) => Array(max + 1).fill(0));

  // 3) 정점을 만들었으니, 연결되는 간선을 만들어줌
  for(let i = 0; i < edges.length; i++) {
    let [row, col, direction] = edges[i];
    if(direction === 'directed') {
      matrix[row][col] = 1;
    }
    else if(direction === 'undirected') {
      matrix[row][col] = 1;
      matrix[col][row] = 1;
    }
  }
  return matrix;
}

let output1 = createMatrix([
	[0, 3, "directed"],
	[0, 2, "directed"],
	[1, 3, "directed"],
	[2, 1, "directed"],
]);

console.log(output1);
/**
 * [
 *  [0, 0, 1, 1],
 *  [0, 0, 0, 1],
 *  [0, 1, 0, 0],
 *  [0, 0, 0, 0]
 * ]
 */

Adjacency list

りんせつひょう
各頂点がどの頂点に隣接しているかをリスト形式で表し、リスト内の隣接する他の頂点を値とします.

let adjList = {0: [1], 1 : [2], 2 : [0, 1]};

隣接マトリクスは、すべての場合の数を格納するため、多くのメモリを消費します.メモリを効率的に使用するには、隣接するリストを使用します.

グラフィックの参照

BFS

幅優先ナビゲーション方法
1-2-3-4-5-6-7-8-9-10-11-12の順にナビゲート
これは

から始まり、近い頂点をすべて探索し、次の頂点を探索する方法です.

の2つの頂点間の最短パスを探します.

図で参照する場合は、無限ループに陥らないように、参照されたノードを表示します.

を順次格納した後、再帰を使用せずに、格納から取り出せる構造キューを先に使用する.

DFS

深度優先ナビゲーション方法DFS(深度優先検索)
1-2-5-9-10-6-3-4-7-11-8-12の順にナビゲート

自己呼び出しループアルゴリズムの形式で、ルートノードから1つの方向に歩き続け、道がなくなった場合、最寄りの分岐点に戻り、その後、1つの方向に探索する方法.

BFSより少し簡単ですが、簡単な検索ではBFSより遅いです.

図で参照する場合は、無限ループに陥らないように、参照されたノードを表示します.

のすべてのノードにアクセスできます.

Reference

image - wiki
BFS & DFS