[Graph] DFS 그래프 깊이 우선 탐색

그래프의 탐색 알고리즘은 특정 정점을 찾아낸다기 보다는 정점들을 정해진 순서대로 둘러보기 위한 알고리즘으로 이해하는 것이 맞다. 가장 유명한 깊이 우선탐색과 너비 우선탐색의 컨셉과 문제상황들을 살펴본다.

 

깊이 우선 탐색

현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라간다. 더이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다 (재귀호출로 구현한다. 그러면 종료하고 호출시점으로 돌아간다). 가능한 한 그래프 안으로 '깊이'  들어가려고 시도하는 알고리즘이다. 

 

알고리즘의 큰 틀

# 슈도 코드

# 인접 리스트 or 인접 행렬
adj = []
# 정점의 방문 여부 리스트 - false 로 초기화
visited = []

def dfsAll():
# 1. 그래프가 여러개의 부분 그래프로 이뤄진 경우 빼먹지 않기 위해 차례대로 DFS 호출
    for node in nodes:
        if not visited[node]:
            dfs(node)

def dfs(here):
# 2. 방문 여부 업데이트
    visited[here] = True
# 3. 인접리스트 중 방문하지 않은 노드가 있다면 DFS (재귀)호출
    for there in adj[here]:
        if not visited[there]:
            dfs(there)

시간 복잡도

1. dfs() 함수를 호출하는 부분
2. dfs() 내부에서 인접 간선을 검사하는 for문

1번의 경우 한 노드마다 한 번씩 호출되므로 시간복잡도는 O(|V|) 이다. 2번의 경우까지 포함해서 시간복잡도를 계산하면, 인접리스트로 구현했는지 인접행렬로 구현했는지에 따라 조금 다르다.

인접리스트로 구현한 경우 최종 시간 복잡도는 O(|V| + |E|). 인접행렬로 구현한 경우 최종 시간 복잡도는  O(|V|^2).

 

DFS 역으로 이용하기

1. 두 정점이 서로 연결되어 있는가 확인하기
   dfs(u)를 수행하고 visited[]를 보면 확인 가능하다.
2. 연결된 부분집합의 개수 세기
   dfsAll()에서 dfs()를 호출하는 횟수를 세면 그래프가 몇 개의 컴포넌트로 이루어져 있는지 확인 가능하다.
3. 위상 정렬 (쉽게 말해 의존성이 있는 작업들 순서정리!)
   제시된 문제를 방향으로 표현한 의존성 그래프를 보면 사이클이 없는 형태의 DAG 이다.
   가장 직관적인 방법은 들어오는 간선이 없는 정점들을 하나씩 찾아서 정렬 결과의 뒤에 붙이고, 그래프에서 이 정점을 지우는 과정을 반복하는 것이다.
   DFS 를 사용한다면 더 간단하게 구현이 가능하다. 직관적으로 생각했을 때, 재귀호출을 종료하고 돌아가는 노드라면 DFS의 끝에 있는 노드이기 때문에 호출시점으로 돌아가는 노드들을 역순으로 정렬하면 될 것이다.
   • dfsAll()을 수행하며 dfs()가 종료할 때마다 현재 정점의 번호를 기록
   • dfsAll()이 종료하고 나서 기록된 순서를 역순으로 정렬
   • 그러면 항상 적절한 위상정렬의 결과가 나온다.

근데 만약 방향 그래프에서 시작하는 노드가 살짝 달라짐에 따라 답이 원하는 바와 같이 나오지 않을 수 있다.

0번 노드와 2번 노드 위치만 바꿨는데 다른 결과가 나올 수 있다.

문제	왼쪽	오른쪽
0번과 2번이 연결되어 있는가?	0번과 2번은 연결되어 있지 않다	0번과 2번은 연결되어 있다
부분 그래프는 몇개인가?	2개	1개
위상정렬의 결과는 어떻게 되는가?	2 → 0 → 3 → 1	0 → 2 → 3 → 1