[ 자바스크립트(JavaScript) ] section09 - 1 - 그래프와 인접행렬

📍 section09 - 1 - 그래프와 인접행렬

이번 섹션은 그래프와 탐색(DFS, BFS)에 대해서 배운다. 지금은 문제를 풀지 않고 그래프에 대해 간단하게 알아보는 시간을 가져보자. 그래프는 다음과 같이 이루어진다.

 

1. Vertex: 정점, 노드
2. Edge: 노드와 노드를 연결하는 간선
3. graph: 2차원 배열에서는 index가 정점(vertex) 번호다.

 

그래프의 종류는 3가지가 있다. 입력이 주어질 때 graph별로 어떻게 입력하는지 코드로 나타냈다. (여기서는 인접 행렬로 표현함)

 

1. 무방향 그래프(unDirected Graph): 방향이 없는 그래프 즉, 양방향인 그래프다. 입력은 보통 [a, b] 형태로 주어지는데 여기서 graph[a][b]=1, graph[b][a]=1을 모두 수행한다.

 

 

// 인접행렬
let node = 5;
let edge = 5;

console.log(unDirectedGraph(node, edge));

function unDirectedGraph(node, edge){
  let graph = Array.from(Array(node+1), () => Array(edge+1).fill(0));
  let input = [[1, 2], [1, 3], [2, 4], [3, 4], [2, 5]];

  for (let [a, b] of input){
    graph[a][b] = 1;
    graph[b][a] = 1;
  }

  return graph;
}

👉🏽 [
  [ 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 1, 1, 0, 0 ],
  [ 0, 1, 0, 0, 1, 1 ],
  [ 0, 1, 0, 0, 1, 0 ],
  [ 0, 0, 1, 1, 0, 0 ],
  [ 0, 0, 1, 0, 0, 0 ]
]

 

2. 방향 그래프(directed Graph): 방향이 정해져 있는 그래프다. 무방향 그래프와는 달리 정점이 가리키는 방향만 graph에 입력한다.

 

 

// 인접행렬
console.log(directedGraph(node, edge));

function directedGraph(node, edge){
  let graph = Array.from(Array(node+1), () => Array(edge+1).fill(0));
  let input = [[1, 2], [1, 3], [2, 4], [3, 4], [2, 5]];

  for (let [a, b] of input){
    graph[a][b] = 1;
  }

  return graph;
}

👉🏽 [
  [ 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 1, 1, 0, 0 ],
  [ 0, 0, 0, 0, 1, 1 ],
  [ 0, 0, 0, 0, 1, 0 ],
  [ 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0 ]
]

 

3. 가중치 방향 그래프(weighted directed Graph): 방향 그래프이면서 가중치도 같이 나타낸 그래프이다. 한 도시에서 다른 도시로 이동할 때 드는 비용과 같은 문제에서 등장한다. 입력을 a, b, c로 받아 graph[a][b]=c 처럼 비용까지 같이 graph에 입력해야한다.

 

 

// 인접행렬
console.log(weightedDirectedGraph(node, edge));

function weightedDirectedGraph(node, edge){
  let graph = Array.from(Array(node+1), () => Array(edge+1).fill(0));
  let input = [[1, 2, 2], [2, 5, 5], [3, 4, 5], [1, 3, 4], [4, 2, 2]];

  for (let [a, b, c] of input){
    graph[a][b] = c;
  }

  return graph;
}

👉🏽 [
  [ 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 2, 4, 0, 0 ],
  [ 0, 0, 0, 0, 0, 5 ],
  [ 0, 0, 0, 0, 5, 0 ],
  [ 0, 0, 2, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0 ]
]

 

728x90

 

위에서는 인접 행렬로 나타냈는데, 그래프의 값을 나타낼 때는 인접 행렬과 인접 리스트의 방식이 있다. 각각의 특징은 다음과 같다.

 

 

1. 인접행렬(adjacency-matrix): 노드와 간선의 정보를 행렬로 표현하는 방법, 간선의 개수와 상관없이 모든 정점을 표현해야 하기 때문에 정점의 개수가 많을수록 메모리 사용량이 늘어난다. 가중치를 방향그래프는 인접 행렬로 나타낸다. 무방향, 방향성그래프 문제를 풀 때 정점의 갯수가 10,000 이하라면 인접행렬로 풀자.

 

// graph에 값을 입력하는 방법
let n = 5;
let m = 9;
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;
}

// 방향 그래프
for (let [a, b] of arr){
    graph[a][b]=1;
}

// 가중치 방향 그래프
let graph = [[1, 2, 2], [2, 5, 5], [3, 4, 5], [1, 3, 4], [4, 2, 2]];

for (let [a, b, c] of arr){
    graph[a][b]=c;
}

 

2. 인접리스트(adjacency-list): 노드와 간선의 정보를 리스트 형태로 표현하는 방법, 연결된 간선만 표시하기 때문에 인접 행렬보다 비교적 간단하다. 정점의 순서는 꼭 오름차순이 아니어도 상관없다. 인접 리스트로 문제를 풀 때는 정점의 개수만큼 반복문을 돌리는것이 아니라 간선의 갯수 graph[v].length 만큼 반복문을 돌려야 실행 속도를 높일 수 있다. 인접 리스트에 있는 정점은 필수로 한 번씩 들려야 하는 정점이므로 (왜냐하면 이미 연결되어있는 정점만 표시하기 때문) 조건문에 graph[v][i]로 값을 확인하는 대신 visited 여부만 확인해주면 된다. 정점의 개수가 10,000 이상일 때는 인접 리스트를 사용하자.

 

// graph에 값을 입력하는 방법
let n = 5;
let m = 9;
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());

// 방향 그래프
for (let [a, b] of arr){
    graph[a].push(b);
}

console.log(graph)
👉🏽 [ [], [ 2, 3, 4 ], [ 1, 3, 5 ], [ 4 ], [ 2, 5 ], [] ]