4.10Graph Traversal

그래프 데이터를 탐색하는 두 가지 방법(DFS, BFS) 구현하기

Graph Traversal

지난번 포스팅에서 살펴봤듯이, 그래프는 SNS 네트워킹, 길 찾기, 추천 시스템 등에 빈번하게 쓰이는 데이터 구조다. 예를 들어, 아래와 같은 데이터 구조가 있다면 Tim이 누구를 '알 수도 있는지' 데이터를 근거로 하여 정량적 수치로 파악할 수 있다.

Tree Traversal과 마찬가지로, 그래프 탐색 또한 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(Breadth-First Search)이 있다.

깊이 우선 탐색

트리와 달리, 그래프는 루트 노드가 없다. 깊이 우선 탐색이 루트 노드로부터 먼 노드부터 탐색하는 방법이라는 사실을 생각해보면, 그래프에서의 깊이 우선 탐색은 어떨까?

그래프에서도 탐색은 기준이 되는 노드가 있어야 한다. 이 노드는 탐색을 시작하는 노드로, 앞서 Tim에게 친구를 추천해주는 그래프 탐색이라면 Tim이 기준 노드고, 현재 위치에서 특정 위치로 가는 길을 찾는 그래프 탐색이라면 현재 위치가 기준 노드다.

따라서 그래프에서의 깊이 우선 탐색은 기준이 되는 노드로부터 이웃이 되는 노드로 가고, 그 노드의 이웃이 되는 노드로 가고... 하는 방식으로 탐색을 하는 방식이다.

다만, 트리와 달리 그래프에선 부모-자식 관계가 없기 때문에 한번 거쳤던 정점을 기억하고 있어야만 한다. 예를 들어, 아래의 그래프에서 A부터 시작해 깊이 우선 탐색을 한다고 해보자.

A에서 시작해 B로 간다면, 고민없이 D로 가면 될 것 같지만, 만약 A를 이미 거쳤다는 정보가 없다면 B 정점(vertex)는 A와 D를 이웃하고 있다는 정보를 가지고 있을 것이므로 A 또는 D로 이동할 수 있다.

그래프에서 깊이 우선 탐색은 재귀적으로 하는 방법과 반복적으로 하는 방법 두 가지가 있다.

1. DFS 구현하기-재귀

재귀적으로 DFS를 구현하는 수도코드를 작성한다면 아래와 같을 것이다:

시작 정점을 받아 DFS를 수행하는 함수를 선언한다.
최종 탐색 결과를 반환할 배열과, 이미 방문한 데이터를 저장해둘 객체를 만든다.
재귀적으로 실행할 헬퍼 함수를 선언한다.
- 만약 시작 정점이 고립되어 있다면(빈 배열이라면) 그냥 반환한다.
- 시작 정점이 연결이 있다면, 해당 정점은 방문한 것으로 데이터를 저장해두고 최종 탐색 결과를 반환할 배열에 추가해둔다. 예를 들어, {"A": true}식이다.
- 해당 정점의 각 이웃들에 대해서, 방문 전이라면 DFS 함수를 재귀적으로 호출한다.
결과 배열을 반환한다.

이번 포스팅에선 이전 포스팅에서 작성한 그래프 클래스에 메소드를 추가한다.

javascript
class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  depthFirstRecursive(start){
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList; // 아래 dfs 헬퍼 함수에서 this의 컨텍스트가 바뀌기 때문에 변수로 저장해서 쓰기 위함

    (function dfs(vertex){
      if(!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach(neighbor => {
        if(!visited[neighbor]){
          return dfs(neighbor);
        }
      })
    })(start);

    return result;
  }
}

2. DFS 구현하기-반복

반복문으로 DFS를 구현해보자. 수도코드를 작성한다면 아래와 같을 것이다:

시작 정점을 받아 DFS를 수행하는 함수를 선언한다.
탐색 과정을 기록할 스택(여기선 배열을 활용하자)을 만든다.
- 깊이를 우선적으로 탐색할 것이기 때문에, 먼저 방문한 정점은 그 이웃에 이웃에 이웃의...를 방문하기 전까지는 남아 있어야 한다.
최종 탐색 결과를 반환할 배열과, 이미 방문한 데이터를 저장해둘 객체를 만든다.
시작 정점을 스택에 넣고, 방문한 데이터에 저장한다.
스택에 뭔가가 있는 동안 아래를 반복한다:
- 스택의 데이터를 pop한다.
- 해당 정점이 아직 방문이 되지 않았다면, 방문한 것으로 표시하고, 결과 배열에 추가한다. 해당 정점과 이웃한 모든 정점을 스택에 넣는다.
결과 배열을 반환한다.

javascript
class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  depthFirstIterative(start){
    const stack = [start];
    const result = [];
    const visited = {};
    let currentVertex; // 루프 안에서 선언하면 계속 재선언하게 되므로 밖에서 선언

    visited[start] = true;
    while(stack.length){
      currentVertex = stack.pop();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach(neighbor => {
        if(!visited[neighbor]){
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      })
    }

    return result;
  }
}

너비 우선 탐색

깊이 우선 탐색과 달리, 너비 우선 탐색은 우선 시작 정점과 인접한 정점들을 먼저 모두 탐색하는 탐색 방법이다.

시작 정점을 받아 BFS를 수행하는 함수를 선언한다.
큐를 만들고(여기서 우리는 배열을 활용한다), 시작 정점을 추가한다.
최종 탐색 결과를 반환할 배열과, 이미 방문한 데이터를 저장해둘 객체를 만든다.
시작 정점을 방문한 것으로 추가한다.
큐에 뭔가가 있는한 아래의 루프를 반복한다:
- 큐의 첫번째 정점을 제거하고, 방문한 데이터를 저장하는 객체에 추가한다.
- 해당 정점의 인접한 정점들을 순회한다.
- 순회 중 방문한 정점이 방문한 데이터를 저장한 객체에 없다면, 해당 정점을 추가하고 큐에 추가한다.
최종 탐색 결과를 반환한다.

javascript
class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  breadthFirst(start){
    const queue = [start];
    const result = [];
    const visited = {};
    let currentVertex; // 루프 안에서 선언하면 계속 재선언하게 되므로 밖에서 선언

    visited[start] = true;
    while(queue.length){
      currentVertex = queue.shift();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach(neighbor => {
        if(!visited[neighbor]){
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      })
    }
    return result;
  }
}

🤠 개인 탐구

프로그래머스는 코딩테스트 고득점 Kit 카테고리에 그래프 문제 3문제를 제공한다. 이 문제들을 이 포스트에서 풀어보았다.

PreviousGraphs

Algorithm

NextDijkstra's Algorithm

Algorithm