16. 그래프 탐색 (2) - DFS

DFS (Depth-First Search)

개요

설계 모델

BFS와 같이 색깔로 정점의 상태를 구별해 보자.

• White: discover되지 않은 상태 즉, 처음에 모든 정점은 white 상태이다.
• Gray: discover는 되었지만 정점에 대해서 탐색이 끝나지 않은 상태

= Gray 정점의 인접 정점들 중 최소 한개는 white 정점인 상태

 

• Black: discover되고 해당 정점에 대해 모든 탐색이 끝난 상태

= Black 정점의 인접 정점들은 모두 Gray 혹은 Black 상태일 것이다.

 

 

DFS에서 Gray 정점은 약간 BFS와 다른데, 각 Gray 정점에서 2개의 타임스탬프를 가진다.

• d[v]: 정점 v의 discovery time
• f[v]: 정점 v의 finish time (방문할 수 있는 모든 정점을 방문한 상태, 추후에 무슨 의미인지 알게 됨)
  1. : discover time이 항상 finish time보다 작은 것은 자명하다.
  2. : 한 정점에 대해서 왔다갔다 두번하므로 finish time의 최댓값은 2|V|
• Principle

 

 

의사 코드

DFS (V, E)
  // 모든 정점을 WHITE로 초기화
  for each u : V
    color[u] = WHITE;

	// 시작시간을 0으로 초기화
	int time = 0;

	// 모든 정점에 대해서 DFS 탐색
	for each u : V {
    if (color[u] == WHITE)
      DFS-VISIT(u);
  }

 

DFS-VISIT(u)
  
  // 선택된 u 정점을 GRAY로 색칠하고
  // 방문했으니 시간을 1 올려주고 d[u]를 설정한다.
  color[u] = GRAY;
	time++;
	d[u] = time;
	
	// u의 모든 인접정점에 대해서 DFS 탐색을 시작한다.
	// recursive 형태이기 때문에 계속 스택이 쌓이면서 깊게 들어가게 된다.
	for each v : Adj[u] {
    if (color[v] == WHITE)
      DFS-VISIT(v);
  }

	// 정점 u의 모든 인접정접에 대해서 DFS 탐색을 마치면 정점 u를 BLACK으로 칠해준다.
  // 다시 정점 u로 돌아왔으므로 시간을 1 올려주고 f[u]를 설정한다.
	color[u] = BLACK;
	time++;
	f[u] = time;

 

 

동작 과정 (각 프레임마다 3초씩 걸리니 머릿속으로 다음 그림을 예상해 보세요!)

 

 

 

시간복잡도

• DFS(G)에서 모든 정점을 WHITE로 초기화 하는 비용: O(V)

DFS (G)
 for each vertex u = V[G]
   color[u] = WHITE;

...
...
...

 

• DFS(G)에서 모든 정점에 대해 DFS-VISIT를 탐색하는 비용: O(V)

 for each vertex u = V[G]
   if (color[u] = WHITE)
     DFS-VISIT(u);

 

• DFS-VISIT에서 정점 u의 모든 인접정점 v = Adj[u]에 대해 DFS-VISIT 탐색하는 비용: O(E)

DFS-VISIT
  for each v = Adj[u]
    if (color[v] = WHITE)
      DFS-VISIT(v);

=> 총 시간복잡도: O(V+E)

 

 

 

C++ 코드 (흐름을 따라가며 코드를 작성해보세요, 외우기 힘들다면 의사코드를 보면서 코드를 작성해 보세요.)

1. recursive 구현

// 위에서는 정점의 색깔로 표시했지만 컴퓨터는 그럴 수 없기에 bool visit[] 배열을 사용한다.
// visit[x] = false 이면 WHITE, true이면 GRAY or BLACK 이다.
// 아래는 인접 리스트 일 때의 구현입니다. 인접 행렬 일 때의 구현도 작성해보세요!

#include <cstdio>
#include <vector>
#include <iostream>

using namespace std;

bool visit[100];
vector <int> adj_list[100];

int d[100], f[100];
int E, V;
int t = 0;


void DFS_ALL() {
    for (int i = 1; i < V; u++) {
        if (visit[i] == false)
            DFS(i);
    }
}

void DFS(int start) {
    // printf("%d ", start);
    visit[start] = true;
    t++;
    d[start] = t;
    // printf("d[%d] = %d\n", start, d[start]);
    
    for (int i = 0; i < adj_list[start].size(); i++) {
        int v = adj_list[start][i];
        if (visit[v] == false) {
            DFS(v);
        }
    }
    
    t++;
    f[start] = t;
    // printf("f[%d] = %d\n", start, f[start]);
}

int main() {
    scanf("%d %d", &E, &V);
    for (int i = 0; i < E; i++) {
        int src, dst;
        scanf("%d %d", &src, &dst);
        adj_list[src].push_back(dst);
        adj_list[dst].push_back(src);
    }

    // check adj_list
    for (int i = 0; i < V; i++) {
        printf("v[%d]: ", i);
        for (int j = 0; j < adj_list[i].size(); j++) {
           printf("%d ", adj_list[i][j]);
        }
        printf("\n");
    }
    	
    // sort ascending order
    for (int i = 0; i < V; i++) 
        sort(adj_list[i].begin(), adj_list[i].end());

    // src = 0, run DFS
    DFS(0);
    return 0;
}

 

 

2. stack 구현

void dfs_stack(int start) {
    stack <int> s;
    s.push(start);

	while (!s.empty()) {
        int v = s.top();
        s.pop();
        
        if (!visit[v]) {
            printf("%d ", v);
            visit[v] = true;
        }
        
        for (int i = adj_list[v].size() - 1; i >= 0; i--) {
            int w = adj_list[v][i];
            if (!visit[w]) {
                s.push(w);
            }
        }
    }
}

 

 

 

심화과정

• Edge의 종류
  • Tree Edge
  • Back Edge
  • Forward Edge
  • Cross Edge
• DFS와 BFS의 차이

	Implement
BFS	Queue
DFS	Stack (or Recursive)

 

• DFS Advanced

1. Topological Sort
2. {[}] problem
3. Finding [Strongly] Connected Component
4. Critical Path Analysis
5. Biconnected Component (Articulation point) Problem