DFS, BFS

DFS (depth first search)

깊이 우선 탐색은 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

C++

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

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

복잡도는 인접 리스트를 사용할 경우 모든 정점(V)을 한번씩 방문, 모든 간선(E)을 한번씩 검사하게 되므로 O(V+E) 이다.

BFS (breadth first search)

너비 우선 탐색은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

방문한 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐가 필요하다.

C++

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

void bfs(int start){
    queue<int> q;
    q.push(start);    
    visited[start] = 1;
    while(!q.empty()){
        int here = q.top();
        q.pop();
        for(int i = 0; i < adj[here].size(); i++){
            int there = adj[here][i];
            if(!visited[there]){
                q.push(there);
                visited[there] = 1;
            }
        }
    }
}

복잡도는 dfs 와 동일.

연결 성분 (connected component)

연결 성분이란 연결된 부분 그래프들 중에서 크기가 제일 큰 그래프를 말한다. 위 그림에는 4개의 연결 성분이 있다.

C++

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

int function(){
    int count = 0;
    for(int i = 0; i < adj.size(); i++){
        for(int j = 0; j < adj[i].size(); j++){
            int start = adj[i][j];
            if(!visited[start]){
                bfs(start);
                count++;
            }
        }
    }
    return count;
}