미로를 탐험하는 것과 같다.
깊이 우선 탐색 알고리즘
- 막다른 골목까지 경로를 따라간다
- 탐색되지 않은 이웃에 도달할 때까지 빵 부스러기를 따라 역추적한다
- 재귀적으로 탐색한다
- 정점을 반복하지 않도록 조심한다
parent = {s:None}
DFS-visit(V,Adj,s):
for v in Adj[s]:
if v not in parent:
parent[v]=s
DFS-visit(V,Adj,v)
DFS(V,Adj)
parent={}
for s inV:
if s not in parent:
parent[s]=None
DFS-visit(V,Adj,s)
- 이 분류를 계산하기 위해(역방향 또는 방향), 정점을 스택 상에 있는 동안 표시한다.
- 무방향 그래프에서는 트리 간선과 역방향 간선만 있다.
분석
- 깊이 우선 탐색 방문은 DFS-visit gets called with a vertex s only one (parent[s]가 설정되기 때문에)
깊이 우선 탐색 방문 시간
- 깊이 우선 탐색 외부 루프는 O(V)를 더한다. => O(V+E)시간 (선형 시간)
순환 검출
- 그래프 G는 순환이 있다 <=> 깊이 우선 탐색은 역방향 간선이 있다.
-
vi 방문이 끝나기 전, vi+1을 방문하고 끝낼 것이다. (vi,vi+1) 간선을 고려한다. => vi+1을 지금 방문하거나 이미 방문했을 것이다.
-
v0 방문이 끝나기 전, vk를 방문할 것이다(& 전에 방문한 적이 없다)
-
vk(또는 v0) 방문이 끝나기 전, (vk,v0) 간선을 역방향 간선으로 볼 것이다
잡 스케줄링
주어진 비순환성 방향 그래프 (DAG)에서, 정점은 할 일이고 간선은 의존 상태를 의미할 때, 의존 상태를 위반하지 않고 할 일을 정렬한다.
소스 = 들어오는 간선이 없는 정점 = 처음 (A,G,I)때 스케줄을 짤 수 있다.
각 소스에서 너비 우선탐색:
- A에서 A,BH,C,F를 찾는다.
- D에서 D, BE, CF를 찾는다.- 느리고 틀렸다.
- G에서 G, H를 찾는다.
- I에서 I를 찾는다.
위상 정렬
깊이 우선 탐색 마무리 시간의 역(깊이 우선 탐색(v)가 끝나는 시간)
정확성
어떤 간선(u,v)에 대해서 u는 v 이전에 정렬된다. 예: u전에 v가 끝난다
- 만약 v전에 u가 방문되면:
- u방문이 끝나기 전, v를 방문할 것이다. (u,v)를 통하거나다른 방법을 통해
- u전에 v가 끝난다
- 만약 u전에 v가 방문되면:
- 그래프는 비순환적이다
- v에서 u로 도달할 수 없다
- u를 방문하기 전에 v방문이 끝난다
출처