자바스크립트 알고리즘 강의를 듣고 내용을 정리했습니다.

그래프

무방향 그래프

무방향 그래프는 1 -> 2, 2 -> 1 처럼 방향성이 없어서 중복이 가능하므로 이차원 배열을 노드의 숫자만큼 행과 열을 생성한 다음 아래와 같이 행과 열을 바꾸어 1로 체크 표시를 하여 DFS를 진행해 경로를 찾습니다.

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;
}

방향 그래프

무방향 그래프와 동일한 원리이지만, 방향성이 존재하여 1 -> 2는 되지만 2 -> 1은 불가능하기 때문에 입력된 행과 열에 해당하는 이차원 배열만 1로 체크해서 DFS를 진행합니다.

let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
for (let [a, b] of arr) {
  graph[a][b] = 1;
}

가중치 방향 그래프

방향 그래프에 방향 이동시에 가중치가 주어지게 되면, 이차원배열에 가중치를 추가로 넣어 시작지점, 종료지점, 가중치로 반복문을 통해 빈 이차원배열에서 해당 x,y좌표에 값으로 가중치를 넣어서 계산을 해주면 됩니다.

let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));

// [x,y,가중치]
let addValue = [[1,2,2],[1,3,4], [3,4,5], [4,2,2], [2,5,5]] 

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