그래프 순회: BFS, DFS, SCC

Opening Hook: 그래프 문제는 결국 '갈 수 있나, 어떤 순서로 보나, 어디를 묶나'입니다

BFS, DFS, SCCs를 처음 보면 이름이 네 개라서 흩어진 주제처럼 느껴집니다. 하지만 시험장에서 실제로 묻는 질문은 세 가지로 정리됩니다. 첫째, 어떤 정점(vertex, Knoten)에서 다른 정점으로 갈 수 있는가? 이것이 path(Pfad)와 reachability(Erreichbarkeit)입니다. 둘째, 갈 수 있는 정점들을 어떤 순서로 방문할 것인가? 여기서 BFS(Breadth-First Search, Breitensuche)는 가까운 층부터 보고, DFS(Depth-First Search, Tiefensuche)는 한 길을 끝까지 파고듭니다. 셋째, 방문 순서에서 어떤 구조를 뽑아낼 것인가? DFS finish time은 topological sorting으로 이어지고, directed graph에서 왕복 가능한 묶음은 SCC(strongly connected component, starke Zusammenhangskomponente)로 이어집니다.

초보자가 가장 먼저 버려야 할 생각은 '그래프는 그림이다'입니다. 그림은 이해를 돕지만 알고리즘은 그림의 위치를 보지 않습니다. 강의의 graph definition처럼 graph는 \(G=(V,E),\)G=(V,E),즉 vertex set V와 edge set E입니다. Directed graph에서는 (u,v)와 (v,u)가 완전히 다릅니다. 그림에서 u와 v가 가까워 보여도 edge가 없으면 갈 수 없고, edge 방향이 반대면 그 방향으로는 갈 수 없습니다. 시험에서 틀리는 많은 답은 바로 이 지점에서 나옵니다. 그림의 직관을 믿고 방향, discovered 상태, finish time, component maximality를 놓치는 것입니다.

오늘의 목표는 코드를 외우는 것이 아닙니다. 각 알고리즘이 유지하는 상태(state)를 말할 수 있어야 합니다. BFS는 queue Q, color, dist, pred를 유지합니다. DFS는 color, predecessor, discovery time d, finish time f를 유지합니다. Topological sort는 DFS의 finish order를 이용합니다. SCC/Kosaraju는 DFS finish order와 \(\text{transpose} \text{graph} G^{T}\)transpose graph Gᵀ를 이용합니다. 이 상태들이 왜 필요한지 설명할 수 있으면, pseudocode가 약간 바뀌어도 시험에서 흔들리지 않습니다.

선수 개념과 용어 지도

필수 어휘를 먼저 고정합시다. Graph(Graph)는 vertex/Knoten들의 집합 V와 edge/Kante들의 집합 E로 이루어진 구조입니다. Directed graph(gerichteter Graph)는 edge가 방향을 가집니다. 보통 E subseteq V x V로 쓰고, (u,v) in E는 u에서 v로 가는 edge가 있다는 뜻입니다. Undirected graph(ungerichteter Graph)는 방향을 무시하거나 양방향 edge로 생각합니다. 강의 자료는 undirected graph에서 (u,v) in E iff (v,u) in E라는 대칭 조건을 설명합니다.

Path(Pfad)는 edge를 따라 이동하는 vertex sequence입니다. (w1,...,wk)가 u에서 v로 가는 path라면 \(w1=u, \text{wk}=v\)w1=u, wk=v이고, 각 i에 대해 (wi,w{i+1})가 edge여야 합니다. Directed graph에서는 반드시 edge 방향을 따라야 합니다. Path length는 보통 edge 개수 k-1입니다. Empty path 때문에 모든 vertex는 자기 자신에게 reachable입니다. 이 작은 사실은 SCC 정의에서 중요합니다. Vertex 하나만 있어도 자기 자신과는 왕복 가능하므로 단일 vertex SCC가 될 수 있습니다.

Representation도 알아야 합니다. Adjazenzmatrix(adjacency matrix)는 \(A[i,j]=1\quad\Longleftrightarrow\quad \text{edge} i \rightarrow j\)A[i,j]=1 iff edge i → j가 존재한다고 두는 |V| x |V| 표입니다. Edge existence query는 빠르지만 sparse graph에도 \(\Theta(|V|^2)\)Θ(|V|²) 공간을 씁니다. Adjazenzliste(adjacency list)는 각 vertex u마다 outgoing neighbor list adj(G,u)를 둡니다. 전체 공간은 \(\Theta(|V|+|E|)\)Θ(|V|+|E|)입니다. 강의의 BFS/DFS runtime \(O(|V|+|E|)\)O(|V|+|E|)는 adjacency list를 순회한다는 전제가 깔려 있습니다. Matrix로 모든 가능한 neighbor를 매번 검사하면 같은 알고리즘 아이디어라도 구현 시간은 달라질 수 있습니다.

마지막으로 color convention입니다. WHITE는 아직 발견되지 않은 vertex, GRAY는 발견되었지만 처리가 완전히 끝나지 않은 vertex, BLACK은 adjacency scan이 끝난 vertex입니다. BFS와 DFS 모두 color를 쓰지만 의미의 느낌이 다릅니다. BFS에서 GRAY는 queue에 있거나 queue에서 나와 neighbor 처리 중인 상태입니다. DFS에서 GRAY는 recursion stack 위에 있는 상태입니다. 이 차이가 edge classification과 cycle detection에서 결정적입니다.

BFS Core Idea: Queue가 level 순서를 보존합니다

BFS(Breitensuche)는 source s에서 시작해 edge 0개로 닿는 곳, edge 1개로 닿는 곳, edge 2개로 닿는 곳을 차례로 방문합니다. 이 순서를 보장하는 자료구조가 queue(Warteschlange)입니다. Queue는 FIF\(O(\text{first} \text{in}, \text{first} \text{out})\)O(first in, first out)입니다. 먼저 발견한 vertex가 먼저 처리됩니다. Source의 neighbor들은 모두 \(\text{dist}=1\)dist=1로 queue 뒤에 들어가고, 이 \(\text{dist}=1 \text{vertex}\)dist=1 vertex들이 처리되기 전에는 \(\text{dist}=2 \text{vertex}\)dist=2 vertex가 먼저 처리될 수 없습니다. 그래서 BFS는 unweighted graph에서 shortest edge count를 계산합니다.

BFS 상태는 color[v], dist[v], pred[v]입니다. 초기에는 모든 vertex가 \(\text{WHITE}, \text{dist}=\text{infinity}, \text{pred}=\text{NIL}\)WHITE, dist=infinity, pred=NIL입니다. Source s만 \(\text{GRAY}, \text{dist}[s]=0, \text{pred}[s]=\text{NIL}\)GRAY, dist[s]=0, pred[s]=NIL이 되고 queue에 들어갑니다. 반복문은 queue가 빌 때까지 dequeue u를 하고, u의 adjacency list를 scan합니다. WHITE neighbor v를 처음 발견하면 \(v.\text{color}=\text{GRAY}, \text{dist}[v]=\text{dist}[u]+1, \text{pred}[v]=u\)v.color=GRAY, dist[v]=dist[u]+1, pred[v]=u로 설정하고 enqueue(v)합니다. u의 모든 neighbor 처리가 끝나면 \(u.\text{color}=\text{BLACK}\)u.color=BLACK입니다.

시험에서 중요한 invariant는 '처음 발견될 때 정해진 dist가 최단 edge count다'입니다. 왜냐하면 queue가 작은 dist부터 처리하기 때문입니다. dist d인 vertex를 처리할 때 새로 발견되는 vertex는 dist d+1입니다. dist d+2 vertex가 먼저 queue 앞에 올 수 없습니다. 따라서 어떤 vertex v가 처음 발견되는 순간, 더 짧은 경로가 나중에 나타날 가능성은 없습니다. 만약 더 짧은 경로가 있었다면 그 경로의 직전 vertex가 더 작은 dist로 더 먼저 처리되어 v를 이미 발견했어야 합니다.

단, 여기서 shortest는 weight sum이 아닙니다. 강의의 weighted graph는 edge마다 w:\(E\rightarrow R\)E→R같은 weight를 붙입니다. BFS dist는 edge 개수 기준입니다. 모든 edge cost가 동일할 때는 의미 있는 shortest path가 되지만, edge weight가 다르면 Dijkstra나 Bellman-Ford의 영역입니다. MC에서 'BFS finds shortest paths'라는 문장은 graph가 unweighted인지, shortest의 의미가 edge count인지 확인해야 합니다.

BFS Worked Table: Sheet09 G3(a) 스타일로 손으로 채우기

