[알고리즘] 순회 - 그래프에서의 DFS

순회  - 그래프에서의 DFS

2번째 순회 알고리즘으로 DFS(Depth First Search)에 대해서 알아보도록 하자

참고로, 이진 트리의 inorder, preorder, postorder는 모두 DFS라고 할 수있다.

그래프의 인접한 노드를 방문해서, 다시 그 노드의 인접한 노드로 계속 들어가다가

끝에 도달 했을 때 돌아오는것이 DFS이다.

즉, BFS와 마찬가지로 시작점 s가 있어야하며 

현재 노드를 visited로 체크하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다.

위의 연산을 계속 반복하며 끝이 도달하면 다시 돌아오게 된다.

그리고 unvisited가 있다면 해당 노드로 들어가며 앞서 했던 연산을 또 반복하게 된다.

결국 모든 순회를 마칠 경우 시작 노드 s로 돌아오게 되고 더 이상 갈곳이 없으면 종료하게 된다.

위의 그림은 이러한 DFS 연산을 그림으로 나타낸 것이다.

탐색을 진행하는 것은 붉은색, 다시 되돌아오는 것을 초록색으로 표현했다.

 DFS(G, v)
    visited[v] <- yes
    for each node adjacent to x do                                                                        
        if visited[v] = NO then
            DFS(G, u);
    end
end

DFS를 슈도코드로 표현했다.

DFS는 앞서 본 이진 트리의 in/pre/post order 탐색 방식과 비슷하므로

재귀로 표현하는 것이 가장 간명하다.

따라서 인접 노드의 visited가 NO이면 재귀적으로 자신을 호출해서 탐색을 진행하게 된다.

여기서 상위의 노드로 되돌아가는것은,

재귀적으로 호출했으므로  visited가 if문을 만족할 경우 그대로 for문을 빠져 나가게 된다.

호출이 종료되며 자신을 호출한 함수로 반환되는데, 이 때 반환되는 위치가 상위의 노드와 동일하므로

별도로 명시를 안하더라도 상위 노드로 돌아가게된다.

그래프가 disconnect이거나 방향 그래프라면 DFS가 모든 노드를 방문하지 않을 수 있다.

그럴때는 DFS를 반복하며 모든 노드를 방문하면 된다.

 DFS-ALL(G)
{
    for each v->v
        visited[v] <- no
    for each v->v
        if(visited[v] = NO) then                                                                          
            DFS(G,v);
}

즉 위와 같이 재귀적으로 다시 DFS를 반복 해준다.

이 때의 시간 복잡도는 O(n+m)이 된다.