[알고리즘] Graph(2) - DFS(Depth-First Search)

1. Graph 주요 용어

• vertex : 정점
• edge : 간선 (정점과 정점을 연결한 선)
• color : 정점에 색깔을 부여하여 방문 상태를 확인하는 용도

• white vertex   : 아직 방문된 적이 없는 정점

• gray vertex    : 방문은 되었지만 인접한 정점들 중에 white vertex가 존재, 즉 더 이상 탐색이 가능한 정점의 상태

• black vertex   : 인접한 모든 정점 중 white vertex가 없음, 즉 더 이상 탐색이 불가능한 정점의 상태

• 선행자( π ) : 부모 정점을 저장하는 용도

• d ( distance ) : 정점까지의 거리

• back tracking : 더 나아갈 정점이 없으면 부모 정점으로 이동하여 다시 그 정점에서 DFS를 수행하는 과정

• 간선의 종류

• 트리간선( Tree Edge ) : DFS의 결과로 완성된 트리의 모든 간선들

• 역행간선( Back Edge ) : 트리에서 자식이 조상을 연결하는 간선들

• 순행간선( Forward Edge ) : 트리에서 조상이 자식을 연결하는 Tree Edge가 아닌 간선들

• 교차간선( Cross Edge ) : 이 외의 나머지모든 간선들

back tracking 이전 까지의 용어들은 BFS에서 사용했던 용어들이므로, 이 글을 읽다 이해가 안되시면 여기를 참고해주세요.

2. DFS( Depth-First Search )

DFS는 BFS와 달리 출발 정점(Start vertex 또는 Root vertex)으로부터 인접한 정점을 확장해나가는 방식이 아닙니다.

DFS는 인접한 정점을 모두 탐색하기는 하지만, 하나의 정점만 깊게 파고듭니다.

그리고 그 정점에 대해서도 위의 과정을 반복하는데, 더 이상 이동할 곳이 없으면 back tracking을 사용하여 부모 정점으로 이동하여 다른 정점을 깊게 파고드는 과정을 반복합니다.

DFS의 이해를 돕기 위해 그림으로 과정을 살펴보고, 수도코드를 분석해보도록 하겠습니다.

처음 시작은 v1이므로 상태를 gray로 업데이트 합니다.

그리고 1의 의미는 처음 방문한 시간을 의미하며

DFS는 두 개의 시간 즉, 처음 방문한 시간, 모든 정점을 방문한 시간(끝나는 시간)을 작성합니다.

v1에서 인접한 정점은 v2, v5가 있습니다.

BFS는 인접한 두 정점의 상태를 gray로 변경을 했는데

이와 달리 DFS는 하나의 정점에 대해서만 상태를 변경하며 또한 어떤 정점을 선택하느냐에 따라 트리의 모양이 달라집니다.

여기서는 v2정점으로 이동해보도록 하겠습니다.

점점 더 DFS는 v1 -> v2 방향으로 깊게 파고 들 것입니다.

v3의 인접 정점은 v1, v4가 있는데, v1의 상태가 gray이므로 v1을 방문하지 않습니다.

만약 v1을 방문하게 되면 cycle이 형성되기 때문에 tree가 되지 않습니다.

cycle이 형성되지 않는다는 점을 기억해주세요 ! 조금 뒤에 이와 관련된 용어를 살펴볼 것입니다.

남는 정점은 v4이므로 v4를 방문해서 v4의 상태를 gray로 변경합니다.

v4에서는 뻗어나가는 간선이 없습니다. 즉 더 이상 이동할 간선이 없는데 이러면 어떻게 할까요?

다음 Step에서 보시겠지만 더 이상 이동할 간선이 없을 때는 부모 정점(v3)으로 이동합니다.

이를 back tracking이라 합니다.

그러면 다음 단계에서 v3는 다른 인접한 정점에 대해서 또 깊이 있게 파고들 것입니다.

그리고 v4는 더 이상 방문할 정점이 없는 모든 정점을 방문한 상태이므로 시간(5)을 기록해주고,

상태를 black으로 변경합니다.

v3으로 back tracking을 했습니다.

그러나 v3에도 더 이상 방문할 정점이 없네요.

상태를 black으로 변경하겠습니다.

v2역시 마찬가지입니다.

결국 v4에서 v1까지 back tracking이 수행되었습니다.

즉 v2의 진행방향에 대해 모든 정점들을 깊이있게 탐색했습니다.

이제 다른 인접 정점에 대해 이와 같은 과정을 반복할 것입니다.

v5의 인접 정접인 v4는 상태가 black이기 때문에 방문할 수가 없습니다.