Sheet09의 BFS/DFS 문제는 알고리즘을 말로 아는지보다 표를 안정적으로 채우는지를 봅니다. 예를 들어 directed graph에서 source C이고 edge가 \(C\rightarrow B, C\rightarrow E, C\rightarrow F, B\rightarrow D, B\rightarrow G, F\rightarrow A\)C→B, C→E, C→F, B→D, B→G, F→A라고 합시다. 시작은 C만 \(\text{GRAY}, \text{dist}(C)=0, \text{pred}(C)=\text{NIL}, \text{queue}=[C]\)GRAY, dist(C)=0, pred(C)=NIL, queue=[C]입니다.

1회차에서 C를 dequeue합니다. C의 WHITE neighbors B,E,F를 순서대로 발견합니다. 각각 \(\text{dist}=1, \text{pred}=C\)dist=1, pred=C가 되고 \(\text{queue}=[B,E,F]\)queue=[B,E,F]입니다. C는 BLACK입니다. 2회차에서 B를 dequeue합니다. B의 WHITE neighbors D,G를 발견하므로 \(\text{dist}(D)=\text{dist}(G)=2, \text{pred}(D)=\text{pred}(G)=B, \text{queue}=[E,F,D,G]\)dist(D)=dist(G)=2, pred(D)=pred(G)=B, queue=[E,F,D,G]입니다. 3회차 E는 새 WHITE neighbor가 없어서 \(\text{queue}=[F,D,G]\)queue=[F,D,G]가 됩니다. 4회차 F에서 A를 발견하므로 \(\text{dist}(A)=2, \text{pred}(A)=F, \text{queue}=[D,G,A]\)dist(A)=2, pred(A)=F, queue=[D,G,A]입니다. 이후 D,G,A는 새 vertex를 발견하지 못하고 queue는 [G,A], [A], []로 줄어듭니다.

이 예시에서 final dist는 \(C=0, B/E/F=1, D/G/A=2\)C=0, B/E/F=1, D/G/A=2입니다. pred tree는 C가 B,E,F의 predecessor이고, B가 D,G의 predecessor이며, F가 A의 predecessor입니다. 손풀이에서 queue snapshot을 빠뜨리면 dist/pred가 맞아도 감점 위험이 큽니다. 특히 이미 GRAY 또는 BLACK인 vertex를 다시 만났을 때 pred를 바꾸지 않는다는 점을 지켜야 합니다. BFS는 '처음 발견'이 중요합니다. 나중에 더 예뻐 보이는 경로가 와도 BFS 표에서는 이미 발견된 vertex의 dist/pred를 업데이트하지 않습니다.

이 표를 말로 설명할 때는 매 줄마다 네 가지를 말하면 됩니다. dequeue된 u, 새로 발견한 WHITE neighbors, queue after iteration, 새 dist/pred assignments입니다. 이 형식은 sheet solution과 잘 맞고 oral exam에서도 깔끔합니다.

DFS Core Idea: 들어간 시간과 빠져나온 시간이 구조를 만듭니다

DFS(Tiefensuche)는 현재 vertex u에서 아직 WHITE인 neighbor v가 보이면 즉시 v로 들어갑니다. v에서도 같은 일을 반복합니다. 더 이상 갈 WHITE neighbor가 없으면 그때 u를 finish하고 직전 호출로 돌아갑니다. 그래서 DFS는 stack 또는 recursion으로 이해하면 좋습니다. BFS가 level을 만드는 알고리즘이라면, DFS는 nested interval을 만드는 알고리즘입니다.

DFS의 두 시간은 discovery time d와 finish time f입니다. Vertex u에 처음 들어갈 때 time을 증가시키고 u.d를 찍습니다. 이때 \(u.\text{color}=\text{GRAY}\)u.color=GRAY입니다. u의 outgoing edges를 모두 확인하고 더 이상 들어갈 곳이 없으면 \(u.\text{color}=\text{BLACK}\)u.color=BLACK이 되고 time을 증가시켜 u.f를 찍습니다. 이 d/f pair가 DFS의 핵심 산출물입니다.

Interval rule은 반드시 외워야 하지만, 외우기만 하면 안 됩니다. u가 v의 ancestor라면 DFS는 u 안에 들어간 상태에서 v로 들어갔다가 v를 끝내고, 나중에야 u를 끝냅니다. 그래서 \(u.d < v.d < v.f < u.f\)u.d < v.d < v.f < u.f입니다. 즉 v의 interval [v.d,v.f]가 u의 interval [u.d,u.f] 안에 완전히 들어갑니다. 반대로 서로 다른 DFS branches는 interval이 겹치지 않습니다. 하나가 완전히 끝난 뒤 다른 branch가 시작됩니다.

DFS tree path는 shortest path가 아닙니다. DFS는 가까운 순서로 퍼지는 것이 아니라 neighbor order에 따라 깊게 들어갑니다. 강의 자료의 DFS 부분도 DFS tree paths are not necessarily shortest paths라는 경고를 줍니다. 그러므로 'DFS로 찾은 predecessor tree가 shortest path tree다'라는 주장은 일반적으로 false입니다. DFS의 강점은 shortest distance가 아니라 time interval, edge classification, topological sort, SCC 같은 구조 분석입니다.

DFS Edge Classes: color와 interval로 tree/back/forward/cross를 판정합니다

Directed DFS에서 edge (u,v)를 검사할 때 v의 상태에 따라 edge class가 정해집니다. v가 WHITE라면 아직 발견되지 않았으므로 DFS가 v로 들어가고 (u,v)는 tree edge가 됩니다. 이때 \(\text{pred}[v]=u\)pred[v]=u입니다. v가 GRAY라면 v는 현재 recursion stack 위에 있습니다. 즉 u에서 ancestor로 되돌아가는 edge이고, directed graph에서는 back edge입니다. Back edge는 directed cycle의 강한 신호입니다.

v가 BLACK이면 v의 처리는 이미 끝났습니다. 이때 v가 u의 descendant라면 forward edge입니다. Tree edge는 아니지만 u의 DFS subtree 안쪽으로 향하는 edge입니다. Interval로는 \(u.d < v.d < v.f < u.f\)u.d < v.d < v.f < u.f입니다. v가 ancestor도 descendant도 아닌 이미 끝난 다른 branch라면 cross edge입니다. Cross edge는 서로 다른 DFS branch 사이로 향합니다.

시험에서는 두 가지 방식으로 묻습니다. 첫째, 알고리즘 중 color를 보고 분류하게 합니다. 이때 WHITE/GRAY/BLACK의 의미를 즉시 말해야 합니다. 둘째, d/f table만 주고 edge를 분류하게 합니다. 이때 interval containment와 predecessor relation을 같이 봅니다. 예를 들어 v interval이 u interval 안에 있고 pred chain상 descendant이면 forward 또는 tree 후보입니다. 실제 \(\text{pred}[v]=u\)pred[v]=u이면 tree edge이고, 그렇지 않으면 forward edge입니다. Interval이 겹치지 않는 이미 끝난 branch로 가면 cross edge입니다.

Undirected DFS의 함정도 큽니다. 강의 기준으로 undirected graph에서 DFS edge는 tree edge와 back edge만 나옵니다. Directed graph의 forward/cross edge class를 그대로 undirected graph에 적용하면 MC에서 틀립니다. 이유는 undirected edge가 양방향으로 보이기 때문에 directed case처럼 별도의 forward/cross class로 독립적으로 나타나지 않고 tree/back 구조로 흡수되기 때문입니다.

Topological Sort: DAG에서 dependency를 한 줄로 세우는 DFS 응용

Topological sorting(topologische Sortierung)은 directed graph의 vertex들을 한 줄로 나열하되, 모든 edge (u,v)에 대해 u가 v보다 앞에 나오게 만드는 것입니다. 이 정의만 보면 간단하지만 전제 조건이 중요합니다. Topological order는 DAG(directed acyclic graph), 즉 directed cycle이 없는 graph에서만 가능합니다. Cycle이 있으면 u before v before ... before u 같은 모순이 생깁니다.

DFS와의 연결은 finish time입니다. DAG에서 DFS를 실행하고 vertex가 finish될 때 list의 앞에 넣거나, 모든 vertex를 finish time decreasing order로 정렬하면 topological order가 됩니다. 직관은 이렇습니다. Edge (u,v)가 있을 때, DAG에서는 v가 u의 ancestor가 되는 back edge 상황이 불가능합니다. 그래서 DFS time 관계를 따져 보면 u는 v보다 늦게 finish됩니다. 즉 \(u.f > v.f\)u.f > v.f가 되고, decreasing finish time에서는 u가 v보다 앞에 옵니다.

여기서 proof intuition은 back edge 부재입니다. Directed graph에서 DFS 중 GRAY vertex로 가는 edge가 있으면 cycle이 있습니다. DAG에는 cycle이 없으므로 그런 edge가 없습니다. 따라서 edge (u,v)는 tree/forward/cross 형태로만 나타나고, 모든 경우에서 finish time order가 dependency 방향과 맞습니다. 시험 답안에서는 'DAG이므로 back edge가 없다. 모든 edge (u,v)에 대해 \(f[u] > f[v].\)f[u] > f[v].따라서 decreasing finish time order가 topological order다' 정도로 말하면 충분합니다.

