그래프 2) 방향 그래프, 무방향 그래프, 가중치 방향그래프 정리

방향 그래프(directed graph)와 무방향 그래프(undirected graph)는 이동방향의 유무 차이로 구분한다.

방향 그래프는 이동할 수 있는 방향이 정해져있고 무방향은 명칭대로 방향이 없어 양쪽 다 가능하다.

// 방향 그래프
let arr = [[1, 2],[1, 3],[1, 4],[2, 1],[2, 3],[2, 5],[3, 4],[4, 2],[4, 5]];
let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
for (let [a, b] of arr) { // arr 값 1개 씩 탐색
  graph[a][b] = 1; // 방향 그래프에서 graph arr 에 1로 체크
} // 1로 체크되어 있으면 갈 수 있는 방향인 것
//console.log(graph)
/*         1  2  3  4  5
0: (6) [0, 0, 0, 0, 0, 0]
1: (6) [0, 0, 1, 1, 1, 0]
2: (6) [0, 1, 0, 1, 0, 1]
3: (6) [0, 0, 0, 0, 1, 0]
4: (6) [0, 0, 1, 0, 0, 1]
5: (6) [0, 0, 0, 0, 0, 0]
*/

// 무방향 그래프
let arr = [[1, 2],[1, 3],[1, 4],[2, 1],[2, 3],[2, 5],[3, 4],[4, 2],[4, 5]];
let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
for (let [a, b] of arr) {
  graph[a][b] = 1;
  graph[b][a] = 1; // 무방향은 양쪽 다 갈 수 있다
//console.log(graph)
/*         1  2  3  4  5
0: (6) [0, 0, 0, 0, 0, 0]
1: (6) [0, 0, 1, 1, 1, 0]
2: (6) [0, 1, 0, 1, 1, 1]
3: (6) [0, 1, 1, 0, 1, 0]
4: (6) [0, 1, 1, 1, 0, 1]
5: (6) [0, 0, 1, 0, 1, 0]
*/

 

가중치 그래프(weighted graph)는 edge가 값(value)나 비용(cost)를 가지고 있는 경우의 그래프다.

// 가중치 방향그래프
let arr = [[1, 2, 2],[1, 3, 4],[2, 5, 5],[3, 4, 5],[4, 2, 2]];
let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
for (let [a, b] of arr) {
  graph[a][b] = c; // 가중치를 넣어주면 된다
//console.log(graph)
/*         1  2  3  4  5
0: (6) [0, 0, 0, 0, 0, 0]
1: (6) [0, 0, 2, 4, 0, 0]
2: (6) [0, 0, 0, 0, 0, 5]
3: (6) [0, 0, 0, 0, 5, 0]
4: (6) [0, 0, 2, 0, 0, 0]
5: (6) [0, 0, 0, 0, 0, 0]
*/