DFS 깊이 우선 탐색

그래프의 탐색(DFS: depth-first search)

 

 

위 그 림의 번호와 같이 갈 수 있는 정점까지 쭈욱~ 방문 후 다시 올라와 다시 갈 수 있는 정점까지

방문을 하는 탐색 방법이다. 이를 재귀호출을 이용하면 간단하게 구현을 할 수 있다.

<소스 코드>
[-] Collapse

#include<cstdio>
#include<vector>
using namespace std;

vector<vector<int> > adj;
vector<bool> visited;

void dfs(int here){
    printf("정점 %d 방문!", here);
    visited[here] = true;

    for (int i = 0; i < adj[here].size(); i++){
        int next = adj[here][i];
        if (!visited[next])
            dfs(next);
    }
}

int main(){
    visited = vector<bool>(adj.size(), false);
    //모든 정점에서 시작, 이미 방문을 했다면 통과
    for (int i = 0; i < adj.size(); i++){
        if (!visited[i])
            dfs(i);
    }
}

 

DFS탐색 방법의 시간 복잡도

1. 인접 리스트를 사용 할 경우: O(|V| + |E|)

2. 인접 행렬을 사용 할 경우: O(|V|2)


<활용 예> 

1. 두 정점의 연결 check
2. 연결된 부분집합의 개수 세기
3. 위상 정렬: 의존성있는 작업이 있을 때 이들을 어떤 순서로 해야하는지 계산