[자료구조] Graph 순회 (javascript로 구현하기)

그래프 개념

DFS 그래프순회

좌) A 를 시작점으로, 우) C를 시작점으로

• 선택한 정점(A)의 인접점(B,C,D) 중 하나를 선택(B)하고 방문한다. 방문한 정점의 인접점이 없을 경우(이전 정점제외) 이전 정점의 다른 인접점을 탐색한다.
• 방문한 정점(B)이 인접점이 있을 경우 인접점(E)을 방문하고 위의 논리를 반복한다.
• 이때 인접점이 여러 개일 경우 어떤 것을 우선으로 방문할 지 정할 수 있다. 그림 예시에서는 abc순으로 정했다.

 

DFS 그래프순회 구현하기

• 참고) 여러 인접점에 대한 우선순위를는 고려하지 않았다.

class Graph {
    // ...constructor 및 기타 메소드: 글 상단 [그래프개념] 링크 참조


  // 재귀를 이용한 방법
  depthFirstTraverseRecursive(startVert) {
    const visitingMark = {};
    const result = [];
    const travel = (vert) => {
      if (visitingMark[vert]) return;
      visitingMark[vert] = true;
      result.push(vert);
      this.adjacencyList[vert].forEach((linkedVert) => {
        travel(linkedVert);
      });
    };
    travel(startVert);
    return result;
  }

  // 반복문을 이용한 방법 Stack의 개념을 이용한다.
  depthFirstTraverseRoop(startVert) {
    const stack = [];
    const visitingMark = {};
    const result = [];
    stack.push(startVert);
    while (stack.length) {
      const current = stack.pop();
      if (!visitingMark[current]) {
        visitingMark[current] = true;
        result.push(current);
      }
      this.adjacencyList[current].forEach((linkedVert) => {
        if (visitingMark[linkedVert]) return;
        stack.push(linkedVert);
      });
    }
    return result;
  }

}

 

BFS 그래프순회

좌) A 시작점, 우) C 시작점

• 선택한정점(A)의 인접정점(B,C,D)을 모두 순회한 후 인접정점 중 하나(B)의 인접정점들(E,F)을 순회한다.

 

BFS 그래프 순회 구현

class Graph {
    // ...생략.. 글 상단 [그래프 기본] 참고


    // queue 자료형을 활용한다. 임시로 array를 큐라고 가정하고 진행함
  breathFisrtTraverse(startVert) {
    const queue = []; // unshift: enqueue, pop: dequeue
    const visitingMark = {};
    const result = [];
    queue.unshift(startVert);

    while (queue.length) {
      const current = queue.pop();
      if (!visitingMark[current]) {
        visitingMark[current] = true;
        result.push(current);
      }
      this.adjacencyList[current].forEach((linkedVert) => {
        if (visitingMark[linkedVert]) return;
        queue.unshift(linkedVert);
      });
    }
    return result;
  }
}