DFS 의 간선 종류
- Tree edge: DFS 트리의 간선
- Back edge: 조상(ancestor)으로 가는 간선
- Cross edge: 둘 다 아닌 간선
DFS spanning tree에는 cross edge가 없음!
DFS는 “한 길로 깊게” 들어가서 스택처럼 돌아오기 때문에,
DFS 도중에 만나는 이미 방문된 정점은 보통 내 조상(ancestor) 이거나 내 자식/후손 쪽이어서, “옆 가지(완전 다른 가지)”로 튀는 cross 형태가 없다.
Root 는 자식이 2개 이상이라면 단절점이고 Root 가 아닌 U 같은 경우, 자식 서브 트리가 U의 조상으로 올라가는 back edge가 없을 시 u는 단절점이다!
d
/ \
b f
/ \ |
a c h
| \
e g
back edge:
- e → d
- f → g → (조상 쪽) (그림 오른쪽 점선 묶음)
여기서 node e 는 단절점이 아니다. 왜냐면 우회가 가능하기 때문에
c 도 단절점이 아니다. c 의 자손이 back edge 가 있어서
node a 는 경로가 하나뿐이기 때문에 부모를 삭제할 시 단절점!
루트를 d로 잡는다.
d → b → a → (back) → c → e → (back) → f → h → g
의 순서라면
정점dfn
| d | 0 |
| b | 1 |
| a | 2 |
| c | 3 |
| e | 4 |
| f | 5 |
| h | 6 |
| g | 7 |
low(v) =
min(
dfn(v),
back edge로 연결된 조상의 dfn,
자식들의 low 값
)
이 정의에 따르면
F 같은 경우 dfn 의 값이 5 이다.
f 에서 왼쪽으로 가는 backedge 는 없기 때문에 5임.
자식들 중에 있으면 0 인데, g 가 아무리 가봤자 f 이므로
그래서 h도 마찬가지로 5
g도 마찬가지로 5!
b는 자식 노드 중 backedge 가 있으므로 0!
c도 마찬가지!
다만 a는 자식 노드가 없음. 그래서 자신의 bfs 숫자인 2의 값을 가지게 된다.