4-2. 그래프의 탐색(DFS, BFS)

그래프의 탐색

• 목적: 시작점 X로 시작하여 모든 정점을 1번씩 방문하고자 한다.

• 깊이 우선 탐색(DFS)

  • 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고, 더 이상 갈 수 없으면 이전 정점으로 돌아간다.

  • 스택을 이용하는 가장 쉬운 방법은 재귀 호출을 이용하는 방법이다.

  • 인접 행렬을 이용한 구현은 다음과 같다.
    정점의 갯수를 V라고 할 때, 시간 복잡도는 O(v^2)가 된다.

    void dfs(int x) {
      check[x] = true;
      printf("%d ", x);
      for(int i=0; i<=n; i++) {
        if(a[x][i] == 1 && check[i] == false) {
           dfs(i);
        }
      }
    }

  • 인접 행렬을 이용한 구현은 다음과 같다.
    정점의 갯수를 V, 간선의 갯수를 E라고 할 때 시간복잡도는 O(V+E)가 된다.

    void dfs(int x) {
      check[x] = true;
      printf("%d ", x);
      for(int i=0; i<=n; i++) {
        if(a[x][i] == 1 && check[i] == false) {
           dfs(i);
        }
      }
    }

• 너비 우선 탐색(BFS)

  • 큐를 이용해서, 현재 정점에서 갈 수 있는 정점을 모두 큐에 넣는 방법이다. 큐에 넣을 때 방문했다고 체크해야 하는 점에 주의하자.

  • 인접행렬을 이용한 구현은 다음과 같다.
    시간복잡도는 O(V^2)가 된다.

    queue<int> q;
    check[1] = true; q.push(1);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        printf("%d ",x);
        for (int i=1; i<=n; i++) {
            if (a[x][i] == 1 && check[i] == false) {
                check[i] = true;
                q.push(i);
            }
        }
    }

  • 인접리스트를 이용한 구현은 다음과 같다.
    시간복잡도는 O(V+E)가 된다.

    queue<int> q;
    check[1] = true; q.push(1);
    while (!q.empty()) {
         int x = q.front(); q.pop();
      printf("%d ",x);
         for(int i=0;i<a[x].size();i++) {
             int y = a[x][i];
             if (check[y] == false) {
                 check[y] = true; q.push(y);
             }
         }
     }

1260 DFS와 BFS, 백준 온라인 저지

• 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제이다.

11724 연결 요소, 백준 온라인 저지

• 여러개로 나누어진 각각의 그래프를 연결 요소라고 한다.
• 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다. 또, 다른 요소에 속한 정점과 연결하는 경로가 있으면 안된다.
• 연결 요소를 구하는 것은 DFS나 BFS 탐색을 이용해서 구할 수 있다.

1707 이분 그래프, 백준 온라인 저지

• 그래프를 다음처럼 A, B로 나눌 수 있으면 이분 그래프라고 한다.
  • A에 포함되어 있는 정점끼리 연결된 간선이 없다.
  • B에 포함되어 있는 정점끼리 연결된 간선이 없다.
  • 모든 간선의 한 끝 점은 A에, 다른 끝 점은 B에 있다.
• 그래프를 DFS또는 BFS탐색으로 이분 그래프인지 아닌지 알아낼 수 있다.