Lecture 10: Depth-First Search (깊이 우선 탐색)

Lecture 10: Depth-First Search 

0. Previously 복습하기 

• Graph definitions (directed/undirected, simple, neighbors, degree)
그래프 정의 (방향있는 그래프 / 무방향 그래프, 단순 그래프, 이웃 정점, 차수)
→ 그래프는 정점(vertex)들과 간선(edge)들로 구성되며,

→ 간선에 방향이 있으면 방향 그래프, 없으면 무방향 그래프라 합니다.
→ 단순 그래프(simple): 자기 자신으로 가는 간선이 없고, 간선이 중복되지 않는 그래프
→ 이웃(neighbors): 각 정점에 연결된 다른 정점들

→ 차수(degree): 이들 이웃과 연결된 간선의 수

 

• Graph representations (Set mapping vertices to adjacency lists)
그래프 표현 방식 (정점을 인접 리스트에 매핑하는 집합 구조)
→ 그래프를 효율적으로 다루기 위해 각 정점을 키로 하고,

이웃 정점 리스트를 값으로 가지는 인접 리스트(adjacency list) 구조를 사용합니다.
→ 일반적으로 배열, 해시 테이블 등을 써서 정점에 빠르게 접근하고, 연결된 정점 목록은 리스트나 배열로 저장합니다.

 

• Paths and simple paths, path length, distance, shortest path
경로, 단순 경로, 경로 길이, 거리, 최단 경로
→ 경로(path)는 정점을 순서대로 따라간 연결입니다.
→ 단순 경로(simple path)는 중복되는 정점 없이 한 번씩만 방문하는 경로입니다.
→ 경로 길이(path length)는 간선의 수 또는 가중치의 합입니다.
→ 거리(distance)는 두 정점 사이의 가장 짧은 경로의 길이를 의미하며, 최단 경로(shortest path) 문제와 관련됩니다.

 

• Graph Path Problems
그래프에서 경로와 관련된 알고리즘 문제들입니다:

 

– Single Pair Reachability(G, s, t)
: 그래프 G에서 정점 s에서 정점 t까지 도달 가능한가?

 

– Single Source Reachability(G, s)
: 그래프 G에서 정점 s에서 도달 가능한 모든 정점은 무엇인가?

 

– Single Pair Shortest Path(G, s, t)
: 정점 s에서 t까지의 최단 경로는 무엇인가?

 

– Single Source Shortest Paths(G, s) (SSSP)
: 정점 s에서 모든 정점까지의 최단 경로를 구하는 문제입니다.

(SSSP): Single-Source Shortest Path. 하나의 시작 정점(source)에서 그래프 내 모든 다른 정점까지의 최단 경로를 찾는 문제

 

 

• Breadth-First Search (BFS)
– Single Source Shortest Paths 단일 출발점 최단 경로 문제를 해결하는 알고리즘
→ BFS는 시작 정점에서부터 넓이 우선 방식으로 이웃들을 탐색하면서, 가장 가까운 순서대로 정점들을 방문합니다.
→ 간선의 가중치가 모두 1일 때는 최단 경로를 효율적으로 찾을 수 있습니다.

예를 들어, 지도의 한 도시에서 다른 모든 도시에 가는 가장 짧은 길을 계산

 

– with appropriate data structures, runs in O(|V| + |E|) time (linear in input size)
→ 적절한 자료구조(예: 큐, 인접 리스트)를 사용하면, BFS는 정점 수 + 간선 수 만큼의 시간에 동작합니다.
→ 입력 크기에 비례하는 선형 시간 알고리즘입니다.

 

 

1. Examples 

 

 

2 Depth-First Search (DFS)

• Searches a graph from a vertex s, similar to BFS
정점 s에서 그래프를 탐색하는데, 방식은 BFS와 유사하다.
→ 시작 정점 s에서 출발하여 그래프 전체를 탐색하는 알고리즘이며, 너비 우선 탐색(BFS)처럼 모든 정점에 도달하는 방법이다.
→ 하지만 탐색 순서는 BFS와 다릅니다.

 