MC trap은 '모든 directed graph는 topological sort가 있다'입니다. False입니다. 또 'topological sort는 unique하다'도 일반적으로 false입니다. 서로 dependency가 없는 vertex들은 여러 순서가 가능합니다. DFS neighbor order가 바뀌면 valid topological order도 달라질 수 있습니다. 답안에서는 uniqueness를 주장하지 말고, edge condition을 만족하는 한 줄이라고 말해야 합니다.

SCC Definition: weak connectivity가 아니라 maximal mutual reachability입니다

SCC(starke Zusammenhangskomponente)는 directed graph에서 서로 왕복 가능한 vertex들의 최대 묶음입니다. Formal하게는 C 안의 임의의 u,v에 대해 u leadsto v and v leadsto u가 성립하고, 더 큰 집합으로 확장할 수 없어야 합니다(maximal). 여기서 두 조건이 모두 중요합니다. Mutual reachability만 말하면 작은 subset도 조건을 만족할 수 있습니다. Maximality가 있어야 component가 됩니다.

Weak connectivity와 구분합시다. Directed edge의 방향을 무시하면 연결되어 보일 수 있지만, SCC는 방향을 지켜야 합니다. 예를 들어 \(1\rightarrow 2\rightarrow 3\)1→2→3만 있으면 undirected로는 연결된 chain처럼 보이지만 SCC는 {1}, {2}, {3}입니다. 1에서 3으로는 갈 수 있어도 3에서 1로 돌아갈 수 없기 때문입니다. 반대로 \(1\rightarrow 2\quad\text{and}\quad 2\rightarrow 1\)1→2 and 2→1이면 {1,2}는 하나의 SCC입니다.

SCC들을 하나의 super-vertex로 압축하면 condensation graph가 됩니다. 서로 다른 SCC C와 D 사이에 \(C\rightarrow D\)C→D와 \(D\rightarrow C\)D→C가 둘 다 있으면 어떻게 될까요? C 안에서는 모든 vertex가 서로 reachable이고, D 안에서도 그렇습니다. C에서 D로 가고 D에서 C로 돌아오는 path가 있다면 C와 D 전체가 서로 reachable해져 하나의 SCC가 되어야 합니다. 따라서 서로 다른 SCC 사이에는 양방향 reachability cycle이 있을 수 없습니다. Condensation graph는 DAG가 됩니다.

이 직관은 Kosaraju의 근거입니다. SCC 내부의 edge 방향을 모두 뒤집어도 그 내부 vertex들은 여전히 서로 reachable입니다. 그래서 \(\text{transpose} \text{graph} G^{T}\)transpose graph Gᵀ는 SCC membership을 바꾸지 않습니다. 다만 SCC들 사이의 one-way 방향은 반대로 바뀝니다. Kosaraju는 이 성질과 DFS finish order를 이용해 한 SCC씩 깔끔하게 떼어냅니다.

Kosaraju Algorithm: finish order와 transpose graph를 같이 씁니다

Kosaraju 알고리즘은 SCC를 찾는 고전적인 DFS 두 번 알고리즘입니다. Step 1: 원래 graph G에서 DFS를 실행하고 각 vertex의 finish time을 기록합니다. Step 2: 모든 edge 방향을 뒤집어 \(\text{transpose} \text{graph} G^{T}\)transpose graph Gᵀ를 만듭니다. Step 3: 첫 DFS의 finish time decreasing order로 \(G^{T}\)Gᵀ에서 DFS를 실행합니다. Step 4: 두 번째 DFS forest의 각 tree가 하나의 SCC입니다.

왜 순서가 중요할까요? SCC condensation graph를 생각하면 됩니다. 원래 G에서 source 쪽 component에서 sink 쪽 component로 edge가 흐를 수 있습니다. 첫 DFS의 finish time은 component DAG의 구조를 반영합니다. 가장 큰 finish time을 가진 vertex가 있는 component를 \(G^{T}\)Gᵀ에서 먼저 시작하면, transpose에서는 원래 들어오던 방향과 나가던 방향이 뒤집혀서 그 component 밖으로 잘못 새어 나가지 않게 됩니다. 그래서 두 번째 DFS tree가 정확히 하나의 SCC에 머무릅니다.

초보자는 보통 두 가지 실수를 합니다. 첫째, 두 번째 DFS도 원래 G에서 돌립니다. 그러면 Kosaraju가 아닙니다. 반드시 \(G^{T}\)Gᵀ에서 돌려야 합니다. 둘째, 두 번째 DFS의 시작 순서를 아무 순서로 해도 된다고 생각합니다. 이것도 틀립니다. 첫 DFS의 finish time decreasing order가 필요합니다. 순서를 잃으면 한 DFS tree가 여러 SCC를 삼켜 버릴 수 있습니다.

Runtime은 adjacency list 기준 \(O(|V|+|E|)\)O(|V|+|E|)입니다. 첫 DFS가 \(O(|V|+|E|)\)O(|V|+|E|), transpose graph 생성도 모든 edge를 한 번 뒤집으므로 \(O(|V|+|E|)\)O(|V|+|E|), 두 번째 DFS도 \(O(|V|+|E|)\)O(|V|+|E|)입니다. 상수 배를 합쳐도 \(O(|V|+|E|)\)O(|V|+|E|)입니다. Matrix representation이면 transpose는 쉬워 보일 수 있지만 공간과 scan cost가 달라지므로, 강의의 standard bound는 adjacency list 기준이라고 말하는 습관이 좋습니다.

Proof Intuition: BFS level, DFS interval, SCC condensation을 따로 증명합니다

BFS correctness intuition은 queue invariant입니다. Queue 안의 vertex들은 dist가 감소하지 않는 순서로 들어 있습니다. dist d인 vertex를 처리할 때 새로 발견되는 vertex는 dist d+1입니다. 더 짧은 path가 있었다면 그 path의 직전 vertex가 더 작은 dist로 먼저 처리되었어야 하므로, 처음 발견된 dist가 최단 edge count입니다. 이 proof는 unweighted edge count에만 해당합니다.

DFS interval proof는 recursion stack입니다. u를 discover한 뒤 finish하기 전까지 u는 stack 위에 남아 있습니다. 그 사이 v를 discover하고 finish하면 v interval은 u interval 안에 들어갑니다. 서로 다른 branches는 한 branch가 완전히 finish된 뒤 다음 branch로 넘어가므로 interval이 겹치지 않습니다. 따라서 d/f table만으로 ancestor relation을 읽을 수 있습니다.

Topological sort proof는 DAG의 no back edge입니다. DFS에서 edge (u,v)가 있는데 \(f[u] \le f[v]\)f[u] ≤ f[v]가 되려면 v가 u의 ancestor처럼 동작하는 경우가 필요합니다. DAG에서는 back edge가 없으므로 모든 edge가 decreasing finish time order와 일치합니다. 그러므로 finish time decreasing order가 모든 dependency edge를 왼쪽에서 오른쪽으로 보냅니다.

SCC/Kosaraju proof intuition은 condensation DAG와 transpose입니다. SCC 내부는 transpose해도 SCC입니다. Component 사이 edge 방향만 뒤집힙니다. 첫 DFS finish order는 component DAG의 sink/source 관계를 드러냅니다. 그 순서로 \(G^{T}\)Gᵀ를 DFS하면 아직 방문하지 않은 component 중 하나를 정확히 떼어냅니다. 시험에서는 완전한 formal proof보다 이 세 문장을 정확히 말하는 것이 중요합니다: SCC membership은 transpose에서 보존된다, component graph는 DAG다, second DFS order는 first finish time decreasing order다.

Exam Strategy: 표 문제와 MC 문제를 분리해서 풉니다

Sheet09 스타일 표 문제는 손을 움직이는 순서가 점수입니다. BFS라면 초기화, queue, dequeue vertex, newly discovered WHITE neighbors, final color/dist/pred를 표로 씁니다. DFS라면 neighbor order를 먼저 확인하고, discovery/finish time, predecessor, edge classification을 차례로 씁니다. Neighbor order가 문제에 주어졌는데 무시하면 결과 전체가 달라질 수 있습니다.

MC 문제는 문장 속 scope를 봅니다. 'BFS finds shortest path'는 unweighted인지 확인합니다. 'DFS uses queue'는 false이고 stack/recursion이 맞습니다. 'In undirected graph DFS creates only tree and back edges'는 강의 기준 true입니다. 'In a DAG DFS can have cross edges'는 directed DAG에서는 possible입니다. Back edge는 cycle을 만들지만 cross edge는 DAG에서도 생길 수 있습니다. 이 distinction은 2025 memory protocol의 graph algorithms MC와도 잘 맞는 함정입니다.

