[JS] 그래프 순회 - DFS,BFS

❗️그래프 (Graph)

• 노드와 노드간의 연결로 이루어진 데이터 구조
• 정점(Vertex)와 간선(Edge)로 구성
• 순회하는 대표적인 방법 : DFS,BFS

✅ 그래프 표현 방법 - 인접행렬 vs 인접리스트

인접행렬

• 인접 행렬의 경우 모든 간선을 표현해 간선이 적은 그래프에서 효율 떨어짐
• 실제론 간선이 존재하지 않는 데이터도 순회해서 순회가 느림

let graph = Array.from(Array(N + 1), () => []);
arr.forEach((el) => {
  let [from, to] = el;
  graph[from].push(to);
  graph[to].push(from);
});
graph.forEach((el) => {
  el.sort((a, b) => a - b);
});

인접리스트

• 특정 간선을 확인하기 어려움

❗️ DFS (깊이 우선 탐색)

• 시작 정점에서 가능한 가장 아래까지 깊이 탐색
• 재귀나 반복을 이용해서 구현

1. 정점을 인자로 받는 재귀 함수를 만듬
2. 정점을 방문 처리
3. 정점의 각 인접점에 대해 방문하지 않은 접점이면 재귀 함수 호출

let visitedDFS = Array(N + 1).fill(0);
visitedDFS[0] = 1;
let result = [];
function DFS(start) {
  visitedDFS[start] = 1; // 시작할때 방문처리
  result.push(start);
  for (next of graph[start]) {
    if (!visitedDFS[next]) {
      DFS(next);
    }
  }
}
DFS(V);
console.log(`DFS : ${result}`); // [3,1,2,5,4]

❗️ BFS (너비 우선 탐색)

• 시작 정점에서 정점의 각 인접점들을 먼저 탐색
• 큐를 이용해서 구현
• 각 정점을 최단경로로 방문 (최단거리를 구할때 사용)

1. 큐를 생성하고 시작 정점을 넣음
2. 시작 접점을 방문 처리
3. 큐에서 접점을 꺼내 방문하지 않으면 방문처리
4. 접점의 각 인접점에 대해 방문하지 않은 인접점을 큐에 넣음
5. 큐가 빌때까지 계속 반복

let visitedBFS = Array(N + 1).fill(0);
visitedBFS[0] = 1;
let result2 = [];
let queue = [V];
visitedBFS[V] = 1;

while (queue.length > 0) {
  let cur = queue.shift();
  result2.push(cur);
  for (next of graph[cur]) {
    if (!visitedBFS[next]) {
      queue.push(next);
      visitedBFS[next] = 1; // 인접노드을 찾을때 방문처리
    }
  }
}
console.log(`BFS : ${result2}`); // [3,1,4,2,5]

❗️BFS의 시간초과

• javascript의 경우 shift연산의 시간복잡도가 높아 시간초과 발생 가능
• 직접 구현해서 사용해야함

✅ Queue의 구현

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }
  isEmpty() {
    return this.size === 0;
  }
  push(data) {
    let node = new Node(data);
    if (this.isEmpty()) {
      this.front = node;
      this.rear = node;
    } else {
      let cur = this.rear;
      cur.next = node;
      this.rear = node;
    }
    this.size++;
  }
  shift() {
    if (this.isEmpty()) return;
    let returnValue = this.front;
    this.front = this.front.next;
    this.size--;

    return returnValue.data;
  }
}