그래프 순회(Graph Traversal)

• 그래프에서 순회하는 코드를 짤 때, 루트가 있는 트리와는 달리 시작점을 정해줘야 한다.
• 그래프의 한 노드에서 다른 노드로 갈 때 유일한 하나의 길만이 있다는 보장은 없다. 이미 방문한 노드를 다시 방문해야 할 수도 있다.
• 그래프 순회 사용 예시
  • P2P 네트워킹
  • 웹 크롤러
  • 최단 거리 찾기

DFS(깊이우선탐색)

Explore as far as possible down one branch before "backtracking”

• DFS(깊이우선탐색)은 다른 형제를 방문( backtracking)하기 전에 한 브랜치에서 가능한 가장 아래까지 깊이 탐색한다.
• DFS와 BFS 모두, 매개변수로 시작점을 받고 순회하면서 방문한 정점을 추적한다는 점들은 같다.
• 아래와 같은 그래프에서 A부터 순회를 시작하는 과정을 살펴보자.
  • 방문한 곳들의 노드를 인접리스트에서 지워나가야 한다. 아래 이미지는 A와 B 노드를 방문하고 이제 B에서 다음으로 방문할 노드를 결정해야 하는 상황이다. 인접리스트에는 A와 B가 삭제되어 있다. B에서 다음으로 방문할 노드는 인접리스트[B]에 남아 있는 ‘D’ 가 된다. 이러한 로직을 인접 리스트의 배열(각 정점의 간선)들에서 값이 남지 않을 때까지 반복한다.

DFS - 재귀형 코드

• depthFirstRecursive 메서드 코드

// 순회를 시작할 정점 노드를 인수로 받는다. 
depthFirstRecursive(start) {
  // 결과를 저장할 빈 배열 result를 만든다(마지막에 이것을 return할 것이다)
  const result = [];
  // 방문한 정점들를 기록할 빈 객체 visted를 만든다. 
  const visited = {};
  const { adjacencyList } = this;
  // 재귀를 도울 헬퍼 함수를 정의하며, start를 인수로 받아 즉시 실행한다.
  (function dfs(vertex) {
    // 만약 정점이 비었다면 return 한다.
    if (!vertex) return null;
    // 방문한 정점을 visited 객체에 true로 기록한다.
    visited[vertex] = true;
    // 방문한 정점을 result 배열에 추가한다. 
    result.push(vertex);
    // 방금 방문한 정점과 간선으로 이어진 노드 중에서 아직 방문하지 않은 노드들에 대하여
    // 본 헬퍼 함수를 재귀한다. 
    adjacencyList[vertex].forEach(neighbor => {
      if (!visited[neighbor]) {
        return dfs(neighbor);
      }
    });
  })(start);

  // 순회한 정점이 순서대로 담긴 배열 result를 return한다.
  return result;
}

• 메서드 실행 결과 확인

const g = new Graph();

g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addVertex("F");

g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("C", "E");
g.addEdge("D", "E");
g.addEdge("D", "F");
g.addEdge("E", "F");

//          A
//        /   \
//       B     C
//       |     |
//       D --- E
//        \   /
//          F

// 위와 같은 그래프에서 A부터 순회를 시작하도록 depthFirstRecursive('A') 메서드를 실행하면, 마지막 줄과 같이 예상한대로 순회했음을 확인할 수 있다.
console.log(g.depthFirstRecursive("A"));

// [ 'A', 'B', 'D', 'E', 'C', 'F' ]

DFS - 순환형 코드

• depthFirstIterative 메서드 코드

