그래프 순회 (DFS, BFS)

그래프 순회(Graph Travaersal)이란 트리 순회와 마찬가지로 그래프의 모든 정점에 접근하는 것이며 실생활에서 연관검색, 사용자 맞춤 추천, 최단거리검색등에 사용된다.

 

해당 포스트의 코드구현은 이전 포스트에서 작성한 인접리스트를 이용하였다. (이전 포스트:  https://mason-lee.tistory.com/73)

 

class Traversal {
  constructor(graph) {
    this.graph = graph;
  }
 }
 
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");

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

const traversal = new Traversal(graph);

새로운 클래스(Traversal)를 만들어 준뒤 객체를 생성할때 이전 포스트에서 작성한 인접리스트를 주입해 준다. 

 

이후 Traversal 클래스안에 순회를 위한 메서드를 정의함

 

깊이 우선 탐색(Depth First Search, DFS)

class Traversal{
  DFS(vertex) {
    let adjacencyList = this.graph.adjacencyList;

    let result = [];//순회의 순서 저장, 이후 반환
    let visitObj = {};//한번 접근한 정점을 객체에 저장, 중복순회 및 무한루프를 방지

    (function actualLogic(vertex) {// 재귀함수 생성
      if (!adjacencyList[vertex]) return;
      
      visitObj[vertex] = true;//정점을 해당 객체에 추가해주고 이후 해당 정점은 무시함
      result.push(vertex);//순회를 도는 순서대로 result 배열에 정점 추가.

      for (let node of adjacencyList[vertex]) {
      //해당 인접리스트가 가진 정점들을 순서대로 반복문을 돌림
        if (!visitObj[node]) actualLogic(node);
        //만약 인접리스트안의 정점들중 순회를 이미 완료한 정점들은 무시하며
        //이로 인해 해당 재귀의 base case는 없어도 무관하다.
      }
    })(vertex);
    //함수를 소괄호 안에 넣어준뒤 다시 소괄호를 열어 매개변수를 넣어주면
    // 함수를 정의함과 동시에 호출함
      
      //   adjacencyList[vertex].forEach((vertex) => {
      //     if (!visitObj[vertex]) actualLogic(vertex);
      //   }); 위의 반복문을 forEach를사용하여 표현

      //   for (let i = adjacencyList[vertex].length - 1; i >= 0; i--) {
      //     if (!visitObj[adjacencyList[vertex][i]])
      //       actualLogic(adjacencyList[vertex][i]);
      //   } 만약 순회를 반대로 돌릴경우
      
    return result;
  }
}

const traversal = new Traversal(graph);
traversal.DFS("A");
//결과
[ 'A', 'B', 'D', 'E', 'C', 'F' ]

(개인적인 공부를 위한 포스트라 주제와 상관없는 주석처리가 많습니다...)

 

1. 순회의 순서를 결과로 반환할 배열(result)과 반복접근을 확인하며 방지할 객체(visitObj)를 선언
2. 순회를 시작할 정점을 매개변수로 받는 재귀 함수 정의
3. 재귀 함수에서 정점을 받아 위에 선언한 배열과 객체에 해당 정점을 추가해줌
4. 이후 해당 정점의 리스트안의 요소들(인접 정점)을 반복문으로 접근한뒤 재귀함수를 호출 (이때 위에 선언한 객체(visitObj)안에 해당 정점이 존재할경우 무시)
5. 마지막으로 result 배열을 반환

 

너비 우선 탐색(Bread First Search, BFS)

class Traversal{  
  breadthFirst(vertex) {
    let adjacencyList = this.graph.adjacencyList;
    let queue = [vertex];// 재귀호출시 순서를 결정할 queue자료구조 선언
    let result = []; // 순회의 순서를 저장 및 반환할 배열
    let visitObj = {}; // 반복순회를 방지할 객체

    (function actualLogic(vertex) {
      if (queue.length === 0) return; //재귀의 base case
      if (!visitObj[vertex]) { //이미 순회를 완료한 정점은 무시함
        result.push(vertex); //위에 선언한 배열과 객체에 정점 추가
        visitObj[vertex] = true;

        adjacencyList[vertex].forEach((vertex) => queue.push(vertex));
        //반복문을 돌며 해당 정점의 인접정점들을 enqueue시킴 
      }

      actualLogic(queue.shift()); //해당 queue의 첫요소를 dequeue하며 재귀 실행
    })(vertex);

    return result;
  }
}

const traversal = new Traversal(graph);
traversal.breadthFirst("A");
// 결과
[ 'A', 'B', 'C', 'D', 'E', 'F' ]

트리의 너비우선탐색과 같이 Queue 자료구조를 이용해 준다.

 

위의 DFS와 비슷하게 재귀를 돌며 모든 정점들은 result배열과 visitObj에 추가된다. 하지만 현재 정점의 인접정점들에 바로 접근하여 재귀를 호출한것과 다르게 BFS에서는 queue자료구조에 현재 정점의 모든 인접정점들을 enqueue해주고 해당 queue의 첫 요소부터 dequeue를 해주며 재귀를 호출한다.