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

깊이우선순회 (DFS)

1. 출발점 s에서 시작한다.

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

3. 2번을 계속 반복한다.

이 것을 끝까지 반복한 뒤에, unvisited 의 이웃 노드가 없다면, 직전 노드로 되돌아가서 반복하는 방식으로 구현하면 된다.

* 검색을 통한 공부. 

참조: https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

이것은 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다.

예시로 미로를 탐색할때 아예 한 방향으로 갈 수 있는데까지 가다가, 갈 수 없게 되면 다시 제일 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법이다.

그러므로 wide하게 탐색하기 전에 deep하게 탐색하는 것이다.

이것도 모든 노드를 방문하고자 하는 경우에 선택하는 방식인데.

이거 구현하는게 BFS보다 간단하긴 한데, 검색 속도 자체는 느리다.

이건 수도 코드를 보면

DFS(G, v) 

    visited[v] <- yes;

    for each node adjacent to x do

        if visited[v] = NO then

            DFS(G, u);

    end

end

이건 되돌아가는 것이 중요한 코드인데,

만약에 disconnected인 그래프이거나, 방향 그래프면 DFS에 의해서 모든 노드가 방문되지 않을 수도 있어서

이것도 반복 시켜 줘야 하는 방식이다.

근데 얘는 시간에 대한 기대가 낮아서 DFS는 이해 가능.

이거 재귀 호출 식으로 구현 할 수도 있고

스택 같은데 넣어놓고 사용해도 되긴 한다... (근데 재귀로 짤 거 같음 - 간단한 예 만...)

만약에 스택 배열 같은 식으로 구현하면 오버플로우 조심 해야 할 듯 (무한으로 돌리다가 메모리 초과시에는 죽는거지 뭐...)

사실 이거는 검색용으로 쓰기는 구리고... 사이클 탐색이나 아니면 미로 찾기 등에서 유용하다고 한다.

이게 최단 경로를 찾아 주는 게 아니라서 여러 가지 경로 찾은 경우 최단이 아닐 수도 있어서 검색 용으로 쓰는 건 아님...

이거 트리에 관해서는 나중에 나올 거 같은데 유향트리이고, 유향간선에 관해서 찾아보면 더 나오겠지만 나중에 나올 것 같다... -.-)