• Solves Single Source Reachability, not SSSP. Useful for solving other problems (later!)
SSSP(단일 출발점 최단 경로)가 아니라, 단일 출발점 도달 가능성(Single Source Reachability) 문제를 해결한다.
→ 즉, s에서 어떤 정점에 도달 가능한지만 알려줄 뿐, 그 경로가 최단인지는 보장하지 않습니다.
→ 그래도 향후 다양한 문제(사이클 탐지, 위상 정렬 등)에 유용하게 쓰입니다.

 

• Return (not necessarily shortest) parent tree of parent pointers back to s
(최단은 아니지만) s로 거슬러 올라갈 수 있는 부모 트리(parent tree)를 반환한다.
→ 방문한 모든 정점에 대해 "누가 너를 통해 왔는가?"라는 정보를 담고 있는 부모 포인터 구조입니다.
→ 이 트리를 통해 DFS가 어떤 순서로 탐색했는지 알 수 있습니다.

 

• Idea! Visit outgoing adjacencies recursively, but never revisit a vertex
아이디어: 나가는 간선들을 재귀적으로 방문하되, 이미 방문한 정점은 다시 방문하지 않는다.
→ 순환하지 않기 위해 방문 여부를 기록하며 재귀적으로 탐색합니다.

 

• i.e., follow any path until you get stuck, backtrack until finding an unexplored path to explore
아무 경로나 따라가다가 더 이상 갈 곳이 없으면 되돌아와서 새로운 경로를 다시 탐색하는 방식이다.
→ 이게 바로 깊이 우선 탐색(DFS)의 핵심 전략입니다.

 

• P(s) = None, then run visit(s), where
시작 정점 s의 부모는 없으므로 P(s) = None으로 설정하고, visit(s) 함수를 호출한다.

 

• visit(u) :
정점 u를 방문하는 재귀 함수 정의

 

– for every v ∈ Adj(u) that does not appear in P:
: u의 이웃 정점 v 중 아직 부모가 지정되지 않은 정점들에 대해

 

∗ set P(v) = u and recursively call visit(v)
: v의 부모를 u로 지정하고, visit(v)를 재귀적으로 호출한다.
→ 즉, u → v 경로를 따라 탐색을 이어간다.

 

– (DFS finishes visiting vertex u, for use later!)
: 정점 u에 대한 탐색이 완료되면 이후 다른 알고리즘(예: 위상 정렬 등)에 이 정보를 사용할 수 있다.

 

• Example: Run DFS on G1 and/or G2 from a
예시: 정점 a에서 시작하여 G1 또는 G2 그래프에 대해 DFS를 실행해본다.
→ DFS가 어떻게 부모 트리를 만들고, 정점들을 어떤 순서로 탐색하는지 직접 확인하는 예시를 아래에서 살펴보자

 

 

3. Correctness 

• Claim: DFS visits v and correctly sets P(v) for every vertex v reachable from s
정확성 주장: DFS는 시작 정점 s로부터 도달 가능한 모든 정점 v를 방문하고, v의 부모 P(v)를 정확하게 설정한다는 주장입니다.

 

• Proof: induct on k, for claim on only vertices within distance k from s
증명: s로부터 거리 k 이내에 있는 정점들에 대해서 귀납법(induction)을 사용하여 증명합니다.

 

– Base case (k = 0): P(s) is set correctly for s and s is visited
기초 단계 (k = 0): s는 자기 자신이므로 P(s)는 None 또는 잘 정의된 값으로 설정되며, DFS는 시작점 s를 방문합니다. 이로써 가장 가까운 거리(k=0)에 대한 올바름을 보여줍니다.

 

– Inductive step: Consider vertex v with δ(s, v) = k' + 1
귀납 단계: s로부터 거리 k'+1만큼 떨어진 정점 v를 고려합니다.

바로 이전 단계보다 한 단계 멀리 있는 정점입니다.

 

– Consider vertex u, the second to last vertex on some shortest path from s to v
정점 v까지의 어떤 최단 경로 상에서 v 바로 이전 정점인 u를 고려합니다.

이때 u는 s로부터 거리 k'에 위치한 정점입니다.

 

– By induction, since δ(s, u) = k', DFS visits u and sets P(u) correctly
귀납 가정에 따라, u는 s로부터 거리 k'에 있으므로 DFS가 u를 방문하고 P(u)를 정확하게 설정했음이 보장됩니다.

 

– While visiting u, DFS considers v ∈ Adj(u)
DFS가 u를 방문하는 동안, u의 인접 정점들 중 하나로서 v를 고려하게 됩니다.

