[Algorithm] 그래프

🌼그래프(Graph)

Graph는 Vertex(정점)와 Edge(간선)로 이루어진 집합을 말한다. 이 자료구조는 G = (V, E)로 표현하며 여기서 G는 Graph 자료구조, V는 Vertex로 각 노드, E는 Edge로 각 정점들을 연결하는 선을 의미한다.

🌼그래프의 종류

각각의 그래프를 이차원 배열로 해석하기 전에 초기 그래프 배열을 다음과 같이 정의한다. 여기서 그래프라는 이차원 배열을 해석할때는 행 기준으로 열이 채워져 있으면(1) 행 노드가 열 노드가 연결되어 있는 것으로 이해한다. 아래의 예시의 노드 정보는 인접 행렬 형태로 노드의 개수가 작은 경우 사용하는 데이터 구조이다.

//노드 개수
let n = 5;
//여기서 graph[0][b] || graph[a][0] 위치는 정의는 했으나 사용하지 않는다.
let graph = Array.from({length: n + 1}, () => Array(n + 1).fill(0));

• 각 입력값의 형태

  • 연결된 노드 정보 : [[1, 2], [1, 3], [2, 4], [3, 4], [2, 5]] : [정점, 인접노드]
  • 노드 개수: 5
  • 간선 개수: 5

• 무방향 그래프: 무방향이라고 하지만 의미적으로는 양방향 그래프에 가깝다.

  • 표현 방법: graph[a][b] = 1; && graph[b][a] = 1; (양방향 체크)

• 방향 그래프: 방향 그래프는 말 그대로 이동하는 방향이 정해져 있는 것이다.

  • 표현 방법: graph[a][b] = 1; (단방향 체크)

• 각 입력값의 형태

  • 연결된 노드 정보: [[1, 2, 2], [1, 3, 4], [2, 4, 2], [3, 4, 5], [2, 5, 5]] : [정점, 인접노드, 가중치]
  • 노드 개수: 5
  • 간선 개수 : 5

• 가중치 그래프: 방향 그래프와 비슷하지만 이동할 때 가중치가 주어진다. (Ex: 지역간 택배비 차이)

  • 표현 방법: graph[a][b] = 가중치;

출처: 인프런-자바스크립트 알고리즘 문제풀이