Topological sort 문장에서는 DAG requirement, edge direction condition, uniqueness 여부를 봅니다. SCC 문장에서는 strong vs weak connectivity, maximality, transpose preserving membership, Kosaraju order를 봅니다. 특히 'transpose changes SCCs'는 false입니다. Transpose는 reachability direction을 모두 뒤집지만 SCC 내부의 mutual reachability는 그대로 유지됩니다.

답안 작성에서는 German/English term을 같이 붙이면 좋습니다. 예: 'BFS(Breitensuche)는 queue(Warteschlange)를 사용하고, dist[v]는 unweighted shortest edge count입니다.' 이렇게 쓰면 개념과 강의 용어가 동시에 잡힙니다. 구두시험에서는 한 문장 정의, 상태 변수, invariant, runtime, trap 순서로 말하면 안정적입니다.

Representation Deep Dive: matrix/list 선택이 알고리즘 설명을 바꿉니다

Graph algorithm을 처음 배울 때 많은 학생이 BFS/DFS runtime \(O(|V|+|E|)\)O(|V|+|E|)만 외웁니다. 하지만 이 bound는 representation과 함께 말해야 정확합니다. Adjazenzliste(adjacency list)에서는 각 vertex u에 대해 실제 outgoing neighbors만 저장합니다. BFS나 DFS가 u를 처리할 때 adj(G,u)를 한 번 scan하고, 전체 실행 동안 모든 adjacency list 길이를 합치면 directed graph에서는 |E|, undirected graph에서는 보통 2|E| 정도입니다. 그래서 vertex initialization \(O(|V|)\)O(|V|)와 edge scan \(O(|E|)\)O(|E|)를 합쳐 \(O(|V|+|E|)\)O(|V|+|E|)가 됩니다.

Adjazenzmatrix(adjacency matrix)는 생각이 다릅니다. A[i,j]를 보면 \(\text{edge} i\rightarrow j\)edge i→j존재 여부를 \(O(1)\)O(1)에 알 수 있습니다. 하지만 u의 모든 outgoing neighbors를 찾으려면 row u의 모든 j를 훑어야 합니다. Vertex가 \(n=|V|\)n=|V|개라면 한 row scan은 \(O(|V|)\)O(|V|)이고, 모든 vertex에서 반복하면 \(O(|V|^2)\)O(|V|²)가 됩니다. Dense graph에서는 |E|가 |\(V|^2\)V|²에 가까워 큰 차이가 안 날 수 있지만, sparse graph에서는 adjacency list가 훨씬 효율적입니다. 따라서 시험에서 'BFS is \(O(|V|+|E|)\)O(|V|+|E|)'라고만 쓰지 말고, 가능하면 'using adjacency lists'를 붙이세요.

Sheet09 G2 같은 representation 문제는 단순 변환 문제가 아닙니다. Matrix에서 list를 만들 때 directed graph라면 row i에서 1인 column j를 i의 outgoing list에 넣습니다. Undirected graph로 해석하면 matrix가 symmetric이어야 하고, list에도 양쪽 방향이 반영됩니다. Self-loop가 있으면 diagonal entry가 1이 됩니다. Isolated vertex는 list가 empty일 수 있지만 V에는 여전히 존재합니다. BFS/DFS initialization에서 isolated vertex도 color WHITE로 초기화해야 하고, DFS 전체 실행에서는 disconnected graph의 isolated vertex도 나중에 새 DFS tree root가 될 수 있습니다.

초보자에게 좋은 mental model은 'matrix는 전체 지도 표, list는 각 정점의 출구 목록'입니다. 출구 목록을 들고 있으면 실제로 나갈 수 있는 길만 확인하므로 traversal에 좋습니다. 전체 지도 표는 특정 두 정점 사이 edge가 있는지 빠르게 확인하는 데 좋습니다. 둘 중 무엇이 항상 좋다고 외우지 말고, operation이 edge query인지 neighbor iteration인지 구분하세요.

BFS Proof More Slowly: 왜 first discovery를 믿어도 되는가

BFS proof에서 핵심 문장은 '처음 발견했을 때 dist가 최단 거리다'입니다. 이 문장이 직관적으로는 맞아 보여도, 시험에서 설명하려면 queue order를 말해야 합니다. Source s의 dist는 0입니다. s를 dequeue하면 s의 모든 WHITE neighbor는 dist 1이 됩니다. 이 neighbor들은 queue 뒤에 들어가지만, queue 안에는 dist 0보다 작은 것이 없고 dist 2도 아직 들어갈 수 없습니다. dist 2 vertex는 dist 1 vertex가 dequeue되어야만 발견됩니다.

일반화하면 queue에는 dist가 작은 vertex가 앞쪽, 같거나 하나 큰 vertex가 뒤쪽에 놓입니다. dist d vertex를 꺼내 처리할 때 새로 들어가는 vertex는 dist d+1입니다. 이미 queue 안에 있던 dist d 또는 d+1 vertex보다 더 작은 dist가 갑자기 뒤에서 나오지 않습니다. 그래서 BFS는 level by level traversal입니다. 이 level 구조 때문에 first discovery가 안전합니다.

반대로 생각해 봅시다. 어떤 vertex v가 처음 발견되어 \(\text{dist}[v]=k\)dist[v]=k가 되었습니다. 그런데 실제 shortest edge count가 k보다 작다고 가정합시다. 그러면 s에서 v까지 길이 k-1 이하인 path가 있고, 그 path에서 v 바로 직전 vertex x는 source에서 k-2 이하 거리입니다. BFS는 x를 v를 발견한 vertex보다 먼저 처리했어야 합니다. x를 처리할 때 v가 WHITE였다면 v를 더 작은 dist로 발견했을 것입니다. v가 WHITE가 아니었다면 이미 더 먼저 발견된 것입니다. 둘 다 contradiction입니다. 그래서 first discovery distance가 shortest edge count입니다.

이 proof가 weighted graph에서 깨지는 지점도 이해해야 합니다. BFS는 모든 edge를 cost 1로 취급합니다. Edge 하나가 cost 100이고 edge 두 개가 cost 2인 상황에서 BFS는 edge 하나 경로를 더 짧다고 봅니다. Weight sum을 최소화하려면 priority queue와 relaxation을 쓰는 Dijkstra나, negative edge를 다룰 수 있는 Bellman-Ford 같은 다른 invariant가 필요합니다. 따라서 BFS proof의 전제는 'unweighted' 또는 'all edges have equal weight'입니다.

DFS Proof More Slowly: recursion stack이 모든 것을 설명합니다

DFS를 표로만 외우면 discovery/finish time이 이상한 숫자놀이처럼 보입니다. 하지만 recursion stack을 떠올리면 자연스럽습니다. DFS-VISIT(u)가 호출되면 u는 stack에 올라갑니다. 이 순간 u.d가 찍히고 color는 GRAY입니다. u의 neighbor v가 WHITE이면 DFS-VISIT(v)를 호출합니다. 이제 v가 stack top입니다. v가 끝나기 전에는 u 호출이 끝날 수 없습니다. 따라서 v.f는 u.f보다 먼저 찍힙니다.

이 구조가 interval theorem입니다. u가 v의 ancestor이면 u.d가 먼저, v.d가 그 다음, v.f가 그 다음, u.f가 마지막입니다. 숫자로 \(u.d < v.d < v.f < u.f\)u.d < v.d < v.f < u.f입니다. 반대로 이 부등식이 성립하면 v의 전체 실행이 u의 실행 안에서 일어난 것이므로 u가 v의 ancestor입니다. DFS branch가 다르면 한 branch가 finish된 뒤 다음 branch가 시작되므로 interval이 겹치지 않습니다. 겹치지 않는 interval을 보고 '같은 ancestor chain이 아니다'라고 말할 수 있습니다.

Edge classification도 stack으로 보면 쉽습니다. Edge (u,v)를 검사하는 순간 v가 WHITE면 아직 stack에 오른 적이 없으므로 그 edge로 새 tree branch를 만듭니다. v가 GRAY면 stack 어딘가에 아직 finish되지 않은 ancestor가 있다는 뜻입니다. u에서 그 ancestor로 돌아가는 directed edge는 cycle을 만듭니다. v가 BLACK이면 이미 끝난 vertex입니다. 그 vertex가 u의 subtree 안쪽에 있으면 forward, 다른 branch에 있으면 cross입니다.

DFS proof에서 조심할 점은 neighbor order입니다. DFS result는 graph 자체만으로 완전히 정해지지 않습니다. Adjacent vertices를 어떤 순서로 보느냐에 따라 d/f times, predecessor tree, edge classification 일부가 달라질 수 있습니다. 문제에서 lexicographically largest/smallest neighbor first 같은 조건을 주면 그것이 곧 알고리즘의 일부입니다. 조건을 무시하고 '아무 DFS'를 하면 구조적 명제는 맞아도 표 정답은 틀릴 수 있습니다.