현재 그래프는 directed graph이기 때문에 v6과 v7은 방문할 수 없습니다.

그래서 v5의 상태를 black으로 변경합니다.

v1으로 back tracking했습니다.

v1 역시 더 이상 방문할 정점이 없네요.

v1의 상태를 black으로 변경합니다.

그런데 그 다음은 어떻게 해야 할까요?

수도코드를 보시면 아시겠지만, DFS는 모든 정점에 대해 탐색을 수행합니다.

즉 v1, v2, v3, v4, v5는 상태가 black이기 때문에 탐색을 수행하지 않고,

남아 있는 정점인 v6, v7에 대해 위의 과정을 수행합니다.

v6, v7 정점 중 아무거나 선택해도 되지만 여기서는 v6을 선택하겠습니다.

v7을 선택하면 결과가 달라지겠죠?

이후의 과정은 Step1 ~ Step10의 과정을 반복하므로 생략하도록 하겠습니다.

위 그림은 DFS 결과를 트리로써 표현한 것입니다.

BFS는 하나의 트리를 형성했지만, DFS는 여러개의 트리를 생성할 수 있습니다.

즉 DFS는 숲(forest)를 형성합니다.

DFS는 한 정점을 깊게 파고드는 방법으로 검색을 수행합니다.

더 이상 연결된 정점이 없거나, 나아갈 수 있는 정점이 없으면 부모 정점으로 이동해서 다시 DFS를 수행하는 back tracking을 합니다.

또한 DFS는 시작 정점의 위치, 또는 방문하는 순서에 따라 트리의 결과가 달라진다는 특징이 있으며 forest를 형성합니다.

다음으로는 간선의 종류에 대해서 알아보도록 하겠습니다.

3. 간선의 종류

1) 트리간선( Tree Edge )

트리간선은 Step14의 빨간색의 간선들 그 자체 입니다.

즉, DFS의 결과로 완성된 트리를 이루고 있는 간선들을 의미합니다.

2) 역행간선( Back Edge )

역행간선은 트리 내에서 자식이 조상을 연결하는 간선을 의미합니다.

Tree1에서 v3은 v1의 자손임을 알 수 있습니다.

그리고 Step4의 Graph를 보시면 간선( v3, v1 )이 존재합니다.

( v3, v1 ) 간선을 연결하면 cycle이 형성된다고 했는데요, back edge를 연결하면 cycle이 형성되는 성질이 있습니다.

v4역시 v1의 자식이지만 Graph 상에서 ( v4 , v1 )이 존재하지 않으므로 ( v4 , v1 ) back edge를 형성하지 않습니다.

3)순행간선( Forward Edge )

순행간선은 역행간선과 달리 조상이 자식을 연결하는 edge를 의미합니다.

그런데 Tree edge 역시 조상이 자손을 연결하고 있으므로, Tree edge를 제외한 간선들입니다.

위의 예제에서는 ( v1 , v4 ) 간선이 순행간선입니다.

( v6 , v5 )는 같은 트리가 아니며 자식 부모 관계가 아니므로 순행간선이 아닙니다.

4)교차간선( Cross Edge )

교차 간선은 트리간선, 역행간선, 순행간선을 제외한 모든 간선을 의미합니다.

4. 수도 코드

1) DFS

line 1~3

모든 정점들의 상태를 white로, 부모를 NIL로 초기화

line 5~6

graph의 모든 정점에 대해서 그 정점의 상태가 white이면 DFS-Visit함수를 호출합니다.

2) DFS-Visit

line 1~3

정점이 처음 방문되면 시간을 1 증가 시키고, 상태를 gray로 변경합니다.

line 4~7

현재 정점의 인접한 모든 정점에 대해 정점의 상태가 white이면 깊이 있는 탐색을 수행을 위해서 재귀호출합니다.

line 8~10

인접한 정점들의 방문이 모두 끝나면 back tracking이 되어 상태를 black으로 변경합니다.

그리고 인접한 모든 정점을 방문한 시간을 기록합니다.

3) 시간 복잡도

DFS 함수의 5행은 총 |V|번 수행이 되며, DFS-Visit 함수를 호출합니다.

DFS-Visit 함수의 4~7행은 총 |Adj[u]|번 수행됩니다.  ( |Adj[u]| : u의 인접 정점들의 개수 )

따라서 θ(V + E)의 시간복잡도가 됩니다.

이상으로 DFS에 대해서 알아보았습니다.

DFS는 더 이상 나아갈 수 없을 때까지 한 정점을 깊게 파고듭니다.

그리고 다시 돌아올 때는 back tracking을 수행한다는 점을 기억해주세요 !