(JS 알고리즘) 그래프 순회(Graph Traversal) - DFS(깊이우선탐색), BFS(너비우선탐색)

그래프 순회(Graph Traversal)

• 그래프에서 순회하는 코드를 짤 때, 루트가 있는 트리 순회와는 달리 시작점을 정해줘야 한다.
• 그래프의 한 노드에서 다른 노드로 갈 때 유일한 하나의 길만이 있다는 보장은 없다. 이미 방문한 노드를 다시 방문해야 할 수도 있다.
  

DFS(깊이 우선 탐색) > 재귀형, 순회형

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

DFS-재귀형

//순회를 시작 할 시작점 노드를 인수를 받는다.
depthFirstRecursive(vertex){ //재귀형
        var results = [];//결과를 저장
        var visited = {};//방문을 추적할 객체
        const list = this.List;
        function DFS(vertex){
            if(!vertex) return null;
            visited[vertex] = true;
            results.push(vertex);
          	//방문한 정점의 간선들이 연결된 정점을 순회하여 아직 방문하지 않은 노드들로 헬퍼 함수를 재귀한다.
            list[vertex].forEach((v)=>{
                if(!visited[v]){
                    return DFS(v);
                }
            });
        }
        DFS(vertex);
        return results;
    }

• 실행 결과 확인

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-순환형

• 재귀형의 호출스택 대신 스택을 사용하였다.
• 코드의 작동 방식 때문에, 재귀형 코드와 달리 순회 순서가 달라지긴 했으나, 두 방법 모두 DFS 방식인 것은 동일하다.

depthFirstIterative(start){
        var stack = [start]; //재귀형의 호출스택 대신 스택 사용
        var results = []; //결과
        var visited = {}; // 방문 추적 객체
        var curVertex;
        visited[start] = true;

        while(stack.length){
            curVertex = stack.pop();
            results.push(curVertex);
            this.List[curVertex].forEach((v)=>{
                if(!visited[v]){
                    visited[v] = true;
                    stack.push(v);
                }
            })
        }
        return results;
    }

• 실행 결과 확인

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(너비우선탐색)은 현재 같은 레벨의 형제 정점들을 먼저 방문하는 알고리즘이다.

breadthFirst(start){ //너비우선
        var result = [];
        var visited = {};
        var queue = [start]; //스택 대신 큐 사용
        var currentVertex;
        visited[start] = true;
        
        while(queue.length){
          	//stack 대신 queue를 사용하였다.
            currentVertex = queue.shift();
            result.push(currentVertex);

            this.List[currentVertex].forEach((v)=>{
                if(!visited[v]){
                    visited[v] = true;
                    queue.push(v);
                }
            });
        }
        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

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