Topological Sort Deep Dive: finish time이 dependency를 뒤집어 세웁니다

Topological sort를 처음 배울 때 가장 흔한 오해는 'DFS 방문 순서(discovery order)가 답인가?'입니다. 보통 답은 finish order입니다. 왜냐하면 어떤 작업 u가 작업 v보다 먼저 끝나야 한다는 \(\text{edge} u\rightarrow v\)edge u→v가 있을 때, DFS는 v 쪽을 먼저 깊게 처리하고 나서 u를 finish할 수 있습니다. 그래서 u는 v보다 늦게 finish되고, decreasing finish time으로 보면 u가 앞에 옵니다. 즉 finish order를 뒤집어 읽는 느낌입니다.

예를 들어 과목 prerequisite graph를 생각해 봅시다. \(\text{edge} \text{Grundkurs} \rightarrow \text{Fortgeschrittene}\)edge Grundkurs → Fortgeschrittene가 있다면 Grundkurs가 먼저 나와야 합니다. DFS가 Grundkurs에서 Fortgeschrittene로 들어가면 Fortgeschrittene를 먼저 finish하고 Grundkurs를 나중에 finish합니다. Finish time decreasing order에서는 Grundkurs가 Fortgeschrittene 앞에 놓입니다. 이것이 list 앞에 insert하는 pseudocode와 같은 효과입니다.

Cycle이 있으면 왜 불가능한지도 말로 설명할 수 있어야 합니다. A before B, B before C, C before A를 동시에 만족하는 줄 세우기는 없습니다. DFS 관점에서는 cycle이 back edge로 나타납니다. GRAY vertex로 돌아가는 edge가 있다는 것은 아직 끝나지 않은 ancestor로 되돌아간다는 뜻이고, directed cycle이 존재한다는 신호입니다. DAG에서는 이런 back edge가 없으므로 finish time argument가 안전합니다.

Topological order는 여러 개일 수 있습니다. A와 B 사이 dependency가 없으면 A before B도, B before A도 가능합니다. DFS neighbor order에 따라 서로 다른 valid order가 나올 수 있습니다. 시험에서 'the topological sort'라고 해도 실제로는 'a topological order'를 요구하는 경우가 많습니다. 따라서 답을 검산할 때는 내 순서가 sample solution과 다르더라도 모든 edge (u,v)에 대해 u가 v보다 앞인지 확인하세요. 그 조건을 만족하면 valid입니다.

SCC Deep Dive: maximality를 빼면 답이 너무 작아집니다

SCC 문제에서 학생들이 자주 하는 실수는 cycle 하나를 찾고 거기서 멈추는 것입니다. 예를 들어 \(3\rightarrow 4\rightarrow 5\rightarrow 3 \text{cycle}\)3→4→5→3 cycle이 있으면 {3,4,5}는 mutual reachable입니다. 그런데 \(5\rightarrow 6\)5→6과 \(6\rightarrow 3\)6→3이 추가되어 있다면 6도 3,4,5와 서로 reachable합니다. 그러면 SCC는 {3,4,5}가 아니라 {3,4,5,6}입니다. Maximality를 확인하지 않으면 이런 확장을 놓칩니다.

SCC를 찾을 때는 두 방향을 모두 확인합니다. u에서 v로 가는 path가 있는지만 보면 reachability set입니다. SCC는 v에서 u로 돌아오는 path도 있어야 합니다. 그래서 directed graph에서 한 방향 chain은 SCC를 만들지 않습니다. \(1\rightarrow 2\rightarrow 3\)1→2→3은 1에서 3으로 갈 수 있지만 3에서 1로 갈 수 없습니다. 각 vertex는 자기 자신으로 empty path가 있으므로 최소한 singleton SCC가 됩니다.

Component graph 관점은 복잡한 graph를 단순하게 만듭니다. 각 SCC를 하나의 blob으로 압축합니다. Blob 내부는 왕복 가능하므로 자세한 vertex를 잠시 잊어도 됩니다. Blob 사이에 edge가 있으면 condensation graph에 directed edge를 둡니다. 이 graph에 cycle이 생기면 cycle 위의 모든 blob이 서로 reachable해집니다. 그러면 사실 blob들이 서로 다른 SCC일 수 없으므로 contradiction입니다. 따라서 condensation graph는 DAG입니다.

이 성질은 exam trap에도 직접 연결됩니다. '서로 다른 SCC 사이에 양방향 edge가 있을 수 있다'는 문장은 false입니다. 양방향 edge는 즉시 두 SCC를 합칩니다. 'SCC는 disjoint하다'는 true입니다. 두 SCC가 vertex 하나라도 공유하면, 그 shared vertex를 통해 두 집합의 모든 vertex가 서로 reachable해져 하나의 SCC가 됩니다. 이런 논리는 source note의 SCC disjointness/one-way transition 내용과 맞닿아 있습니다.

Kosaraju Deep Dive: 두 번째 DFS가 왜 \(G^{T}\)Gᵀ에서 시작하는가

Kosaraju의 절차는 외우기 쉽지만 이유를 놓치기 쉽습니다. 첫 DFS는 SCC를 직접 출력하지 않습니다. 첫 DFS의 역할은 finish time order를 만드는 것입니다. 이 order는 condensation DAG에서 어떤 component를 먼저 떼어낼지 알려주는 신호입니다. 두 번째 DFS는 원래 graph가 아니라 \(\text{transpose} \text{graph} G^{T}\)transpose graph Gᵀ에서 실행합니다. \(G^{T}\)Gᵀ에서는 모든 edge direction이 뒤집힙니다.

SCC 내부를 생각해 봅시다. C 안의 u와 v가 서로 reachable이라면 G에는 u leadsto v path와 v leadsto u path가 둘 다 있습니다. 모든 edge를 뒤집으면 이 두 path의 방향도 각각 뒤집히지만, 여전히 u와 v 사이에는 양방향 reachability가 있습니다. 그래서 SCC 내부 membership은 변하지 않습니다. 반면 서로 다른 SCC 사이 edge 방향은 뒤집힙니다. 원래 \(C\rightarrow D\)C→D였으면 transpose에서는 \(D\rightarrow C\)D→C입니다.

두 번째 DFS의 order가 중요한 이유는 component 밖으로 새어 나가지 않기 위해서입니다. Finish time decreasing order로 아직 방문하지 않은 component를 고르면, \(G^{T}\)Gᵀ에서 그 component에서 출발하는 DFS가 정확히 그 SCC 내부를 sweep하도록 설계됩니다. 아무 순서로 시작하면 transpose의 edge를 타고 이전에 분리했어야 할 component까지 방문해 버릴 수 있습니다. 그래서 '\(G^{T}\)Gᵀ에서 DFS'와 'decreasing finish time order'는 둘 중 하나만 있어서는 부족합니다.

답안에서 Kosaraju를 쓸 때는 네 줄로 쓰면 안전합니다. \(1) \text{Run} \text{DFS} \text{on} G\quad\text{and}\quad \text{record} \text{finish} \text{회}. 2) \text{Construct} \text{transpose} \text{graph} G^{T}. 3) \text{Run} \text{DFS} \text{on} G^{T}\in \text{decreasing} \text{order} \text{of} \text{the} \text{finish} \text{회} \text{from} \text{step} 1. 4) \text{Each} \text{tree}\in \text{the} \text{second} \text{DFS} \text{forest} \text{is} \text{one} \text{SCC}. \text{Runtime}\)1) Run DFS on G and record finish times. 2) Construct transpose graph Gᵀ. 3) Run DFS on Gᵀ ∈ decreasing order of the finish times from step 1. 4) Each tree ∈ the second DFS forest is one SCC. Runtime은 adjacency list 기준 \(O(|V|+|E|)\)O(|V|+|E|)입니다. Transpose를 만드는 cost도 edge를 한 번씩 뒤집는 것이므로 같은 order입니다.

Comparisons: BFS, DFS, Topological Sort, SCC를 한 표로 말하기

BFS와 DFS는 둘 다 graph traversal입니다. 둘 다 color를 쓰고, adjacency list를 scan하며, standard runtime은 \(O(|V|+|E|)\)O(|V|+|E|)입니다. 하지만 목적과 산출물이 다릅니다. BFS는 source 기준 level과 unweighted shortest edge count를 얻습니다. Output으로 dist와 pred tree가 중요합니다. DFS는 graph의 깊은 구조를 얻습니다. Output으로 discovery/finish times, predecessor forest, edge classes가 중요합니다.

자료구조도 다릅니다. BFS는 queue(FIFO)입니다. 먼저 발견된 같은 level vertex들이 먼저 처리되어 level 순서가 유지됩니다. DFS는 recursion/stack(LIFO)입니다. 마지막으로 들어간 호출이 먼저 끝나며 nested interval이 만들어집니다. 이 차이를 말하지 못하면 'BFS vs DFS' 비교 질문에서 점수가 약해집니다.

