[자료구조/알고리즘] Graph - BFS , DFS

그래프를 순회하는 방법 중 가장 일반적인 너비 우선 검색과 깊이 우선 검색에 대해 공부한다

1. 너비 우선 방법 (BFS , Breadth-First Search)

그림출처

• 위의 그림과 같이 그래프에서 연결된 노드와 해당 노드들 간의 간선을 순서대로 검색하는 알고리즘을 말한다.
• 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회한다.
• 이진트리검색의 차수 우선 순회와 비슷한 개념이다.
• 구현을 위해서는 Queue를 필요로 한다.
• 시간 복잡도 O(V+E) : V는 정점의 개수이고 E는 간선의 개수이다. 전체 그래프를 순회하기 위해 모든 정점과 간선을 방문해야 하기 때문
• 아래의 무지향성 그래프의 예와 함께 코드를 분석해보자
  • 탐색 순서는 a → b → d→ c →e 이다.

아래 코드에서 vertex는 현재 방문 중인 node를 나타내고,

배열 visited는 이미 방문을 한 노드들이 들어있다.

let queue = [],
    visited = [];

위의 그림에서 BFS는 노드 "a"에서 시작한다. 노드 "a"의 인접 도드로 "b"와 "d"가 있기 때문에 해당 노드들을 queue에 넣는다.

// 정점 vertex의 각 요소 (인접 정점)에 접근하여 queue에 넣는다.
// vertex = "a"   , queue = ["b","d"]
      for (let adjacentVertex in this.edges[vertex]) {
        queue.push(adjacentVertex);

그다음, 노드 "B"를 방문하고 B에 방문하였음을 표시한다. 동시에 queue에 있던 "b"는 삭제되고 queue에는 "d"만 남게 된다.

// 노드 "B" 방문
// vertex = "b" queue = ["d"]  visite[a:true]
vertex = queue.shift();

// visite[a: true,b: true]

 if (!visited[vertex]) {
      visited[vertex] = true;

그리고 "b"의 이웃 노드인 "c"를 queue에 넣는다.

// vertex="b" , queue=["c","d"]
 for (let adjacentVertex in this.edges[vertex]) {
        queue.push(adjacentVertex);
      }

전체 코드는 다음과 같다.

DirectedGraph.prototype.traverseBFS = function (vertex) {
// 접근 데이터를 넣을 queue 와 방문 했음음 표기할 visited 배열을 선언한다.
  let queue = [],
    visited = [];

// queue에 입력받은 정점을 넣는다 (첫 번재로 탐색할 정점)
  queue.push(vertex);

// queuq에 데이터가 없을 때까지 반복문을 돌린다.
  while (queue.length) {
        // 탐색을 할 vertex를 queue에서 가져온다.
    vertex = queue.shift();

        // 이미 방문한 노드가 아니하면 방문했음을 표기한다.
    if (!visited[vertex]) {
      visited[vertex] = true;
            console.log(vertex);

            // 정점 vertex의 각 요소 (인접 정점)에 접근하여 queue에 넣는다.
      for (let adjacentVertex in this.edges[vertex]) {
        queue.push(adjacentVertex);
      }
    }
  }
};

// 정점을 추가하고 간선을 추가하는 함수들을 호출한 것/
digraph1.addVertex("b");
digraph1.addVertex("c");
digraph1.addVertex("d");
digraph1.addVertex("e");
digraph1.addVertex("a");
digraph1.addEdge("a", "b");
digraph1.addEdge("a", "d");
digraph1.addEdge("b", "c");
digraph1.addEdge("b", "e");

// BFS 탐색 알고리즘 실행 ("a" 부터 탐색 시작)
digraph1.traverseBFS("a")

/* 
정점 
DirectedGraph {
  edges: { b: { c: 0, e: 0 }, c: {}, d: {}, e: {}, a: { b: 0, d: 0 } }
}

결과 탐색이 a → b → d→ c →e  임을 확인한다.
a
b
d
c
e
*/

2. 깊이 우선 방법 (DFS , Depth-First Search)

그림출처

• 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와 다른 형제들의 자식을 타고 내려가며 순회한다.
• 하나의 견결을 깊게 파고들며 순회하는 알고리즘이다.
• 이진트리의 후순위, 중순위 트리 순회와 비슷하다.
• 시간 복잡도 O(V+E) : V는 정점의 개수이고 E는 간선의 개수이다. 전체 그래프를 순회하기 위해 모든 정점과 간선을 방문해야 하기 때문. 너비 우선 검색 알고리즘과 비슷하다.
• 아래의 무지향성 그래프의 예와 함께 코드를 분석해보자
  • 탐색 순서는 a → b → c→ e→d이다.

트리 자료구조의 선순위 순회와 중순위 순회와 유사하게 한 노드의 깊이 쪽으로 연결된 모든 경로를 거치게 되므로

"재귀"를 사용한다.

현재 정점에 방문했음을 표시하고, 현재 정점을 출력한다.

visited[vertex] = true;
  console.log(vertex);

현재 정점의 인접 노드를 순차적으로 방문하기 위해 반복문을 사용한다

각 인접 노드가 방문하지 않은 노드라면 재귀를 사용하여 인접 노드를 루트 노드로 하여 깊이 탐색을 진행한다.

for (let adjacentVertex in this.edges[vertex])
// 이미 방문한 노드가 아니라면 재귀를 사용하여 그 노드의 인접 노드로 탐색을 시작한다.
    if (!visited[adjacentVertex])
      this._traverseDFS(adjacentVertex, visited, fn);
};

전체 코드는 아래와 같다.

DirectedGraph.prototype.traverseDFS = function (vertex, fn) {
  let visited = [];
  this._traverseDFS(vertex, visited, fn);
};

// __traverseDFS 메서드는 인자로 주어진 vertex부터 시작하여 재귀적으로 깊이 검색을 실행한다.
DirectedGraph.prototype._traverseDFS = function (vertex, visited, fn) {

// 방문 했음을 표시하고 현재 정점을 콘솔로 출력한다.
  visited[vertex] = true;
  console.log(vertex);
// 깊이 검색을 위해 현재 정점의 인접 노드로 반복문을진행한다.
  for (let adjacentVertex in this.edges[vertex])
// 이미 방문한 노드가 아니라면 재귀를 사용하여 그 노드의 인접 노드로 탐색을 시작한다.
    if (!visited[adjacentVertex])
      this._traverseDFS(adjacentVertex, visited, fn);
};

/* 결과
a
b
c
e
d
*/