Udemy - 그래프 순회(DFS/DFS)

그래프 순회

그래프 순회는 우리의 일상 생활에서 굉장히 많이 활용될 수 있는 알고리즘 중 하나다.

대표적인 예로, 길 찾기가 있다. 특정 노드(시작점)에서 목적지로 갈 수 있는 최단거리 등을 계산하는데 활용될 수 있기 때문이다. 뿐만 아니라, 페이스북이나 인스타그램에서 처럼, 친구/팔로우 관계 등을 관리하는데 사용될 수도 있다. (연관 데이터 추천도 굉장히 많이 활용됨)

이러한 그래프 순회 방식에는 크게 두 가지의 방식이 존재한다. BFS와 DFS다. 이는 이전 트리 순회 포스팅에서 다뤘던 내용이기도 하고, 기본적인 핵심 개념은 거의 같다.

---

DFS (깊이 우선 탐색)

재귀 방식 순회

class Graph {
  constructor() {
    this.list = {};
  }
  DFS(start) {
    // 방문한 노드가 담길 result
    const result = [];
    // 방문한 노드의 값이 true or false로 저장됨
    const visited = {};
    // dfs()는 내부함수이기 때문에 아래와 같이 this를 명시해줘야 함
    const list = this.list;
    function dfs(v) {
      // 존재하지 않는 값이 들어오면 null처리
      if (!v) return null;
      // 방문 기록을 아래와 같이 기록
      result.push(v);
      visited[v] = true;
      // 현재 Vertex의 배열을 forEach로 각각 접근 -> 아직 그 안의 요소들이 탐색되기 전이라면?
      list[v].forEach((li) => {
        // 재귀 시작
        if (!visited[li]) return dfs(li);
      });
    }
    dfs(start);
    return result;
  }
}

반복적 방식 순회 (배열 사용)

class Graph {
  constructor() {
    this.list = {};
  }
  DFS(start) {
    // 반복문을 사용한 DFS에서는 stack이 사용된다.
    const stack = [start];
    const result = [];
    const visited = {};
    // 첫 vertex에 대해서 true를 적용해준다.
    visited[start] = true;
    let currentVertex;
    while (stack.length) {
      // currentVertex는 stack의 끝 vertex
      currentVertex = stack.pop();
      // 해당 vertex를 result에 push
      result.push(currentVertex);
      // 그리고 그 vertex의 인접 vertex들을 순회한다!
      this.list[currentVertex].forEach((v) => {
        if (!visited[v]) {
          visited[v] = true;
          stack.push(v);
        }
      });
    }
    return result;
  }
}

---

BFS (너비 우선 탐색)

반복문 활용 방식을 사용했다.
사실 위의 DFS 반복문 활용 방식과 거의 동일하나, queue를 사용한다는 차이점이 있다.

class Graph {
  constructor() {
    this.list = {};
  }
  BFS(start) {
    const queue = [start];
    const visited = {};
    const result = [];
    visited[start] = true;
    let currentVertex;
    while (queue.length) {
      currentVertex = queue.shift();
      result.push(currentVertex);
      this.list[currentVertex].forEach((li) => {
        if (!visited[li]) {
          queue.push(li);
          visited[li] = true;
        }
      });
    }
    return result;
  }
}

---