DFS는 u → v 간선을 따라가 보려 합니다.

 

– Either v is in P, so has already been visited, or v will be visited while visiting u
이 시점에서 v는 두 가지 경우 중 하나입니다:
(1) 이미 P에 포함되어 있어 이전에 방문된 상태이거나,
(2) 아직 방문되지 않았다면 DFS는 u를 방문하면서 v도 방문하게 됩니다.

 

– In either case, v will be visited by DFS and will be added correctly to P
어느 경우든 v는 결국 DFS에 의해 방문되며, P(v)는 u로 정확하게 설정됩니다.

따라서 v도 올바르게 처리된다는 결론에 도달합니다.

 

 

4. Running Time

• Algorithm visits each vertex u at most once and spends O(1) time for each v ∈ Adj(u)
알고리즘은 각 정점 u를 최대 한 번만 방문하며, u의 인접 정점 v 하나하나에 대해 O(1) 시간만 사용합니다. 즉, u에서 나가는 간선 하나마다 일정한 시간만 소요됩니다.

• Work upper bounded by O(1) × deg(u) = O(|E|) u∈V
모든 정점 u에 대해 각자의 인접 정점들을 처리하는 데 드는 시간은 O(1) × deg(u)이고, 이들을 모든 정점에 대해 합치면 ∑deg(u) = |E|이므로, 전체 시간은 O(|E|)입니다.

• Unlike BFS, not returning a distance for each vertex, so DFS runs in O(|E|) time
BFS는 각 정점까지의 거리를 계산하지만, DFS는 거리를 따로 계산하지 않기 때문에 그 추가 연산이 없습니다. 따라서 DFS의 전체 실행 시간은 O(|V| + |E|), 간단히 O(|E|)로 표현됩니다 (|E| ≥ |V|인 연결 그래프 기준에서).

 

 

5. Full-BFS and Full-DFS

Full-BFS and Full-DFS
Full-BFS 및 Full-DFS는 그래프 전체를 탐색할 때 사용하는 방식입니다.

• Suppose want to explore entire graph, not just vertices reachable from one vertex
하나의 시작 정점에서 도달 가능한 정점들만이 아니라, 그래프 전체를 탐색하고자 하는 경우를 생각합니다.

• Idea! Repeat a graph search algorithm A on any unvisited vertex
아이디어: 그래프 탐색 알고리즘 A (예: DFS나 BFS)를 아직 방문되지 않은 정점에서 반복 실행합니다.

• Repeat the following until all vertices have been visited:
모든 정점이 방문될 때까지 아래의 과정을 반복합니다:

– Choose an arbitrary unvisited vertex s, use A to explore all vertices reachable from s
방문되지 않은 정점 s를 임의로 선택한 뒤, A (DFS 또는 BFS)를 사용하여 s에서 도달할 수 있는 모든 정점을 탐색합니다.

• We call this algorithm Full-A, specifically Full-BFS or Full-DFS if A is BFS or DFS
이 전체 탐색 알고리즘을 Full-A라고 부르며, A가 BFS이면 Full-BFS, A가 DFS이면 Full-DFS라고 합니다.

• Visits every vertex once, so both Full-BFS and Full-DFS run in O(|V | + |E|) time
모든 정점을 한 번씩 방문하므로, Full-BFS와 Full-DFS 모두 실행 시간은 **O(|V| + |E|)**입니다.

• Example: Run Full-DFS/Full-BFS on G1 and/or G2
예시로, 그래프 G1 또는 G2에 대해 Full-DFS나 Full-BFS를 실행할 수 있습니다.
(※ G1, G2는 강의나 책에서 나오는 예시 그래프를 의미합니다.)

 

 

6. Graph Connectivity

그래프 연결성에 대한 기본 개념과 이를 탐색 알고리즘으로 해결하는 방법을 설명합니다.

• An undirected graph is connected if there is a path connecting every pair of vertices
무방향 그래프에서 모든 정점 쌍 간에 경로가 존재하면, 그 그래프는 connected (연결됨) 상태입니다.

• In a directed graph, vertex u may be reachable from v, but v may not be reachable from u
방향 그래프에서는 u에서 v로는 갈 수 있어도, 반대로는 갈 수 없는 경우가 있습니다. 즉, 연결 개념이 더 복잡합니다.

