MIT - Introduction to Algorithms
- Lecture 14. Depth First Search(DFS), topological sorting 깊이 우선 탐색, 위상 정렬 Review
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/
모든 정점들을 한 번만 방문하는 것
BFS 너비 우선 탐색은 레이어를 하나씩 탐색했으며 시작점 s로부터 최단 경로를 알 수 있었다. 그러나 시작점으로부터 어떤 정점에 갈 수 없다면 최단 경로는 무한, 도달 불가
오늘 배울 DFS의 경우는 s가 도달할 수 있는 부분만 탐색하는 것이 아닌 그래프 전체를 탐색하는데 사용
BFS보다 DFS가 일반적인 방법
깊이 우선 탐색은 미로 탐색과 비슷 - recursivly explore
방문한 것을 parent dict를 통해 확인
Edge Classification
Figure 4를 이용한 코드 해석하기
C언어를 통해서는 Stack을 이용해 만듬
V = [a,b,c,d,e,f]
Adj={a:[b,d],b:[e],c:[e,f],d:[b],e:[d],f:[f]}
DFS(V, adj)를 통해 parent에 추가를 하고 DFS-visit 함수 사용
DFS-visit 함수는 재귀함수로 깊게 들어간다. 다만 parent dict을 통해 방문했는지를 확인할 수도 있고 깊게 들어간 vertex에서 부모 vertex로 나올 수 있는 근거를 마련할 수도 있다.
b->e (parent node : a)
e->d (parent node : e)
d->b 갈 수 없음 b는 이미 방문 skip - 다음 단계 위로 올라감 : 현재 위치 e
backtrack e
backtrack b
backtrack a(이미 d는 방문했으므로 재귀를 끝냄)
b로 이동(e 가봤으니 다음으로)
c로 이동 s2 설정
c->f (parent node : c)
f loop 이미 방문 되돌아감
O(V+E) linear time 모든 정점들을 한 번씩 방문
$O(\sum_{v \in V} |Adj[v]|)=O(E)$
forward edge : node->descendant in tree
backward edge : node->ancestor in tree
cross edge : between two non-ancestor-related subtrees
Edges는 크게 2개로 분류가 가능하다.
NonTree Edges : forward edge, backward edge, cross edge
Tree Edges : NonTree edge들을 제외한 나머지 일반 Edges
무방향간선에서는 forward, cross edge가 불가능, backward 가능, tree edge 가능
예) 무방향 그래프에서 순방향 간선 forward는 불가능, backward는 가능
Cycle
v0를 시작으로 가정한다면 (vk,v0)를 back edge라 주장 가능
start v0 ... start vk ... finish vk ... finish v0 : (...(...)...)
재귀의 형태
start v0 ... start vk ...