Topological sort와 SCC는 DFS의 응용입니다. Topological sort는 DAG라는 precondition이 있고, finish time decreasing order를 사용해 dependency order를 만듭니다. SCC/Kosaraju는 general directed graph에서 가능하고, finish time order plus transpose graph를 사용해 mutual reachability components를 찾습니다. 둘 다 finish time을 쓰지만 목적이 다릅니다. Topological sort는 vertex ordering이고, SCC는 vertex partition입니다.

Shortest path와도 비교해야 합니다. BFS는 unweighted shortest path에 직접 연결됩니다. DFS는 shortest path가 아닙니다. Dijkstra/Bellman-Ford는 weighted shortest path로 다음 lecture 주제에 가깝습니다. Max-flow에서도 augmenting path search에 BFS/DFS가 등장할 수 있지만, 그때의 BFS/DFS는 residual graph에서 path를 찾는 subroutine입니다. 이처럼 같은 traversal 도구가 다른 알고리즘 안에 들어가도, BFS 자체의 invariant와 DFS 자체의 invariant는 변하지 않습니다.

구두시험 답안법: 정의, 상태, 불변식, 실행 시간, 함정

구두시험에서 긴 설명을 요구받으면 순서를 정해 두는 것이 중요합니다. 첫 문장은 definition입니다. 'BFS(Breitensuche)는 source s에서 queue를 사용해 graph를 level by level 방문하는 traversal입니다.' 둘째 문장은 state입니다. 'It maintains color, dist, pred, and queue Q.' 셋째 문장은 invariant입니다. 'Queue order ensures that when a vertex is first discovered, dist is the shortest edge count in an unweighted graph.' 넷째 문장은 runtime입니다. 'With adjacency lists, \(O(|V|+|E|)\)O(|V|+|E|).' 다섯째 문장은 trap입니다. 'It is not a weighted shortest-path algorithm.' 이렇게 말하면 60초 안에 핵심이 다 들어갑니다.

DFS도 같은 template을 씁니다. Definition: recursion/stack으로 깊게 들어가는 traversal. State: color, pred, discovery time d, finish time f. Invariant: interval containment characterizes ancestor relation. Runtime: adjacency list 기준 \(O(|V|+|E|)\)O(|V|+|E|). Trap: DFS tree paths are not necessarily shortest paths; directed and undirected edge classes differ.

Topological sort는 precondition부터 말하세요. 'For a DAG, topological sorting orders vertices so every edge (u,v) has u before v.' State/algorithm은 DFS finish times입니다. Invariant/proof는 \(\text{DAG} \text{has} \text{no} \text{back} \text{edge}, \text{hence} f[u] > f[v] \text{for} \text{every} \text{edge}. \text{Trap}\)DAG has no back edge, hence f[u] > f[v] for every edge. Trap은 cycle이 있으면 불가능하고, order가 unique할 필요는 없다는 것입니다.

SCC/Kosaraju는 definition에서 mutual reachability and maximality를 반드시 말하세요. Algorithm은 four steps로 말합니다. Proof intuition은 transpose preserves SCC membership and condensation graph is a DAG입니다. Runtime은 \(O(|V|+|E|)\)O(|V|+|E|). Trap은 weak connectivity와 혼동하지 말 것, second DFS order를 아무렇게나 하지 말 것, transpose가 SCC membership을 바꾼다고 말하지 말 것입니다.

Pseudocode Reading Protocol: 한 줄씩 무엇이 변하는지 표시합니다

BFS와 DFS pseudocode를 읽을 때는 syntax보다 state change를 표시해야 합니다. BFS 초기화 loop에서는 모든 vertex를 WHITE로 만들고 dist를 infinity, pred를 NIL로 둡니다. 이 줄은 단순 준비가 아니라 disconnected vertex까지 포함해 모든 vertex의 상태를 정의하는 줄입니다. 그 다음 source s만 GRAY, dist 0, pred NIL로 바꾸고 queue에 넣습니다. 이 순간 BFS tree의 root가 정해집니다. While Q not empty는 frontier가 남아 있다는 뜻입니다. Dequeue u는 지금 처리할 level의 vertex 하나를 꺼내는 것입니다. For each v in adj[u]는 실제 outgoing edges를 scan하는 줄입니다. \(\text{If} \text{color}[v]=\text{WHITE}\)If color[v]==WHITE조건은 first discovery만 받아들이겠다는 안전장치입니다.

BFS pseudocode에서 가장 시험 친화적인 줄은 \(\text{dist}[v]=\text{dist}[u]+1\)dist[v]=dist[u]+1입니다. 이 한 줄이 BFS가 level을 만든다는 증거입니다. \(\text{pred}[v]=u\)pred[v]=u는 shortest path tree를 복원하는 데 쓰입니다. Enqueue(v)는 v를 나중에 처리할 frontier로 넣습니다. 마지막 \(\text{color}[u]=\text{BLACK}\)color[u]=BLACK은 u의 adjacency scan이 끝났다는 표시입니다. 학생 답안에서 BLACK 처리를 생략해도 dist table은 맞을 수 있지만, color-state 문제나 pseudocode 설명에서는 빠뜨리면 안 됩니다.

DFS pseudocode는 DFS(G)와 DFS-VISIT(u)를 구분해야 합니다. DFS(G)는 모든 vertex를 초기화하고, 아직 WHITE인 vertex를 만나면 새 DFS tree root로 DFS-VISIT을 호출합니다. 그래서 graph가 disconnected이거나 directed graph에서 source 하나로 모든 vertex에 닿지 않아도 전체 DFS forest가 만들어집니다. DFS-VISIT(u)는 u를 GRAY로 만들고 discovery time을 찍은 뒤, WHITE neighbor마다 recursive call을 합니다. 모든 neighbor가 끝나면 u를 BLACK으로 만들고 finish time을 찍습니다.

Pseudocode를 손으로 따라갈 때는 줄 번호 옆에 'state mutation'을 써 보세요. color changes, time increments, pred assignments, queue/stack changes만 추적하면 됩니다. 복잡한 graph 그림을 한 번에 이해하려 하지 말고, 현재 줄이 어느 변수 하나를 바꾸는지 확인하면 실수가 줄어듭니다.

Hand Simulation Protocol: 시험장에서 표를 안정적으로 채우는 순서

BFS hand simulation은 네 단계 checklist로 고정하세요. 1) Vertex order와 neighbor order를 문제에서 확인합니다. 2) 초기 table을 씁니다: source만 dist 0, pred NIL, queue [s], 나머지는 infinity/NIL/WHITE. 3) 각 iteration마다 dequeue u를 먼저 적고, adj[u]를 순서대로 보면서 WHITE인 vertex만 새로 발견합니다. 4) iteration 끝의 queue를 반드시 적습니다. 이때 이미 GRAY 또는 BLACK인 vertex는 skip합니다. Skip했다는 사실을 마음속으로만 처리하지 말고, 복잡한 문제에서는 작은 표시를 해 두면 pred를 잘못 바꾸는 일을 막을 수 있습니다.

DFS hand simulation은 time counter를 눈에 보이게 관리해야 합니다. 시작 \(\text{time}=0\)time=0으로 두고, discover할 때마다 time++ 후 d를 찍습니다. finish할 때마다 time++ 후 f를 찍습니다. Recursive call이 들어가면 현재 vertex는 아직 finish되지 않았다는 점을 표시하세요. 종이에 stack column을 만들거나, 현재 path를 작게 적어 두면 GRAY edge와 BLACK edge를 구분하기 쉽습니다. DFS에서 가장 흔한 실수는 어떤 vertex가 아직 GRAY인지 이미 BLACK인지 헷갈리는 것입니다. Edge classification은 이 차이에 달려 있습니다.

Topological sort hand simulation에서는 DFS table을 먼저 완성하고, finish time decreasing order로 정렬합니다. List-front insertion 방식으로 풀면 finish되는 vertex를 answer list 앞에 붙입니다. 둘은 같은 결과입니다. 검산은 모든 edge (u,v)를 보며 u가 v보다 앞에 있는지 확인합니다. 하나라도 반대면 틀렸거나 graph에 cycle이 있는 것입니다. Sample answer와 순서가 다를 때도 edge condition으로 검산하세요.

SCC/Kosaraju hand simulation은 두 장의 graph를 분리해 그리는 것이 좋습니다. 첫 장에는 G와 first DFS finish times를 적습니다. 둘째 장에는 \(G^{T}\)Gᵀ를 그리고, first finish time decreasing order를 시작 순서로 표시합니다. Second DFS에서 생기는 tree마다 component label C1, C2, ...를 붙입니다. G와 \(G^{T}\)Gᵀ를 한 그림에 섞으면 방향을 헷갈립니다. 특히 transpose 후에도 SCC 내부 vertex membership은 같지만, algorithm이 실제로 찾는 순서는 달라질 수 있다는 점을 기억하세요.