• Connectivity is more complicated for directed graphs (we won’t discuss in this class)
방향 그래프의 연결성(예: Strongly Connected)은 복잡하므로, 여기서는 다루지 않습니다.

• Connectivity(G): is undirected graph G connected?
문제 정의: 주어진 무방향 그래프 G가 연결되어 있는지 확인하는 문제입니다.

• Connected Components(G): given undirected graph G = (V, E), return partition of V into subsets Vi ⊆ V (connected components) where each Vi is connected in G and there are no edges between vertices from different connected components
Connected Components (연결 요소) 문제: 무방향 그래프 G에서 정점 집합 V를 연결된 부분 집합 Vi로 나누되,

• 각 Vi는 내부적으로는 연결되어 있어야 하고,
• 서로 다른 Vi 사이에는 간선이 없어야 합니다.
  즉, 각 Vi는 하나의 연결된 덩어리입니다.

• Consider a graph algorithm A that solves Single Source Reachability
단일 출발점 도달성(Single Source Reachability)을 푸는 어떤 그래프 알고리즘 A (예: DFS나 BFS)를 생각해봅니다.

• Claim: A can be used to solve Connected Components
주장: 알고리즘 A를 이용해서 연결 요소들을 찾을 수 있습니다.

• Proof: Run Full-A. For each run of A, put visited vertices in a connected component
증명: Full-A (Full-DFS 또는 Full-BFS)를 실행합니다.

• 아직 방문되지 않은 정점에서 A를 실행하고,
• 그 탐색에서 방문된 모든 정점을 **하나의 연결 요소(Connected Component)**로 묶습니다.
  이 과정을 모든 정점이 방문될 때까지 반복하면, 전체 연결 요소들이 완성됩니다.

 

7. Topological Sort

위상 정렬은 방향 비순환 그래프(DAG)에 대해 가능한 정점의 정렬 방법을 다룹니다.

• A Directed Acyclic Graph (DAG) is a directed graph that contains no directed cycle.
DAG란 방향성이 있는 간선들로 구성되며, 어떤 정점으로부터 다시 그 정점으로 돌아오는 사이클이 없는 방향 그래프입니다.

• A Topological Order of a graph G = (V, E) is an ordering f on the vertices such that: every edge (u, v) ∈ E satisfies f(u) < f(v).
위상 정렬이란, 간선 (u, v)에 대해 항상 u가 v보다 먼저 나오는 정점의 순서입니다. 즉, 정렬된 순서에서 원인 u → 결과 v가 되도록 정렬하는 것입니다.

• Exercise: Prove that a directed graph admits a topological ordering if and only if it is a DAG.
연습문제: 어떤 방향 그래프가 위상 정렬이 가능하려면 DAG여야 하고, DAG이면 반드시 위상 정렬이 가능함을 증명해보세요.

• How to find a topological order?
어떻게 위상 정렬을 찾을 수 있을까요? (다음 줄부터 설명)

• A Finishing Order is the order in which a Full-DFS finishes visiting each vertex in G
Finishing Order(완료 순서)란, Full-DFS를 수행했을 때 각 정점의 탐색이 끝나는 순서를 의미합니다.

• Claim: If G = (V, E) is a DAG, the reverse of a finishing order is a topological order
주장: DAG G에 대해, Finishing Order를 거꾸로 뒤집은 순서는 유효한 위상 정렬입니다.

• Proof: Need to prove, for every edge (u, v) ∈ E that u is ordered before v, i.e., the visit to v finishes before visiting u. Two cases:
증명: 모든 간선 (u, v)에 대해, u가 v보다 앞에 나와야 함을 보여야 합니다.
→ 즉, DFS 기준으로 v가 먼저 종료되고 u가 나중에 종료되어야 합니다.
이것을 보이기 위해 두 가지 경우를 나눕니다:

– If u visited before v:
첫 번째 경우: u를 먼저 방문한 경우

∗ Before visit to u finishes, will visit v (via (u, v) or otherwise)
DFS가 u를 방문하면, 그 도중에 u → v를 따라 v도 방문하게 됩니다.

∗ Thus the visit to v finishes before visiting u
DFS는 자식 정점을 모두 방문 완료한 뒤에 부모 정점 방문을 종료하므로, v가 먼저 종료되고 그 후에 u가 종료됩니다.

