[algorithm]dfs
DFS
그래프 탐색에서 사용되는 방법
그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점을 하나씩 탐색.
-
DFS: 시작정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더이상 갈 곳 이 없게되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법.
-
가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로
- 1.재귀적으로 구현
- 2.후입선출 구조의 스택 사용
G: 그래프, adj:인접리스트
DFS(v){ // v:탐색정점
visited[v] = true
for(Node n : adj[v]){
if(!visited[n]){
DFS(n)
}
}
}
특징
-
DFS의 경우 어떤 노드를 방문했는지 반드시 검사해야한다.검사하지 않을 경우 무한루프에 빠질 위험이 있다. 재귀함수 시작에서 방문처리를 하고 호출하기전에 검사한다.
-
깊이우선탐색(DFS)가 너비우선탐색(BFS) 보다 좀 더 간단하다. 단순검색속도는 BFS에 비해 느리다
- 인접리스트 O(N+E)
- 인접행렬 O(N^2)
따라서 그래프 내에 적은 숫자의 간선을 가지는 희소그래프의 경우 인접행렬이 아닌 인접리스트를 사용하는 것이 유리하다.