C++ DFS & BFS

in Dev. Log on Algorithm

탐색 알고리즘의 대표 주자인 DFS(Depth First Search)와 BFS(Breadth First Search)의 구현에 대해 DFS와 BFS 문제를 풀며 간단히 알아보겠습니다.

공통 코드

int total_node;
bool graph[MAX_VERTEX + 1][MAX_VERTEX + 1];
bool is_visited[MAX_VERTEX + 1];

bool graph[][] 2차원 배열의 인접 행렬(adjacency matrix)을 통해 그래프를 나타냅니다.
bool is_visited[]는 각 노드의 방문 여부를 나타내며, 노드는 1 ~ total_node 까지 존재합니다.

재귀나 stack을 이용하여 구현합니다.
대부분의 경우 재귀 함수를 통해 구현하며, 이 경우 너무 깊게 탐색하게 될 경우 stack memory limit을 넘는 경우가 있을 수 있습니다.
이 떄 도착점에 도달한 경로를 구했다 하더라도, 해당 경로가 최단 경로라는 보장이 없습니다.

구현

void dfs(int cur) {
  is_visited[cur] = true;
  cout << cur << " ";

  for (int next = 1; next <= total_node; next++)
    if (graph[cur][next] && !is_visited[next])
      dfs(next);
}

dfs() 재귀 호출을 통해 방문한 노드를 표시해주고, 포문을 통해 연결된 노드 중 아직 방문하지 않은 노드를 재귀 호출합니다.

queue를 이용해 간단하게 구현할 수 있습니다.
또한 가중치가 없는 그래프에서는 도착점까지의 최단 경로를 구할 수 있습니다.

구현

void bfs(int start) {
  queue<int> myQ;
  is_visited[start] = true;
  myQ.push(start);

  while(!myQ.empty()) {
    int cur = myQ.front();
    myQ.pop();
    cout << cur << " ";
    for (int next = 1; next <= total_node; next++) {
      if (graph[cur][next] && !is_visited[next]) {
        is_visited[next] = true;
        myQ.push(next);
      }
    }
  }
}

BFS를 구현할 때 주의할 점은 queue에 다음 노드를 push() 하기 전에 is_visited를 업데이트 해줘야 한다는 것 입니다.
방문 여부를 DFS 때와 마찬가지로 노드에 도착했을때 진행할 경우 동일한 노드가 여러번 queue에 들어갈 수 있다는 점에 주의하여야 합니다.