– If v visited before u:
두 번째 경우: v를 먼저 방문한 경우

∗ u can’t be reached from v since graph is acyclic
DAG이므로, v에서 u로 가는 경로는 존재하지 않습니다. 즉, u는 v의 후손이 될 수 없습니다.

∗ Thus the visit to v finishes before visiting u
따라서 DFS는 v를 끝내고 나중에 u를 별도로 방문하게 되고, 결과적으로 v가 먼저 종료됩니다.

→ 이 두 경우 모두에서 v의 종료 시점이 u보다 앞서므로, Finishing Order를 뒤집으면 (u가 v보다 먼저 오게 되어) 위상 정렬 조건을 만족합니다.

 

 

8. Cycle Detection 

Cycle Detection
사이클 유무를 DFS를 통해 판단하고, 실제 사이클도 찾아낼 수 있는 방법을 설명합니다.

• Full-DFS will find a topological order if a graph G = (V, E) is acyclic
그래프 G가 사이클이 없다면 (즉, DAG라면), Full-DFS를 통해 유효한 위상 정렬을 얻을 수 있습니다.

• If reverse finishing order for Full-DFS is not a topological order, then G must contain a cycle
만약 Full-DFS의 종료 순서를 뒤집은 결과가 위상 정렬 조건을 만족하지 않는다면,
즉 어떤 간선 (u, v)에 대해 u가 v보다 뒤에 나왔다면, 이는 사이클이 존재함을 의미합니다.

• Check if G is acyclic: for each edge (u, v), check if v is before u in reverse finishing order
G가 DAG인지 확인하려면, 모든 간선 (u, v)에 대해 v가 u보다 먼저 나왔는지 (즉, f(u) < f(v))를 체크합니다.
→ 반대가 있다면 사이클이 있다는 뜻입니다.

• Can be done in O(|E|) time via a hash table or direct access array
이 검사는 정점 순서를 배열에 저장하거나 해시 테이블을 써서 각 정점의 위치를 빠르게 비교하면 되므로, O(|E|) 시간에 수행 가능합니다.

• To return such a cycle, maintain the set of ancestors along the path back to s in Full-DFS
실제 사이클을 찾아내기 위해선 DFS 수행 중 **현재 경로 상의 조상 노드들(ancestor)**을 추적해야 합니다.
이 정보로 되돌아가는 간선을 발견하면 즉시 사이클을 복원할 수 있습니다.

• Claim: If G contains a cycle, Full-DFS will traverse an edge from v to an ancestor of v.
주장: 만약 그래프에 사이클이 있다면, Full-DFS 수행 중에 어떤 정점 v에서 조상 정점으로 되돌아가는 간선을 타게 됩니다.

• Proof: Consider a cycle (v0, v1, . . . , vk, v0) in G
사이클 (v₀, v₁, ..., vₖ, v₀)을 고려해 봅시다.

– Without loss of generality, let v0 be the first vertex visited by Full-DFS on the cycle
일반성을 잃지 않고, 이 사이클 중 Full-DFS가 가장 먼저 방문하는 정점을 v₀라고 하겠습니다.

– For each vi, before visit to vi finishes, will visit vi+1 and finish
v₀에서 시작한 DFS는 vi를 방문한 후, vi+1로 이어지는 간선을 통해 다음 정점들을 차례로 방문하며 종료합니다.

– Will consider edge (vi, vi+1), and if vi+1 has not been visited, it will be visited now
각 단계에서 DFS는 (vi, vi+1) 간선을 따라가며 아직 방문하지 않은 정점이라면 방문하게 됩니다.

– Thus, before visit to v0 finishes, will visit vk (for the first time, by v0 assumption)
이 흐름에 따라, DFS는 v₀가 종료되기 전에 사이클의 끝 정점인 vₖ도 방문합니다.

– So, before visit to vk finishes, will consider (vk, v0), where v0 is an ancestor of vk
그리고 vₖ의 이웃 정점 중에는 사이클을 완성하는 간선 (vₖ, v₀)이 있으므로,
vₖ는 조상 정점인 v₀로 되돌아가는 간선을 따라가게 되며, 이로써 DFS 중 사이클을 발견합니다.