서술형 답안에 재사용하는 증명 틀

BFS 최단 경로 증명은 층(level)에 대한 귀납으로 씁니다. 처음에는 \(\text{dist}[s]=0\)dist[s]=0이 맞습니다. 올바른 dist[u]를 가진 u를 큐에서 꺼낼 때 아직 발견하지 않은 이웃 v에는 \(\text{dist}[v]=\text{dist}[u]+1\)dist[v]=dist[u]+1을 기록합니다. 큐가 선입선출(FIFO)이므로 거리가 작은 모든 정점이 더 큰 정점보다 먼저 처리됩니다. v로 가는 더 짧은 경로가 있었다면 그 경로에서 v 바로 앞의 정점이 더 먼저 처리되어 v를 이미 발견했어야 합니다. 모순이므로 첫 발견 시의 거리가 최소 간선 수입니다. 핵심어는 FIFO, 첫 발견(first discovery), 더 짧은 경로를 가정한 모순입니다.

DFS 시간 구간 증명은 재귀 호출을 이용합니다. DFS-VISIT(u)가 실행되는 동안 u는 아래의 모든 재귀 호출이 끝날 때까지 회색(GRAY)입니다. 이 호출 안에서 v를 발견했다면 v는 u보다 늦게 발견되고 u보다 먼저 종료되므로 \(u.d < v.d < v.f < u.f\)u.d < v.d < v.f < u.f입니다. 서로 다른 재귀 가지는 차례로 처리되므로 그 시간 구간은 겹치지 않습니다. 이 증명은 조상 관계, 간선 분류, 위상 정렬 증명의 기반입니다.

위상 정렬 증명은 DAG와 종료 시각을 연결합니다. DAG의 DFS에는 역방향 간선(back edge)이 없습니다. 모든 간선 (u,v)에 대해 v는 u의 조상이 될 수 없습니다. v가 u에서 또는 u의 부분 트리 안에서 발견되면 v가 u보다 먼저 종료되고, 이미 종료된 v라면 역시 종료 시각이 더 작습니다. 따라서 모든 간선에 대해 \(f[u] > f[v]\)f[u] > f[v]이며 종료 시각 내림차순은 u를 v보다 앞에 놓는 유효한 위상 순서입니다.

SCC와 Kosaraju의 증명 직관은 다음과 같습니다. 모든 경로를 뒤집어도 상호 도달 가능성은 상호 도달 가능성으로 남으므로 전치 그래프는 SCC 구성 정점을 보존합니다. SCC 축약 그래프는 DAG입니다. 첫 번째 DFS의 종료 순서는 전치 뒤 두 번째 DFS가 아직 출력하지 않은 SCC를 정확히 하나씩 방문할 수 있는 순서를 제공합니다. 따라서 두 번째 탐색의 각 DFS 트리가 하나의 SCC입니다.

Counterexample Bank: 틀린 문장을 즉시 반박하는 작은 그래프들

MC나 oral exam에서 false statement를 반박하려면 작은 counterexample이 필요합니다. 'BFS solves weighted shortest path'를 반박하려면 세 vertex s,a,t를 두세요. \(\text{Edge} s\rightarrow t\)Edge s→t의 weight는 \(100, s\rightarrow a\)100, s→a와 \(a\rightarrow t\)a→t의 weight는 각각 1입니다. BFS는 edge count 1인 \(s\rightarrow t\)s→t를 먼저 shortest로 볼 수 있지만, minimum weight path는 \(s\rightarrow a\rightarrow t \text{cost} 2\)s→a→t cost 2입니다. 그래서 BFS의 shortest는 unweighted edge count라는 점이 드러납니다.

'DFS tree path is shortest'를 반박하려면 \(s\rightarrow a\rightarrow b\rightarrow t\)s→a→b→t와 \(s\rightarrow t\)s→t를 동시에 둡니다. Neighbor order가 a first이면 DFS tree는 s-a-b-t path를 만들 수 있습니다. 하지만 shortest edge count path는 \(s\rightarrow t\)s→t입니다. 이 예시는 DFS가 structural traversal이지 shortest path algorithm이 아니라는 점을 보여 줍니다.

'Topological order exists for every directed graph'를 반박하려면 \(\text{two}-\text{cycle} u\rightarrow v\quad\text{and}\quad v\rightarrow u\)two-cycle u→v and v→u만 있으면 됩니다. Topological order는 u before v와 v before u를 동시에 요구하게 됩니다. 불가능합니다. 'Topological order is unique'를 반박하려면 edge가 없는 두 vertex a,b를 두면 됩니다. [a,b]와 [b,a]가 모두 valid입니다. Dependency가 없으면 여러 순서가 가능합니다.

'SCC is connected component ignoring directions'를 반박하려면 \(1\rightarrow 2\rightarrow 3 \text{chain}\)1→2→3 chain을 쓰세요. 방향을 무시하면 연결되어 보이지만 strong connectivity는 없습니다. SCC는 singleton 세 개입니다. 'Transpose changes SCC membership'을 반박하려면 \(1<\rightarrow 2 \text{cycle}\)1<→2 cycle을 쓰면 됩니다. Edge를 뒤집어도 1과 2는 여전히 서로 reachable입니다. 조금 더 큰 예시로 {3,4,5} cycle도 transpose 후 같은 component로 남습니다.

'Directed and undirected DFS edge classes are the same'은 graph type을 바꿔 반박합니다. Directed graph에서는 이미 BLACK인 다른 branch로 가는 cross edge가 가능합니다. Undirected DFS에서는 강의 기준 tree/back만 말합니다. Statement가 graph type을 생략하면 조심해야 합니다.

Final Drill: 한 장 요약으로 다시 압축하기

마지막으로 전체 장을 한 장으로 압축해 봅시다. Graph basics: \(G=(V,E), \text{directed} \text{edge} (u,v), \text{path}, \text{reachable}, \text{adjacency} \text{matrix}/\text{list}. \text{Matrix}\)G=(V,E), directed edge (u,v), path, reachable, adjacency matrix/list. Matrix는 \(\Theta(|V|^2)\)Θ(|V|²), list는 \(\Theta(|V|+|E|)\)Θ(|V|+|E|). Traversal runtime \(O(|V|+|E|)\)O(|V|+|E|)를 말할 때는 adjacency list 기준이라고 붙입니다.

BFS: queue FIFO, color WHITE/GRAY/BLACK, dist, pred. Initialization은 source만 dist 0, queue [s]. WHITE neighbor v를 처음 발견하면 \(\text{dist}[v]=\text{dist}[u]+1, \text{pred}[v]=u. \text{Invariant}\)dist[v]=dist[u]+1, pred[v]=u. Invariant는 queue가 level order를 보존한다는 것입니다. Output은 unweighted shortest edge count와 predecessor tree입니다. Trap은 weighted shortest path가 아니라는 점, 이미 discovered vertex의 pred를 함부로 바꾸지 않는다는 점입니다.

DFS: recursion/stack, color, pred, discovery time d, finish time f. u ancestor of v iff u.\(d < v.d\)d < v.d < v.\(f < u.f.\)f < u.f. Directed edge classes: WHITE tree, GRAY back, BLACK descendant forward, BLACK other cross. Undirected DFS는 강의 기준 tree/back만. Trap은 DFS tree path가 shortest path가 아니라는 점, neighbor order가 결과를 바꾼다는 점입니다.

Topological sort: DAG only. 모든 edge (u,v)에 대해 u before v. DFS finish time decreasing order가 valid order입니다. Cycle/back edge가 있으면 불가능합니다. Order는 unique하지 않을 수 있습니다.

SCC/Kosaraju: SCC는 maximal mutual reachability set입니다. Weak connectivity가 아닙니다. Condensation graph는 DAG입니다. \(\text{Transpose} \text{graph} G^{T}\)Transpose graph Gᵀ는 SCC membership을 보존합니다. Kosaraju steps: \(\text{DFS}(G), \text{build} G^{T}, \text{DFS}(G^{T})\in \text{decreasing} \text{finish} \text{time}, \text{each} \text{second}-\text{pass} \text{DFS} \text{tree} \text{is} \text{one} \text{SCC}. \text{Runtime}\)DFS(G), build Gᵀ, DFS(Gᵀ) ∈ decreasing finish time, each second-pass DFS tree is one SCC. Runtime은 \(O(|V|+|E|)\)O(|V|+|E|) with adjacency lists입니다. 이 다섯 단락을 막힘없이 말하면 BFS/DFS/SCC 첫 강의 목표는 달성한 것입니다.

Integrated Practice Lecture: 한 그래프를 네 가지 렌즈로 보기

