[JS] 깊이 우선 탐색

1. 깊이 우선 탐색

 깊이 우선 탐색(DFS, Depth First Search)은 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해나가다가 더 이상 갈곳이 이 없으면 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서, 다른 방향의 간선으로 탐색을 계속함으로써 모든 정점을 방문하는 순회 방법이다. 저번에 트리에 대해 포스팅했을 때 전위, 중위, 후위 순회 방법 세 가지를 언급한 적이 있었다. 이 세 가지 방법이 깊이 우선 탐색에 해당된다. 깊이 우선 탐색은 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가 다시 깊이 우선 탐색을 반복해야 하므로 스택을 사용한다.

 

 

2. 탐색 과정

 그림을 이용해서 알고리즘이 어떻게 돌아가는지 설명해보도록 하겠다. 밑에 [그림1]은 빈 스택과, 아직 탐색하지 않은 그래프가 있다. 이제 우리는 밑에 있는 그래프 G를 이용하여 깊이 우선 탐색의 과정을 설명하려한다.

[그림 1]

 

 기본 노드는 다음과 같이 구성한다.

const Node = function(data){
  this.data = data; 
  this.link = null;
  this.visited = false;
}

 

 데이터는 정점이 삽입될 곳이고 링크는 인접리스트의 다음 정점을 가리키는 변수이다. visited는 깊이 우선 탐색을 하면서 해당 정점을 방문처리를 하기위해 만든 변수이다. 편의상 정점 A부터 우선탐색을 시작하도록 하겠다. 탐색 후 A에 대하여 방문 처리를 한다.

 

[그림 2]

 

 노드 A에 방문하지 않은 노드 B,C가 있으므로 스택에 노드 A를 삽입한다. A 다음에 오름차순으로 가장 인접한 B를 선택하여 탐색을 계속한다.

 

[그림 3]

 

 노드 B에 인접한 노드는 A, E이다. 그런데 A는 이미 방문처리를 한 노드이기 때문에 탐색하면 안된다. 따라서 A 다음으로 인접한 E를 선택하여 탐색을 계속한다.

 

[그림 4]

 

 방문 처리한 노드 B를 스택에 넣는다. 그리고 E를 방문했으므로 Visited에 True값을 줘서 방문처리를 한다. 노드 E와 인접한 노드는 B 밖에 없다. 하지만 B는 이미 방문 처리를 한 노드이다. 따라서 우리는 스택에 삽입했던 노드들을 차례대로 꺼내서, 꺼낸 노드의 인접 노드들의 방문처리 유무를 확인해야 한다.

 

[그림 5]

 

 마침 A 노드에 방문처리를 하지 않은 노드 C가 있다. 따라서 C를 선택해서 탐색을 계속 하도록 한다.

 

[그림 6]

 

 노드 C를 스택에 넣는다. 노드 C와 인접한 노드는 A, D가 있다. 하지만 A는 이미 방문처리를 한 상태이므로 탐색을 할 수 없다. 따라서 노드 D를 선택해서 탐색을 계속한다.

 

[그림 7]

 

 노드 D와 인접한 노드는 C밖에 없다. 하지만 C는 이미 방문 처리를 한 상태이다. 따라서 노드 D에서 탐색 가능한 인접노드는 한 개도 없다. 그런데 스택에는 C노드가 있다. C노드의 인접 노드 중 방문처리를 하지 못한 노드가 있을 수도 있다. 따라서 C를 꺼내서 검사를 해봐야 한다.

 

[그림 8]

 

 노드 C와 인접한 노드는 A, D다. 하지만 A, D 모두 방문처리를 한 상태이다. 또한 스택에는 남아있는 데이터가 없다. 스택은 비어있다. 스택이 비어있다는 의미는 깊이 우선 탐색과정을 모두 마쳤다는 의미다. 따라서 더 이상 탐색할 노드는 없다. 그러므로 탐색을 종료한다.

 

 

3. 프로그램 코드

프로그램 코드는 다음과 같다.

const Node = function(data){
  this.data = data; 
  this.link = null;
  this.visited = false;
}

const Graph = function(size){
  this.graph = Array.from({length: size}, (e,i) => new Node(String.fromCharCode(65+i)));

  Graph.prototype.insertEdge = function(v1, v2){
    const v1Idx = v1.charCodeAt(0)-65;
    const v2Idx = v2.charCodeAt(0)-65;

    if(v1Idx > size || v2Idx > size) return;
    
    let startV1 = this.graph[v1Idx];
    let startV2 = this.graph[v2Idx];
    const v1Node = new Node(v1);
    const v2Node = new Node(v2);

    while(startV1.link != null)
      startV1 = startV1.link;
    while(startV2.link != null)
      startV2 = startV2.link;

    startV1.link = v2Node;
    startV2.link = v1Node;
  }

  Graph.prototype.printAdjList = function(){
    console.log("Print AdjList");
    for(let i=0; i<size; i++){
      let vertex = this.graph[i];
      const connected = " - ";
      let str = vertex.data;
      while(vertex.link != null){
        vertex = vertex.link;
        str = str + connected + vertex.data; 
      }
      console.log(str);
    }
  }

  Graph.prototype.DFS = function(){
    const stack = [];
    const graph = this.graph;
    let node = this.graph[0];
    let str = node.data;
    let idx = 0;
    stack.unshift(node);
    node.visited = true;
    
    while(node.link !== null){
      node = node.link;
      idx = node.data.charCodeAt(0)-65;
      if(!graph[idx].visited){
        graph[idx].visited = true;
        str += graph[idx].data;
        stack.unshift(graph[idx]);
        node = graph[idx];
      }
    }

    while(stack.length){
      node = stack.shift();
      while(node.link !== null){
        node = node.link;
        idx = node.data.charCodeAt(0)-65;
        if(!graph[idx].visited){
          graph[idx].visited = true;
          stack.unshift(graph[idx]);
          node = graph[idx];
          str += node.data;
          break;
        }
      }
    }

    console.log("\nDFS 순회:",str.split("").join(" - "));
  }

}


const main = (function(){
  const graph = new Graph(5);
  graph.insertEdge('A', 'B');
  graph.insertEdge('C', 'A');
  graph.insertEdge('C', 'D');
  graph.insertEdge('B', 'E');

  graph.printAdjList();

  graph.DFS();

}());

 

 

4. 참고 자료

 자바로 배우는 쉬운 자료구조, 한빛 미디어