[알고리즘] 그래프 순회 (자바스크립트)

그래프 순회와 노드 탐색

그래프 순회를 구현하기 위해서는 일반적인 트리 순회와 달리 루트가 존재하지 않기 때문에, 시작점을 정해주어야 한다. 또한 여러 순서가 존재할 수 있고, 이미 방문했던 노드를 다시 방문하거나 뒤로 돌아가야 하는 경우가 있을 수 있다. 해당 차이점을 제외하고는 트리 순회에서와 마찬가지로 BFS, DFS, 재귀형과 순환형을 통해 구현한다.

 

웹 크롤링, 최단거리 추천, 미로찾기, GPS 네비게이션 등에서 그래프 순회가 사용된다. 실생활과 굉장히 밀접한 알고리즘이다.

 

깊이 우선 그래프 순회 (DFS)

이전에 학습했던 트리 구조에서의 깊이 우선 그래프 순회를 간단히 정리하자면, 형제트리를 방문하기 전에 자식 노드를 먼저 방문하는 것을 말한다. 유방향 그래프를 기준 깊이 우선 그래프에서는 인접점의 Vertex를 우선적으로 방문한 후에 형제 Vertex로 넘어가게 된다.

 

그래프에서의 노드(혹은 정점, Vertex)는 키-값 형태의 객체에 저장되고, 노드마다 키를 갖고, 해당하는 키의 값에 노드들의 연결관계가 담겨 있다는 것을 지난 시간에 학습하였다. Branch를 따라 인접점 노드를 우선적으로 탐색하고, 방문한 노드와 연결관계가 있는 값 데이터에 체크를 해주면 된다. 노드마다의 Boolean 값을 통해 방문여부를 확인해주었다.

 

재귀적 용법의 깊이 우선 탐색 (DFSR)

• 시작 노드 지정 및 결과를 반환할 빈 리스트 생성
• 방문한 노드를 확인할 수 있는 객체 형태 생성
• 정점을 입력 파라미터로 갖는 헬퍼 함수 선언 - 방문 표시 및 결과 리스트에 Push
• 방문하지 않는 인접 정점들에 대해 재귀적으로 헬퍼 함수 호출

 

구현

  // 재귀적 깊이 우선 그래프 순회
  DFSR(start) {
    const result = [];
    const visited = {};
    const adjacencyList = this.adjList;

    (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;
  }

 

순환적 용법의 깊이 우선 탐색 (DFSI)

• 배열 스택을 이용한 상태관리 (S)
• 배열 S가 비어 있지 않는 한, 루프를 반복
• S의 마지막 요소를 Pop하고, 해당 정점의 방문 여부를 판별
• 아직 방문을 하지 않았다면 visitedList 및 결과 리스트에 해당 정점을 추가

재귀에서의 호출 스택을 직접 구현한다고 생각하면 될 듯.

 

구현

  DFSI(start) {
    const stack = [start];
    const result = [];
    const visited = {};
    let currentVertex;

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

      // 인접점 방문
      this.adjList[currentVertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      });
    }
    return result;
  }

 

넓이 우선 그래프 순회 (BFS)

정점마다 계층을 부여하여 인접점으로 타고 들어가기 전에, 같은 계층에 있는 정점을 우선적으로 순회. (수평) DFS와의 차이점이 있다면, 스택 자료구조 대신 큐를 사용한다는 점이다.

• 큐를 이용한 상태관리
• 시작점을 지정하고, 결과를 반환할 빈 리스트를 생성
• 큐 배열에 값이 들어있는 한, 루프를 반복
• 현재 정점을 큐 배열에 Shift 
• 인접점들에 대한 반복 구성

 

구현

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

    while (queue.length) {
      currentVertex = queue.shift;
      result.push(currentVertex);

      // 수평 정방향
      // this.adjList[currentVertex].forEach((neighbor) => {

      // 수평 역순
      this.adjList[currentVertex]
        .slice()
        .reverse()
        .forEach((neighbor) => {
          if (!visited[neighbor]) {
            visited[neighbor] = true;
          }
        });
    }
    return result;
  }

 

만든 그래프 구조를 시각적으로 쉽게 확인할 수 있었으면 좋았을 듯.