depthFirstIterative(start) {
  // stack 배열을 정의하고, start 노드를 추가한다.stack은 반복문에서 조건으로 사용할 것이다.
  const stack = [start];
  // 결과를 저장할 빈 배열 result를 만든다(마지막에 이것을 return할 것이다)
  const result = [];
  // 방문한 정점들를 기록할 빈 객체 visted를 만든다. 
  const visited = {};
  let currentVertex;
  // visited 객체에 start 노드는 방문했음을 기록한다.
  visited[start] = true;

  // stack이 비어 있지 않은 한, 무한 루프를 돌린다.
  while (stack.length) {
    // 여기서는 pop을 이용하여 간선 배열의 끝에서부터 정점을 꺼내어 방문한다.
    // stack에서 가장 최근에 들어온 노드를 하나 꺼내어(pop), currentVertex 변수에 할당한다.
    currentVertex = stack.pop();
    // 지금 방문한 정점을 result 배열의 마지막에 추가(push)한다. 
    result.push(currentVertex);

    // 지금 방문한 정점과 간선으로 이어진 정점 중 
    this.adjacencyList[currentVertex].forEach(neighbor => {
      // 아직 방문하지 않은 이웃 정점에 대하여
      if (!visited[neighbor]) {
        // visited 객체에 이제 방문했음을 기록하고
        visited[neighbor] = true;
        // stack 배열(while문 종료 조건이었죠~)에 push한다. 
        // stack에는 이제 start 정점은 없고 그 다음에 방문한 정점 하나가 있게 되며, 다시 while문을 돈다.
        stack.push(neighbor);
      }
    });
  }
  // 반복문이 다 종료된 후 result를 반환한다.
  return result;
}

• 코드 실행 결과
  • 코드의 작동 방식 때문에, 재귀형 코드와 달리 순회 순서가 달라지긴 했으나, 두 방법 모두 DFS 방식인 것은 동일하다.

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  // 기타 메서드 생략
depthFirstIterative(start) {
    const stack = [start];
    const result = [];
    const visited = {};
    let currentVertex;

    visited[start] = true;
    while (stack.length) {
      console.log("stack", stack);  // 이해하기 위해 콘솔로그 찍음
      currentVertex = stack.pop();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          console.log("neighbor", neighbor);  // 이해하기 위해 콘솔로그 찍음
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      });
    }
    return result;
  }
}
const g = new Graph();

g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addVertex("F");

g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("C", "E");
g.addEdge("D", "E");
g.addEdge("D", "F");
g.addEdge("E", "F");

//          A
//        /   \
//       B     C
//       |     |
//       D --- E
//        \   /
//          F

// 위와 같은 그래프에서 A부터 순회를 시작하도록 depthFirstIterative('A') 메서드를 실행하면, 마지막 줄과 같이 순회했음을 확인할 수 있다.  

console.log(g.depthFirstIterative("A"));

// [ 'A', 'C', 'E', 'F', 'D', 'B' ]

BFS(너비우선탐색)

• BFS(너비우선탐색)은 현재 같은 높이(height)의 이웃 정점들을 먼저 방문하는 알고리즘이다.
• 아래 코드에 주석을 달긴 했지만, BFS 순환형 코드는 DFS 순환형 코드와 거의 비슷한다.
  • 다른 점은 while 조건문에서 순회하는 개념으로 stack 대신 queue를 사용하고 이를 위해 pop 메서드 대신 shift 메서드를 쓴다는 것이다.

breadthFirst(start) {
  const queue = [start];
  const result = [];
  const visited = {};
  let currentVertex;
  visited[start] = true;

  while (queue.length) {
    // 여기서는 shift를 이용하여 간선 배열의 처음부터 정점을 꺼내어 방문한다.
    // queue에서 줄 제일 앞에 서 있는 노드를 하나 꺼내어(shift), currentVertex 변수에 할당한다.
    currentVertex = queue.shift();
    result.push(currentVertex);

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

• 코드 실행 결과

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

// 기타 메서드 생략

breadthFirst(start) {
    const queue = [start];
    const result = [];
    const visited = {};
    let currentVertex;
    visited[start] = true;

    while (queue.length) {
      console.log("queue", queue);  // 이해하기 위해 콘솔로그 찍음
      currentVertex = queue.shift();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          console.log("neighbor", neighbor);  // 이해하기 위해 콘솔로그 찍음
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      });
    }
    return result;
  }
}

const g = new Graph();

g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addVertex("F");

g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("C", "E");
g.addEdge("D", "E");
g.addEdge("D", "F");
g.addEdge("E", "F");

//          A
//        /   \
//       B     C
//       |     |
//       D --- E
//        \   /
//          F

// QUEUE: []
console.log(g.breadthFirst("A"));
// RESULT: [A, B, C, D, E, F]

메서드 내부에서 실행된 콘솔로그까지 포함한 코드 실행 결과는 아래 이미지와 같다.

queue에서 제일 앞 정점부터 초록선으로 shift하며 순회하는 모습이다. 지금 방문한 정점과 간선으로 이어진 정점들을 돌리는 forEach문에서 queue에 push되는 정점들이 neighbor 옆에 찍혔다.