이제 같은 directed graph를 BFS, DFS, topological sort, SCC 네 렌즈로 보는 연습을 해 봅시다. Vertex가 {a,b,c,d,e,f}이고 edge가 \(a\rightarrow b, a\rightarrow c, b\rightarrow d, c\rightarrow d, d\rightarrow e, e\rightarrow f\)a→b, a→c, b→d, c→d, d→e, e→f라고 합시다. 이 graph는 방향이 모두 왼쪽에서 오른쪽으로 흐르는 DAG입니다. BFS를 a에서 시작하면 level 0은 a, level 1은 b,c, level 2는 d, level 3은 e, level 4는 f입니다. 여기서 BFS dist는 a에서 각 vertex까지 필요한 최소 edge 수입니다. pred는 neighbor order에 따라 b 또는 c 중 누가 d를 먼저 발견했는지에 따라 달라질 수 있지만, \(\text{dist}(d)=2\)dist(d)=2라는 사실은 변하지 않습니다.

같은 graph에서 DFS를 하면 결과는 neighbor order에 따라 달라집니다. a에서 b를 먼저 보면 a.d가 먼저 찍히고 b, d, e, f로 깊게 들어갈 수 있습니다. f가 finish되고 e, d, b가 차례로 finish된 뒤 a로 돌아와 c를 볼 수 있습니다. 이때 c에서 d로 가는 edge는 d가 이미 BLACK일 수 있으므로 cross 또는 forward 성격을 따져야 합니다. 표를 채울 때는 '내가 지금 어느 vertex call 안에 있는가'를 계속 추적해야 합니다.

Topological sort는 이 graph에서 가능합니다. 왜냐하면 directed cycle이 없기 때문입니다. 가능한 order는 a,b,c,d,e,f일 수도 있고, a,c,b,d,e,f일 수도 있습니다. b와 c 사이에는 직접 dependency가 없으므로 둘의 상대 순서는 여러 가지가 가능합니다. 검산은 모든 edge를 보는 것입니다. a는 b,c보다 앞인가? b와 c는 d보다 앞인가? d는 e보다 앞인가? e는 f보다 앞인가? 모두 맞으면 valid입니다.

SCC lens로 보면 이 graph의 모든 SCC는 singleton입니다. 왜냐하면 edge가 앞으로만 흐르고 되돌아오는 path가 없기 때문입니다. Condensation graph는 원래 graph와 거의 같습니다. 이제 \(\text{edge} f\rightarrow d\)edge f→d를 추가하면 d,e,f가 \(\text{cycle} d\rightarrow e\rightarrow f\rightarrow d\)cycle d→e→f→d를 이루어 하나의 SCC가 됩니다. 그래도 a,b,c는 그 SCC로 들어갈 수만 있고 돌아오지는 못하므로 같은 SCC가 아닙니다. 이 한 예시만으로도 BFS level, DFS intervals, topological order, SCC grouping이 서로 다른 질문에 답한다는 것을 볼 수 있습니다.

Grading Rubric: 좋은 답안과 아쉬운 답안을 구분하는 기준

좋은 BFS 답안은 자료구조와 보장 범위를 같이 말합니다. 'BFS는 queue를 쓴다'에서 멈추면 반쪽 답입니다. 'FIFO queue가 level order를 보존하므로 unweighted graph에서 dist가 shortest edge count가 된다'까지 가야 합니다. 표 문제에서는 queue snapshot과 dist/pred update가 있어야 합니다. Runtime은 adjacency list 기준 \(O(|V|+|E|)\)O(|V|+|E|)라고 쓰면 가장 안전합니다. Weighted shortest path가 아니라는 caveat를 붙이면 MC 함정에도 강합니다.

좋은 DFS 답안은 recursion stack과 timestamps를 연결합니다. 단순히 'DFS는 깊게 간다'는 설명은 너무 약합니다. 'Discover할 때 d를 찍고, 모든 outgoing edge 처리가 끝나면 f를 찍는다. GRAY vertex는 recursion stack 위에 있다. \(u.d < v.d < v.f < u.f\)u.d < v.d < v.f < u.f이면 u가 v의 ancestor다'라고 말해야 합니다. Edge classification 문제에서는 graph가 directed인지 undirected인지 먼저 확인합니다. Directed이면 tree/back/forward/cross를 말하고, undirected이면 강의 기준 tree/back만 말합니다.

좋은 topological sort 답안은 definition과 precondition을 분리합니다. Definition은 모든 edge (u,v)에 대해 u before v입니다. Precondition은 DAG입니다. Algorithm은 DFS finish time decreasing order입니다. Proof는 no back edge와 \(f[u] > f[v]\)f[u] > f[v]입니다. 아쉬운 답안은 'DFS order로 정렬한다'처럼 discovery order와 finish order를 섞거나, cycle이 있어도 되는 것처럼 말합니다. 또 topological order가 항상 unique하다고 쓰면 감점 위험이 큽니다.

좋은 SCC 답안은 strong connectivity와 maximality를 모두 말합니다. '서로 연결된 정점들'은 너무 모호합니다. Directed graph에서 'for all u,v in C, u reaches v and v reaches u, and C is maximal'이라고 해야 합니다. Kosaraju 답안은 네 단계가 순서대로 있어야 합니다. \(\text{DFS}(G), G^{T}\)DFS(G), Gᵀ생성, first finish time decreasing order로 \(\text{DFS}(G^{T}), \text{second} \text{DFS} \text{tree}\)DFS(Gᵀ), second DFS tree마다 SCC 출력입니다. \(G^{T}\)Gᵀ를 빼거나 order를 빼면 핵심이 빠진 답안입니다.

채점자가 보고 싶은 것은 암기한 문장이 아니라 조건을 지키는 습관입니다. Graph type, representation, source vertex, neighbor order, weighted/unweighted, DAG 여부, transpose 여부. 이 여섯 가지를 문제에서 먼저 표시하면 대부분의 실수를 예방할 수 있습니다.

Last Active Recall Round: 답을 보기 전에 말로 재구성하기

지금부터는 책을 덮고 말로 재구성하는 단계입니다. 첫 번째 질문: directed graph와 undirected graph의 차이를 \(G=(V,E) \text{notation}\)G=(V,E) notation으로 설명해 보세요. 답에는 E subseteq V x V, ordered pair, symmetry condition이 들어가야 합니다. 두 번째 질문: adjacency matrix와 adjacency list 중 BFS/DFS \(O(|V|+|E|)\)O(|V|+|E|) 분석에 자연스러운 representation은 무엇인가요? 답은 adjacency list이고, 이유는 모든 실제 edge list를 한 번씩 scan하기 때문입니다.

세 번째 질문: BFS에서 pred[v]는 언제 정해지고 언제 바뀌지 않나요? 답은 WHITE vertex를 처음 발견할 때 정해지고, 이미 GRAY 또는 BLACK이면 바꾸지 않는다는 것입니다. 네 번째 질문: BFS dist가 weighted shortest path가 아닌 이유를 counterexample으로 말해 보세요. Edge 하나 cost 100, edge 두 개 cost 2 예시를 말하면 됩니다.

다섯 번째 질문: DFS에서 GRAY vertex로 가는 directed edge는 무엇이며 무엇을 의미하나요? 답은 back edge이고 directed cycle의 신호입니다. 여섯 번째 질문: \(u.d < v.d < v.f < u.f\)u.d < v.d < v.f < u.f를 보면 무엇을 결론낼 수 있나요? 답은 u가 v의 DFS ancestor라는 것입니다. 일곱 번째 질문: undirected DFS와 directed DFS edge classes의 차이를 말하세요. 답은 directed에는 tree/back/forward/cross가 있고, undirected에는 강의 기준 tree/back만 나온다는 것입니다.

여덟 번째 질문: topological sorting의 정의와 불가능한 경우를 말하세요. 모든 edge (u,v)에 대해 u before v이고, directed cycle이 있으면 불가능합니다. 아홉 번째 질문: decreasing finish time order가 왜 topological order가 되나요? DAG에는 back edge가 없고 모든 edge에서 \(f[u] > f[v]\)f[u] > f[v]가 되기 때문입니다.

열 번째 질문: SCC에서 maximality가 왜 필요한가요? 작은 mutual reachable subset에서 멈추지 않고 더 붙일 수 있는 vertex까지 포함해야 component가 되기 때문입니다. 열한 번째 질문: \(G^{T}\)Gᵀ가 SCC membership을 보존하는 이유는 무엇인가요? 양방향 path가 모두 있었으면 뒤집어도 양방향 path가 모두 남기 때문입니다. 열두 번째 질문: Kosaraju 네 단계를 순서대로 말하세요. 이 열두 질문을 막힘없이 말하면, 이 페이지는 읽은 것이 아니라 실제 시험용 지식으로 바뀐 것입니다.