[그래프]DFS - Deapth First Search 깊이우선 탐색

그래프에서는 크게 두 가지 탐색법이 존재한다. 깊이우선과 너비우선 (DFS and WFS)

탐색의 목적은 '어떤 Vertex가 있을까?'하는 'Find'가 아닌, 그래프내에서 모든 Vertex를 Edge를 따라서 '순회'하는데 있다. 즉, 빠짐없이 순회하면서 그 Vertex와 Edge로부터 정보를 얻어서 무언가를 하는데 그 목적이 있다.

깊이우선은 스택(Stack)과 재귀호출을 이용해서, 너비우선은 큐(Queue)를 이용해서 구현된다.

먼저 깊이우선부터 알아보자.

깊이우선 탐색 (DFS. Depth First Search)

핵심

  - 모든 점에 대해 인접리스트 생성 : vector<vector<int>> adj

  - 모든 점에 대해 방문여부 관리 : vector<bool> visited

  - 처음에 모든 점의 방문여부를 false로 초기화하고, 모든 점에 대해서 dfs함수 호출

  - dfs()에서는, 

    . 현재의 점을 방문한 것으로 세팅: visited[u] = true

    . 현재 점과 연결된 모든 점에 대해, 만약 방문하지  않았던 점이면, dfs() 호출 (재귀적)

코드

vector<vector<int>> adj;

vector<bool> visited;

 

void dfs(int u){

         visited[u] = true;

 

         //연결된 모든 점들에 대해

         for (int i = 0; i < adj[u].size(); ++i){

                  int v = adj[u][i];

                  if (!visited[v]) dfs(v);

         }

}

 

void visitAll(){

         visited = vector<bool>(adj.size(),false);

         for (int i = 0; i < adj.size(); ++i){

                  if (!visited[i])  dfs(i);

         }

}

int main(void){

         freopen("dfs.txt", "r", stdin);

         setbuf(stdout, NULL);

 

         int V, E;

         cin >> V;         cin >> E;

 

         adj = vector<vector<int>>(V+1);

         int u, v;

         for (int i = 0; i < E; ++i){

                  cin >> u >> v;

                  adj[u].push_back(v);

         }       

         visitAll();

         return 0;

}

      

시간복잡도 고려

- 인접리스트로 구현한 경우 O(V + E)

- 행렬로 구현한 경우 O(V²)

문제 유형들 - 깊이우선탐색으로 풀 수 있는 

1) 임의의 두 점 a,b가 연결되어 있는가? (중간에 다른 점을 거쳐서라도)

   --> dfs(u)를 수행한 후, visited[v] 값을 확인하면 됨. 만약 visited[v]==false이면 연결안됨

2) 그래프가 몇 개의 컴퍼넌트(단락된 그래프 그룹)로 구성되었는가?

   --> visitAll()에서 dfs()가 몇 번 호출되는 지 세어보면 됨

3)작업간 의존관계가 있는 그래프에서의 위상정렬(totplogical sort): 의존관계 고려한 작업순서대로 정렬

   --> dfs()가 종료되기 직전에, 해당 정점을 vector에 저장해 뒀다가, 탐색이 모두 끝난 후 해당 vector내용을 거꾸로하면 소팅된 것임.

Reference

1. 구종만. 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략. 인사이트. 

-끝-