Lecture 9: Breadth-First Search (BFS) 너비 우선 탐색
Lecture 9: Breadth-First Search (BFS) 너비 우선 탐색
이 강의에서는 BFS라는 알고리즘을 알아보겠습니다
1. Graph Applications
• Why? Graphs are everywhere!
왜 그래프를 배우는가? 그래프는 어디에나 존재한다!
다양한 시스템이나 문제들이 그래프로 표현되는 경우가 많기 때문에 그래프를 배우는 것이 중요합니다.
• any network system has direct connection to graphs
모든 네트워크 시스템은 그래프와 직접적으로 연결되어 있다
• e.g., road networks, computer networks, social networks
예: 도로망, 컴퓨터 네트워크, 소셜 네트워크
각각 도로나 사람(vertex)과 그 사이의 연결(도로, 통신, 친구 관계 등)을 edge로 표현할 수 있습니다.
• the state space of any discrete system can be represented by a transition graph
모든 이산적인(discrete) 시스템의 상태 공간은 전이 그래프로 표현할 수 있다
예를 들어 시스템이 가질 수 있는 모든 상태와 상태 간 이동을 정점와 간선으로 나타내면 상태 공간 그래프가 됩니다.
* discrete system: 값이나 상태가 연속적인 것이 아니라, 셀 수 있는 개별적인(이산적인) 상태들로 구성된 시스템
예를 들어 체스는 한 번에 하나의 말이 움직이고, 말의 위치가 격자판 위의 정해진 칸 중 하나이기 때문에 이산 시스템입니다.
반대로 온도계처럼 0도에서 1도 사이에도 무한한 실수값을 가질 수 있는 시스템은 연속 시스템(continuous system)입니다.
* transition graph
어떤 시스템이 다양한 상태(state)를 가지며, 그 상태들 사이를 어떻게 이동(transition)할 수 있는지를 표현하는 그래프입니다.
그래서 이걸 분석하면 문제 해결이나 최적 경로 찾기 등에 매우 유용합니다.
• e.g., puzzle & games like Chess, Tetris, Rubik’s cube
예: 체스, 테트리스, 루빅스 큐브 같은 퍼즐이나 게임
게임의 각 상태(말의 배치, 블록의 위치 등)를 vertex로 보고, 한 수 한 수의 움직임을 edge로 보면 그래프 탐색 문제로 바꿀 수 있습니다.
* 루빅스 큐브: 큐브가 현재 어떤 색 배열인지가 "vertex", 한 면을 돌리는 동작이 "edge"
* 체스: 말이 있는 상태가 "vertex", 말을 한 칸 움직이는 게 "edge"
• e.g., application workflows, specifications
예: 애플리케이션의 작업 흐름, 시스템 명세
어떤 작업 순서나 조건들을 그래프로 표현해 자동화하거나 검증할 수 있습니다.
2. Graph Definitions
그래프의 구조와 종류
• Graph G = (V, E) is a set of vertices V and a set of pairs of vertices E ⊆ V × V.
V: 그래프의 정점(Vertex) 들의 집합
V x V: V의 데카르트 곱(Cartesian product). 가능한 모든 정점(Vertex)들의 쌍으로 만든 집합
E: 이 전체 V x V 집합에서 전체나 일부를 담은 집합
예를 들어 V= {A, B, C} 일 때
V x V = {(A, A), (A, B), (A, C), (B, A), (B, B), (B, C), (C, A), (C, B), (C, C)} 9개의 정점 쌍을 만들 수 있습니다.
그 중에서 일부만 담아서
E = {(A, B), (B, C)} 이렇게 표현할 수 있습니다
• Directed edges are ordered pairs, e.g., (u, v) for u, v ∈ V
방향이 있는 엣지는 순서가 있는 쌍이다.
예를 들어 (u, v)는 u에서 v로 가는 간선이다. 이는 u → v의 의미로, 한쪽 방향만 존재합니다.
방향 그래프에서 (u, v)와 (v, u)는 다르다.
괄호 안에 두 정점을 넣는다
* orders pairs: 순서가 중요
• Undirected edges are unordered pairs, e.g., {u, v} for u, v ∈ V i.e., (u, v) and (v, u)
방향이 없는 간선은 순서 없는 쌍으로 표현된다.
예를 들어 {u, v}. 즉, (u, v)와 (v, u)는 동일하다.
중괄호 안에 두 정점을 넣어 표현합니다.
무방향 그래프에서는 두 정점 사이의 연결에 방향이 없기 때문에 순서와 상관없습니다.
• In this class, we assume all graphs are simple:
이 수업에서는 모든 그래프를 단순 그래프로 가정한다.
단순 그래프(simple graph)는 중복된 간선이나 자기 자신과 연결된 간선이 없는 그래프입니다.
– edges are distinct, e.g., (u, v) only occurs once in E (though (v, u) may appear), and
모든 간선은 중복 없이 하나만 존재한다. 예: (u, v)가 E에 한 번만 나타난다. (단, (v, u)는 따로 존재할 수 있다.)
중복된 연결은 없으며, 방향이 있는 그래프에서는 u → v와 v → u를 별개의 간선으로 간주합니다.
– edges are pairs of distinct vertices, e.g., u ≠ v for all (u, v) ∈ E
모든 간선은 서로 다른 정점을 가진 쌍으로 이루어진다. 즉, (u, u) 같은 자기 자신으로의 간선은 없다.
자기 루프(self-loop)는 허용되지 않으며, 모든 간선은 두 서로 다른 정점 사이에서만 가능합니다.
단순 그래프에서는 간선의 수가 O(|V|²) 이하이다.
무방향 그래프의 경우 최대 |V|(|V| - 1)/2,
방향 그래프는 |V|(|V| - 1)이다.
* |E|: 간선 수
* |V|: 정점 수
* 무방향 그래프: 각 정점 쌍에 대해 하나의 간선만 존재하므로 조합(순서 X)
* 방향 그래프: 각 정점 쌍에 대해 양방향 간선이 가능하므로 순열(순서 O)
1) 무방향 그래프 예
|V|={A, B, C, D}로 4개일 때
가능한 간선 조합의 목록은 다음과 같습니다
- (A, B)
- (A, C)
- (A, D)
- (B, C)
- (B, D)
- (C, D)
총 6개의 간선이 만들어집니다
계산으로 간선의 개수를 도출해보면 다음과 같습니다.
2) 방향 그래프 (Directed Graph)
|V|={A, B, C, D}로 4개일 때
가능한 간선 조합의 목록은 다음과 같습니다
- (A → B), (B → A)
- (A → C), (C → A)
- (A → D), (D → A)
- (B → C), (C → B)
- (B → D), (D → B)
- (C → D), (D → C)
총 12개의 방향 간선
간선의 개수를 계산으로 풀면 다음과 같습니다.
3) 왜 간선 수의 최댓값이 O(|V|²) 일까?
간선 최대 개수는 정점 수의 제곱에 비례합니다
각 간선을 도출하는 수식을 보면
무방향 그래프 최대 간선 수:
방향 그래프 최대 간선 수:
위 식에서 보듯이 분자나 곱셈 항이 |V|^2 (정점 개수의 제곱)에 비례합니다.
예를 들어, 정점 수가 1000개라면 최대 간선 수는 약 1000 × 999 ≈ 1,000,000개에 가깝습니다.
빅오 표기법으로 나타내면?
상수와 덧셈 항을 무시하고 가장 큰 차수 항만 봅니다.
3. Neighbor Sets/Adjacencies
• The outgoing neighbor set of u ∈ V is Adj⁺(u) = {v ∈ V | (u, v) ∈ E}
정점 u의 출력 이웃 집합은 Adj⁺(u) = {v ∈ V | (u, v) ∈ E}이다.
u에서 방향이 나가는 간선이 연결된 모든 정점들의 집합입니다.
즉, u → v 형태의 간선이 있을 때 그 v들을 모은 것.
* {v ∈ V | (u, v) ∈ E}: 집합을 정의하는 수학적 표기법
* v ∈ V: V에 속한 모든 정점 v 중에서, 어떤 조건을 만족하는 v들만 모은 집합
* (u, v) ∈ E: 간선의 두 점 (u, v). u에서 v로 나감
예시) 그래프 G = (V, E)가 다음과 같다고 해볼게요
- 정점 집합 V = {A, B, C, D}
- 간선 집합 E = { (A, B), (A, C), (B, D), (C, D) } (→ 방향이 있는 간선, 예: A → B)
이때 각 정점의 outgoing neighbor set, 즉 Adj⁺(u)는 다음과 같습니다:
- Adj⁺(A) = {B, C}
→ A에서 나가는 간선: A → B, A → C - Adj⁺(B) = {D}
→ B에서 나가는 간선: B → D - Adj⁺(C) = {D}
→ C에서 나가는 간선: C → D - Adj⁺(D) = ∅
→ D는 나가는 간선이 없음
• The incoming neighbor set of u ∈ V is Adj⁻(u) = {v ∈ V | (v, u) ∈ E}
정점 u의 입력 이웃 집합은 Adj⁻(u) = {v ∈ V | (v, u) ∈ E}이다.
u로 방향이 들어오는 간선이 연결된 모든 정점들의 집합입니다.
즉, v → u 형태의 간선이 있을 때 정점 u로 들어오는 간선의 시작점들의 집합
예를 들어 다음과 같은
그래프 G = (V, E)가 있을 때
- V = {A, B, C, D}
- E = { (A, B), (A, C), (B, D), (C, D) }
이 방향 그래프에서 각 정점의 incoming neighbor set은 다음과 같아요:
- Adj⁻(A) = ∅
→ A로 들어오는 간선 없음 - Adj⁻(B) = {A}
→ B는 A로부터 간선이 들어옴: A → B - Adj⁻(C) = {A}
→ C는 A로부터 간선이 들어옴: A → C - Adj⁻(D) = {B, C}
→ D는 B, C로부터 간선이 들어옴: B → D, C → D
• The out-degree of a vertex u ∈ V is deg⁺(u) = |Adj⁺(u)|
정점 u의 출력 차수(out-degree)는 deg⁺(u) = Adj⁺(u)의 크기이다.
u의 출력 차수(out-degree)는 u에서 나가는 간선의 개수입니다.
즉, u가 몇 개의 정점으로 연결되는지를 나타냅니다.
예를 들어 다음과 같은
그래프 G = (V, E)가 있을 때
- V = {A, B, C, D}
- E = { (A, B), (A, C), (B, D), (C, D) }
각 정점의 out-degree (deg⁺)는 다음과 같아요:
- deg⁺(A) = |{B, C}| = 2
→ A에서 나가는 간선 2개 (A → B, A → C) - deg⁺(B) = |{D}| = 1
→ B → D - deg⁺(C) = |{D}| = 1
→ C → D - deg⁺(D) = |∅| = 0
→ 나가는 간선 없음
• The in-degree of a vertex u ∈ V is deg⁻(u) = |Adj⁻(u)|
정점 u의 입력 차수(in-degree)는 deg⁻(u) = Adj⁻(u)의 크기이다.
u의 입력 차수(in-degree)는 u로 들어오는 간선의 개수입니다.
즉, 몇 개의 정점에서 u로 연결되는지를 나타냅니다.
위와 같은 그래프에서
이때 각 정점의 in-degree는:
- deg⁻(A) = |∅| = 0
→ A로 들어오는 간선 없음 - deg⁻(B) = |{A}| = 1
→ A → B - deg⁻(C) = |{A}| = 1
→ A → C - deg⁻(D) = |{B, C}| = 2
→ B → D, C → D
• For undirected graphs, Adj⁻(u) = Adj⁺(u) and deg⁻(u) = deg⁺(u)
무방향 그래프에서는 Adj⁻(u) = Adj⁺(u), deg⁻(u) = deg⁺(u)이다.
방향이 없기 때문에 들어오고 나가는 개념이 구분되지 않습니다.
연결된 이웃은 모두 같은 집합이고, 차수도 같음.
예를 들어 다음과 같은
그래프 G = (V, E)가 있을 때
- V = {A, B, C, D}
- E = { {A, B}, {A, C}, {B, D}, {C, D} } (집합으로 표현해서 방향이 없음을 나타냄)
정점 u | Adj(u) | deg(u) |
A | {B, C} | 2 |
B | {A, D} | 2 |
C | {A, D} | 2 |
D | {B, C} | 2 |
- 여기서 Adj⁺(u) = Adj⁻(u) = Adj(u)
- deg⁺(u) = deg⁻(u) = deg(u) = |Adj(u)|
방향 그래프 (Directed) | 무방향 그래프 (Undirected) |
A → B | A — B |
B → D | B — D |
→ in/out 구분됨 | → in/out 개념 없음 |
deg⁺(D) = 2, deg⁻(D) = 0 | deg(D) = 2 (양방향 연결만 있음) |
• Dropping superscript defaults to outgoing, i.e., Adj(u) = Adj⁺(u) and deg(u) = deg⁺(u)
지수(⁺, ⁻)를 생략하면 기본적으로 출력(outgoing)을 의미한다. 즉, Adj(u) = Adj⁺(u), deg(u) = deg⁺(u)
특별히 명시하지 않으면, 이웃이나 차수를 말할 때 출력 기준으로 간주합니다
- Adj⁺(u)는 u에서 나가는 이웃들
- Adj⁻(u)는 u로 들어오는 이웃들
→ 그런데 Adj(u)라고 쓸 경우 → Adj⁺(u)로 간주한다는 의미입니다.
같은 방식으로:
- deg(u) → deg⁺(u)로 해석합니다.
즉, 생략하면 outgoing이 기본입니다.
* superscript: 여기서는 위첨자 (예: +, -)를 말합니다.
* dropping: 생략하는 것
* defaults: 기본적으로 ~로 간주한다
4. Graph Representations
그래프를 메모리상에 어떻게 저장하고 다룰지를 알아봅시다
• To store a graph G = (V, E), we need to store the outgoing edges Adj(u) for all u ∈ V
그래프 G = (V, E)를 저장하려면 모든 정점 u ∈ V에 대해 Adj(u) (출력 이웃)를 저장해야 한다.
각 정점에서 나가는 간선들을 기억해 두어야 그래프 탐색이 가능하다는 뜻입니다.
• First, need a Set data structure Adj to map u to Adj(u)
먼저, 정점 u를 Adj(u)로 매핑해 줄 수 있는 Set 자료구조 Adj가 필요하다.
이건 일종의 딕셔너리처럼 정점 u를 키로, u의 이웃 정점들을 값으로 저장하는 구조입니다.
1) 예시: 방향 그래프 (Directed Graph)
그래프 G = (V, E)
- V = {A, B, C, D}
- E = { (A, B), (A, C), (B, D), (C, D) } 인 경우
인접 리스트로 저장하는 방법은 다음과 같습니다
Adj = {
'A': {'B', 'C'},
'B': {'D'},
'C': {'D'},
'D': set()
}
여기서 Adj['A']는 A에서 나가는 이웃 정점들, 즉 {B, C}
- Adj는 딕셔너리(Dictionary) 또는 맵(Map)처럼 생긴 자료구조
- 각 키 u ∈ V는 정점
- 각 값 Adj(u)는 u에서 나가는 이웃 정점들의 집합 (Set)
Set 사용 (예: 'A': {'B', 'C'})
- 중복된 간선이 필요 없는 경우
- 이웃 정점이 있는지 빠르게 확인하고 싶을 때 (in 연산이 빠름)
- 방향 그래프나 무방향 그래프에서 간선이 1개씩만 있을 때 일반적으로 사용
2) 예시: 무방향 그래프
위 그래프를 무방향 그래프로 바꾸면 E = { {A, B}, {A, C}, {B, D}, {C, D} }
Adj = {
'A': {'B', 'C'},
'B': {'A', 'D'},
'C': {'A', 'D'},
'D': {'B', 'C'}
}
• Then for each u, need to store Adj(u) in another data structure called an adjacency list
그리고 각 u에 대해 Adj(u)를 저장할 자료구조가 필요한데, 이걸 adjacency list (인접 리스트)라고 부른다.
각 정점마다 이웃 정점들의 목록을 저장한 구조입니다.
가장 일반적인 그래프 표현 방식 중 하나입니다.
Adjacency list란 각 정점 u를 키(key)로 하고, u와 연결된 정점들의 리스트(또는 집합)를 값(value)으로 갖는 자료구조입니다.
Adj(u) 자체가 리스트나 배열 또는 집합(Set)으로 저장
1) 예시 방향 그래프
그래프 G = (V, E):
- V = {A, B, C, D}
- E = { (A, B), (A, C), (B, D), (C, D) }
AdjacencyList = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D'],
'D': []
}
여기서 AdjacencyList['A']가 바로 A의 인접 리스트에 해당합니다.
- Adj(u)는 u의 이웃들 집합
- Adj(u)는 다시 인접 리스트(adjacency list)라는 자료구조에 저장
- 전체 그래프는 Adj라는 맵(Map)으로 표현
List 사용 (예: 'A': ['B', 'C'])
- 정점의 이웃 순서를 유지하고 싶을 때
- 중복 간선이 가능하거나 필요할 수 있을 때 (예: 멀티그래프)
- 순회 시 순서가 중요하거나, index 접근이 필요한 경우
2) 무방향 그래프
무방향 그래프 G = (V, E):
- V = {A, B, C, D}
- E = { {A, B}, {A, C}, {B, D}, {C, D} }
AdjacencyList = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
- 한 간선 {u, v}는 u와 v 각각의 인접 리스트에 서로 추가됨
- 방향 그래프와 거의 같은 구조지만, 양쪽에 모두 기록
• Common to use direct access array or hash table for Adj, since want lookup fast by vertex
Adj는 보통 배열이나 해시 테이블로 구현한다. 이유는 정점을 기준으로 빠르게 검색하고 싶기 때문이다.
빠른 조회 속도를 위해 정점 u로 바로 접근할 수 있는 자료구조를 씁니다.
해시 테이블이면 O(1), 배열이면 정수 인덱스로 바로 접근 가능합니다.
* Adj = 전체의 인접 리스트 Adjacency List
* Adj = {
'A': ['B', 'C'], # Adj('A')
'B': ['D'], # Adj('B')
'C': ['D'], # Adj('C')
'D': [] # Adj('D')
}
• Common to use array or linked list for each Adj(u) since usually only iteration is needed
각 Adj(u)는 보통 배열 또는 연결 리스트로 구현한다. 대부분 순회(iteration)만 필요하기 때문이다.
이웃 정점들을 하나씩 순회하면서 탐색할 수 있으면 되기 때문에, 간단한 자료구조면 충분합니다.
• For the common representations, Adj has size Θ(|V|), while each Adj(u) has size Θ(deg(u))
일반적인 표현 방식에서는 Adj의 크기는 Θ(|V|), 각 Adj(u)의 크기(공간 복잡도)는 Θ(deg(u))이다.
Adj는 모든 정점 u에 대해 Adj(u)를 저장하는 자료구조입니다
이 Adj 자체의 크기(= Adj가 저장하는 키, 즉 정점의 수)는 Θ(|V|) 정점 개수에 비례합니다
그리고 각각의 Adj(u) (u의 인접 리스트)의 크기는 그 정점 u의 deg(u) (degree, 연결된 간선 수)에 비례합니다
그래서 Adj(u) 크기는 Θ(deg(u))입니다
• Since ∑₍u ∈ V₎ deg(u) ≤ 2|E| by handshaking lemma, graph storable in Θ(|V| + |E|) space
핸드셰이킹 정리에 따라 모든 정점의 차수를 합한 값은 2|E| 이내이다 (무방향 그래프의 경우 정확히 ∑deg(u) = 2|E|)
그래서 그래프 전체를 저장하는 데 드는 공간은 정점 수 + 간선 수에 비례한다, 즉 Θ(|V| + |E|)
예를 들어
무방향 그래프 G = (V, E):
- V = {A, B, C, D}
- E = { {A, B}, {A, C}, {B, D}, {C, D} } → 총 4개의 간선
각 정점의 차수 (deg):
- deg(A) = 2
- deg(B) = 2
- deg(C) = 2
- deg(D) = 2
∑deg(u) = 2 + 2 + 2 + 2 = 8 = 2 × 4 = 2|E|
→ 그러므로 전체 인접 리스트의 항목 수 = 8
→ 정점 키 4개 + 이웃 원소 8개 → 총 메모리 공간 = Θ(4 + 8) = Θ(|V| + |E|)
* lemma: 하나의 큰 정리를 증명할 때, 중간 단계에서 먼저 증명해두면 유용한 작은 주장
* handshaking lemma (악수 보조정리)
이 정리는 모든 사람들이 서로 악수하면, 총 악수 수는 사람 수의 절반만 세면 된다는 직관에서 유래했습니다.
A가 B와 악수하고, B도 A와 악수했으니 두 번 세지지요.
그래서 모든 사람의 악수 수(=차수)를 더하면 2배가 되는 것입니다.
인접 리스트 방식 공간 복잡도는
- 각 정점 키를 저장: Θ(|V|)
- 각 정점의 이웃들을 저장: 총 Θ(|E|)개
- 전체 메모리 사용량 = Θ(|V| + |E|)
이건 그래프를 저장하는 데 가장 효율적인 방법 중 하나입니다.
• Thus, for algorithms on graphs, linear time will mean Θ(|V| + |E|) (linear in size of graph)
따라서 그래프 알고리즘에서 선형 시간(linear time)이란 Θ(|V| + |E|), 즉 그래프 크기에 비례하는 시간 복잡도를 의미한다.
이론에서 말하는 선형 시간은 배열의 O(n)과 같은 개념이지만, 그래프에서는 정점 수와 간선 수의 합이 기준입니다.
5. Examples
• Examples 1 and 2 assume vertices are labeled {0, 1, . . . , |V| − 1},
so can use a direct access array for Adj, and store Adj(u) in an array.
예제 1과 2는 정점들이 {0, 1, ..., |V| − 1} 식으로 라벨링되어 있다고 가정한다.
그래서 Adj를 직접 접근 배열(direct access array)로 구현할 수 있고, 각 Adj(u)도 배열로 저장한 경우를 볼 수 있다.
정점이 연속된 숫자로 되어 있는 경우 인덱스를 배열에 그대로 쓸 수 있어서 매우 빠르게 접근할 수 있습니다.
예: Adj[2]는 정점 2의 이웃 목록
• Example 3 uses a hash table for Adj.
예제 3에서는 Adj를 해시 테이블(hash table)로 구현한 경우이다
정점이 숫자가 아니라 문자열이나 랜덤 ID처럼 비연속적인 경우, 배열 대신 해시 테이블이 적합합니다.
예: Adj["nodeA"]처럼 키로 빠르게 접근하려면 해시가 필요합니다.
A hash table for each Adj(u) can allow checking for an edge (u, v) ∈ E in O(1)_(e) time
각 Adj(u)를 해시 테이블로 구현하면, (u, v) ∈ E 여부를 O(1)(평균) 시간에 확인할 수 있다.
특정 이웃이 존재하는지 빠르게 검사하고 싶을 때 유용함.
예: if v in Adj[u]를 빠르게 처리 가능. 배열/리스트로 하면 O(deg(u)) 시간이 걸리지만, 해시 테이블이면 O(1)
Note that in an undirected graph, connections are symmetric as every edge is outgoing twice
무방향 그래프에서는 연결이 대칭적이다. 모든 간선이 두 번의 출력 간선으로 간주되기 때문이다.
예: 정점 u와 v가 연결되어 있으면, Adj(u)에도 v가 있고 Adj(v)에도 u가 있음. 즉, (u, v)와 (v, u) 둘 다 출력 간선처럼 작동함.
6. Paths
• A path is a sequence of vertices p = (v₁, v₂, ..., vₖ) where (vᵢ, vᵢ₊₁) ∈ E for all 1 ≤ i < k.
경로(path)란 정점들의 나열 p = (v₁, v₂, ..., vₖ)로, 각 연속된 정점 쌍 (vᵢ, vᵢ₊₁)가 간선 (vᵢ, vᵢ₊₁) ∈ E일 때를 말한다.
즉, v₁에서 시작해서 v₂로, v₂에서 v₃로… 이렇게 간선들을 따라 이동할 수 있는 정점의 순서입니다.
• A path is simple if it does not repeat vertices
경로가 단순(simple)하다는 것은 정점을 반복하지 않는다는 뜻이다.
다시 말해, 같은 정점을 두 번 이상 지나지 않는 경로를 simple path라고 부릅니다.
루프나 사이클이 없는 깨끗한 경로.
• The length (p) of a path p is the number of edges in the path
경로 p의 길이 (p)는 그 경로에 포함된 간선의 개수이다.
정점이 k개인 경로라면 간선은 k - 1개이고, 이것이 길이입니다.
예: (A, B, C, D) → 길이는 3 (A-B, B-C, C-D)
• The distance δ(u, v) from u ∈ V to v ∈ V is the minimum length of any path from u to v,
i.e., the length of a shortest path from u to v
정점 u에서 v까지의 거리 δ(u, v)는 u에서 v로 가는 가장 짧은 경로의 길이를 의미한다.
여러 경로가 있을 수 있지만, 그중 가장 적은 간선 수를 갖는 경로의 길이가 거리입니다.
(by convention, δ(u, v) = ∞ if u is not connected to v)
관례상, u에서 v로 갈 수 없다면 δ(u, v)는 무한(∞)으로 정의한다.
즉, 경로 자체가 존재하지 않으면 도달 불가능하므로 거리도 무한입니다.
7. Graph Path Problems
• There are many problems you might want to solve concerning paths in a graph:
그래프에서 경로를 이용해 해결하고 싶은 문제들이 많을 것이다
다양한 종류의 "경로 탐색 문제"를 소개합니다.
• SINGLE PAIR REACHABILITY(G, s, t): is there a path in G from s ∈ V to t ∈ V ?
단일 쌍 도달 가능성(SINGLE PAIR REACHABILITY): G에서 정점 s에서 정점 t까지 경로가 존재하는가?
단순히 연결되어 있는지 여부만 판단하는 문제입니다. (예: 친구 추천 시스템에서 '두 사람 연결 가능?')
• SINGLE PAIR SHORTEST PATH(G, s, t): return distance δ(s, t), and a shortest path in G = (V, E) from s ∈ V to t ∈ V
단일 쌍 최단 경로(SINGLE PAIR SHORTEST PATH): s에서 t까지의 거리 δ(s, t)와 가장 짧은 경로를 반환
연결 여부뿐 아니라, 최소 간선 경로를 실제로 구하는 문제입니다.
• SINGLE SOURCE SHORTEST PATHS(G, s): return δ(s, v) for all v ∈ V , and a shortest-path tree containing a shortest path from s to every v ∈ V (defined below)
단일 출발점 최단 경로(SINGLE SOURCE SHORTEST PATHS): 정점 s에서 모든 정점 v ∈ V까지의 거리 δ(s, v)와,
각각의 최단 경로들을 포함하는 최단 경로 트리(shortest-path tree)를 반환
s에서 모든 정점으로 가는 최단 경로를 구하는 문제입니다. (예: GPS에서 한 지점에서 모든 목적지까지의 경로)
• Each problem above is at least as hard as every problem above it
(i.e., you can use a black-box that solves a lower problem to solve any higher problem)
위의 문제들은 아래의 문제보다 항상 어렵거나 같으며,
즉, 더 복잡한 문제를 해결하는 알고리즘이 있으면, 그것을 활용해 더 간단한 문제도 풀 수 있다
예: "최단 경로" 알고리즘이 있으면, 단순히 "도달 가능한가?"도 쉽게 알 수 있습니다.
• We won’t show algorithms to solve all of these problems
우리는 이 모든 문제를 푸는 알고리즘을 전부 다루진 않는다.
• Instead, show one algorithm that solves the hardest in O(|V| + |E|) time!
대신, 이들 중 가장 어려운 문제를 선형 시간 O(|V| + |E|) 안에 해결하는 하나의 알고리즘을 소개한다!
미리 귀뜸하자면 이 알고리즘은 BFS입니다.
8. Shortest Paths Tree
• How to return a shortest path from source vertex s for every vertex in graph?
그래프의 모든 정점에 대해 시작 정점 s로부터의 최단 경로를 어떻게 반환할까?
s → 모든 정점으로 가는 최단 경로를 각각 저장하고 싶다면?
• Many paths could have length Ω(|V|), so returning every path could require Ω(|V|²) time
어떤 최단 경로는 길이가 Ω(|V|)일 수 있으므로, 모든 경로를 반환하려면 Ω(|V|²) 시간이 걸릴 수 있다.
다음과 같은 그래프가 있을 때
- A-B-C 경로와 A-D-C 경로가 있음
- 가중치: A-B=1, B-C=1, A-D=1, D-C=1
A → C:
- distance(A, C) = 2 (두 경로 다 2이므로 동일)
- path(A, C) =
- [A, B, C] 도 될 수 있고
- [A, D, C] 도 될 수 있음
목적지 C까지 가는 경로는 여러가지 일 수 있지만, 거리는 하나로 결정됩니다.
개념 | 의미 | 예시 |
distance | 정점 간 최단 경로의 길이 ("몇 개의 간선을 지나가는가?") A → C까지 거리 | 2 |
path | 실제 최단 경로를 이루는 정점들의 순서 | A → B → C |
도착 정점 | 최단 경로 | 길이 |
v₂ | [v₁, v₂] | 1 |
v₃ | [v₁, v₂, v₃] | 2 |
v₄ | [v₁, v₂, v₃, v₄] | 3 |
... | ... | ... |
vₙ | [v₁, v₂, ..., vₙ] | n-1 |
모든 경로들의 길이의 합은 "모든 경로를 출력하거나 저장하는 데 필요한 최소한의 정보량"
각 최단 경로의 길이(간선 수)를 모두 더한 것이고,
그 총합은 전체 경로들을 출력하는 데 필요한 최소 공간 또는 시간
전체 경로들의 길이 합 ≈ 1 + 2 + 3 + ... + (n - 1) = (n(n-1))/2 = Θ(n²)
|V|개의 정점이 있는 그래프에서, 정점 s로부터 모든 정점 v에 대한 최단 경로를 구하려고 할 때
최단 거리(distance)만 구하면 O(|V| + |E|)면 충분하지만,
경로(path 자체)를 모두 저장하거나 반환하려면 경로 하나하나가 길고 많을 수 있습니다
그래프 알고리즘에서:
- "거리만 필요" → BFS나 Dijkstra 결과의 dist[v]만 보면 됨
- "경로도 필요" → prev[v]를 통해 추적하거나, 아예 경로 리스트를 저장해야 함
→ 메모리/시간 많이 듬
• Instead, for all v ∈ V, store its parent P(v): second to last vertex on a shortest path from s
그래서 모든 정점 v ∈ V에 대해 부모 정점 P(v)만 저장한다. 이건 s에서 v로 가는 최단 경로의 마지막 바로 전 정점이다.
이 정보를 통해 경로 전체를 복원할 수 있음.
다음 그래프 G 가 있는 경우
- 정점: V = {A, B, C, D}
- 시작점: s = A
- 간선: (A-B), (B-C), (C-D) → 간선 길이 모두 1
최단 거리와 부모 저장
(BFS 또는 Dijkstra 알고리즘을 통해) A로부터의 최단 경로를 구하면서 각 정점의 부모 P(v)를 저장
정점 v | 최단 거리 (dist(v)) | 부모 P(v) |
A | 0 | null (시작점) |
B | 1 | A |
C | 2 | B |
D | 3 | C |
경로 복원 방법 (A → D)
- D의 부모는 C
- C의 부모는 B
- B의 부모는 A
→ 역으로 따라가면: D ← C ← B ← A
→ 뒤집으면: A → B → C → D
왜 이 방법이 효율적인가?
- 각 정점마다 한 개의 부모만 저장 → 공간: O(|V|)
- 어떤 정점까지의 경로가 필요할 때, 역추적해서 경로를 복원하면 됨 → 시간: O(path 길이)
- 경로 전체를 미리 저장하는 것보다 훨씬 공간/시간 효율적
• Let P(s) be null (no second to last vertex on shortest path from s to s)
시작 정점 s는 자기 자신으로 가는 경로의 전 정점이 없으므로, P(s)는 null이다.
즉, s는 트리의 루트입니다.
* second to last: 끝에서 두 번째. 경로 A → B → C → D 에서 D의 second-to-last는 C
* s → s는?
- s에서 s로 가는 경로는 그냥 [s]
- 경로에 정점 하나뿐이니까:
- 첫 번째 정점 = s
- 마지막 정점 = s
- second-to-last 정점 없음!
따라서 P(s) = null
• Set of parents comprise a shortest paths tree with O(|V|) size!
각 정점 v에 대해 부모 정점 P(v)를 저장하면, 이 부모들로 이루어진 구조 전체가 하나의 “최단 경로 트리”를 구성하고,
이 트리의 크기는 정점 수 |V|에 비례, 즉 O(|V|)이다.
모든 정점이 하나의 부모만 가지므로, 간선 수도 O(|V|)이고 전체가 트리 구조가 됨.
방향성 있는 그래프, 없는 그래프 모두에서 사용 가능하지만
방향성 없는 그래프 예로 들어보면
최단 경로 탐색 결과
정점 v | P(v) (부모 정점) |
A | null |
B | A |
C | A |
D | B |
이렇게 P(v)를 저장하면, 아래처럼 부모를 따라가는 경로들이 생깁니다:
- D → B → A
- B → A
- C → A
이것들이 모여서 다음과 같은 트리를 이룹니다:
이것이 Shortest Path Tree (SPT)입니다
A에서 출발해 모든 정점으로 가는 최단 경로만 포함한 트리
왜 O(|V|)인가?
- 트리는 정점 |V|개에 대해 간선 |V| - 1개만 가짐
- 각 정점 v마다 P(v) 하나만 저장 → 총 |V|개 저장
- 공간도 O(|V|), 트리 크기도 O(|V|)
(i.e., reversed shortest paths back to s from every vertex reachable from s)
즉, 각 정점에서 시작 정점 s로 거꾸로 돌아가는 최단 경로들을 연결한 구조이다.
정점마다 "어디서 왔는지"만 알고 있으면 전체 경로를 역추적할 수 있음.
9. Breadth-First Search (BFS)
Breadth-First Search (BFS)
BFS는 시작 정점 s로부터 모든 정점 v에 대해 거리 δ(s, v)와 부모 정점 P(v)를 구하는 알고리즘입니다.
"모든 간선의 가중치가 동일한 그래프(= 무가중치 그래프)"에서만 최단 거리를 정확하게 구할 수 있습니다.
왜 BFS로 최단 거리를 구할 수 있을까?
BFS는 그래프를 거리 순으로 탐색합니다.
- 시작 정점 s에서 거리 0인 정점 방문
- → 거리 1인 정점들 방문
- → 거리 2인 정점들 방문
- … 이런 식으로 거리가 가까운 정점부터 차례대로 방문하므로
처음으로 어떤 정점 v를 방문했을 때,
v까지 가는 최단 거리 δ(s, v)를 찾았다고 볼 수 있습니다
만약 그래프에 가중치가 있다면
- BFS는 가중치를 무시하고 거리만 재므로 틀린 결과 나올 수 있음
- 이 경우에는 Dijkstra 알고리즘을 사용해야 함
• How to compute δ(s, v) and P(v) for all v ∈ V ?
시작 정점 s에서 부터 모든 정점 v까지의 거리 δ(s, v)와 부모 정점 P(v)를 어떻게 구할까?
* δ(s, v): 시작점 s에서 정점 v까지의 최단 거리 (distance. 간선 몇 개를 거쳐서 가는지)
* P(v): v로 가는 최단 경로 상의 직전 정점 (parent)
• Store δ(s, v) and P(v) in Set data structures mapping vertices v to distance and parent
δ(s, v)와 P(v)를 각각의 정점 v에 매핑하는 Set 자료구조에 저장한다.
딕셔너리나 해시 테이블처럼, 각 정점마다 거리와 부모 정보를 저장.
distance = {
v1: δ(s, v1),
v2: δ(s, v2),
...
}
parent = {
v1: P(v1),
v2: P(v2),
...
}
예를 들어 다음과 같은 그래프에서는 다음과 같이 저장할 수 있습니다
distance = {
'A': 0,
'B': 1,
'C': 2
}
parent = {
'A': None,
'B': 'A',
'C': 'B'
}
- 'C'까지 거리를 알고 싶으면: distance['C'] → 2
- 'C'까지 경로를 복원하고 싶으면:
C → B → A 역추적 → 뒤집으면 A → B → C
• (If no path from s to v, do not store v in P and set δ(s, v) to ∞)
s에서 v로 가는 경로가 없으면 P에 v를 저장하지 않고, δ(s, v)는 ∞로 설정한다.
도달 불가능한 정점은 부모 없음(null)이고, 거리는 무한.
distance = {
'A': 0,
'B': 1,
'C': 2,
'D': ∞ # 도달 불가능. A와 연결되어 있지 않음
}
parent = {
'A': None,
'B': 'A',
'C': 'B'
# D는 저장하지 않음 (도달 불가능)
}
• Idea! Explore graph nodes in increasing order of distance
핵심 아이디어: 그래프 정점들을 거리 순서대로 탐색하자.
먼저 가까운 정점을 다 보고, 그다음에 더 멀리 있는 정점들을 본다. 이것이 BFS의 핵심 개념.
• Goal: Compute level sets Lᵢ = {v | v ∈ V and δ(s, v) = i} (i.e., all vertices at distance i)
목표: 거리 i인 정점들의 집합인 레벨 집합 Lᵢ를 계산하는 것이다.
δ(s, v): 시작점 s에서 v까지의 최단 거리
P(v): 시작점 s에서 v까지의 최단 경로에서, v의 바로 앞 정점 (Parent)
i: 시작점 s로부터의 거리 (0, 1, 2, ...)
Lᵢ: 거리 i에 있는 정점들의 집합 (level set)
다음과 같은 그래프에서
- 시작 정점 s = A
- 모든 간선의 길이 = 1
BFS 탐색 결과
정점 v | δ(s, v) | 속한 레벨 Lᵢ | 설명 |
A | 0 | L₀ = {A} | 시작점 s |
B | 1 | L₁ = {B} | 거리 1인 이웃들. s와 직접 연결된 정점들 |
C, D | 2 | L₂ = {C, D} | 거리 2인 이웃들. 그 다음 정점들 … 이런 식으로 레벨별로 정리를 함. |
• Claim: Every vertex v ∈ Lᵢ must be adjacent to a vertex u ∈ Lᵢ₋₁ (i.e., v ∈ Adj(u))
주장: 레벨 집합 Lᵢ에 있는 모든 정점 v는 반드시 바로 이전 레벨 Lᵢ₋₁의 어떤 정점 u에 인접해 있어야 한다.
BFS는:
- 시작 정점 s에서 탐색을 시작해서 (L₀ = {s})
- 그 이웃들을 L₁로 넣고,
- L₁의 이웃 중 아직 안 본 정점들을 L₂로 넣고,
- 이런 식으로 한 레벨씩 확장해 나갑니다.
그래서 Lᵢ에 있는 정점은 무조건 바로 이전 레벨 Lᵢ₋₁에 있는 정점의 이웃이 될 수밖에 없습니다
다음과 같은 그래프에서
시작 정점: s = A
BFS 순서:
- L₀ = {A}
- L₁ = {B} (A의 이웃)
- L₂ = {C, D} (B의 이웃)
여기서:
- C ∈ L₂ → C는 B의 이웃 → B ∈ L₁
- D ∈ L₂ → D도 B의 이웃 → B ∈ L₁
따라서 모든 v ∈ L₂는 어떤 u ∈ L₁에 인접합니다.
• Claim: No vertex that is in Lⱼ for some j < i, appears in Lᵢ
주장: Lᵢ보다 가까운 레벨 Lⱼ (j < i)에 속한 정점은 Lᵢ에 다시 나타나지 않는다.
BFS 레벨 집합 L₀, L₁, L₂, ..., Lᵢ를 만들 때,
이미 L₀, L₁, ..., Lᵢ₋₁에서 등장한 정점은
절대 다시 Lᵢ에 포함되지 않는다.
왜냐하면
- BFS는 정점들을 거리 순서대로 방문하기 때문에
- 먼저 방문된 정점이 더 짧은 거리의 경로를 가진 것이고
- 그 정점은 나중에 다시 더 긴 거리로 방문될 일이 없어요.
다음 그래프에서
시작 정점: A
BFS 탐색:
- L₀ = {A}
- L₁ = {B}
- L₂ = {C, D}
여기서 B는 L₁에 이미 등장했기 때문에
절대 L₂나 L₃ 등 뒤 레벨 집합에 다시 등장하지 않음
"B는 L₁에만 있다."
• Invariant: δ(s, v) and P(v) have been computed correctly for all v in any Lⱼ for j < i
레벨 i를 탐색하기 전까지 모든 이전 레벨 L₀, L₁, ..., Lᵢ₋₁에 있는 정점들에 대해서는
최단 거리 δ(s, v), 부모 정점 P(v) 이 올바르게 계산되어 있다
* δ(s, v): 시작점 s에서 v까지의 최단 거리
* P(v): 시작점 s에서 v까지의 최단 경로에서, v의 바로 앞 정점 (Parent)
레벨 i를 탐색할 때 이전 레벨 j < i의 결과는 신뢰할 수 있어야 합니다
다음 그래프에서
BFS 레벨 탐색 결과:
- L₀ = {A} → δ(A) = 0, P(A) = None
- L₁ = {B} → δ(B) = 1, P(B) = A
- L₂ = {C, D} → δ(C) = 2, P(C) = B / δ(D) = 2, P(D) = B
L₂를 계산할 때는 반드시 L₁의 정보(거리와 부모)가 정확해야
C, D의 거리와 부모를 정확하게 구할 수 있어요.
• Base case (i = 1): L₀ = {s}, δ(s, s) = 0, P(s) = None
Base case: i = 1일 때
L₀은 시작 정점 s만 포함하는 집합이며,
s에서 자기 자신까지의 거리 δ(s, s)는 0,
s의 부모는 없으므로 P(s) = None
• Inductive Step: To compute Lᵢ:
귀납적 단계: i 번째 레벨 Lᵢ를 계산하는 방법은 다음과 같다.
– for every vertex u in Lᵢ₋₁:
바로 이전 레벨 Lᵢ₋₁에 있는 모든 정점 u에 대해
∗ for every vertex v ∈ Adj(u) that does not appear in any Lⱼ for j < i:
u의 인접 정점들 중, 아직 이전 레벨들(L₀부터 Lᵢ₋₁)에 등장하지 않은 정점 v에 대해
· add v to Lᵢ, set δ(s, v) = i, and set P(v) = u
정점 v를 현재 레벨 Lᵢ에 추가하고,
δ(s, v) = i로 설정 (s로부터의 거리),
P(v) = u로 설정 (v의 부모는 u)
• Repeatedly compute Lᵢ from Lⱼ for j < i for increasing i until Lᵢ is the empty set
Lᵢ가 빈 집합이 될 때까지 i를 증가시키며 Lⱼ로부터 Lᵢ를 계속 계산한다.
더 이상 탐색할 정점이 없을 때까지 반복.
• Set δ(s, v) = ∞ for any v ∈ V for which δ(s, v) was not set
δ(s, v)가 설정되지 않은 정점 v에 대해서는 경로가 없다는 뜻이므로 δ(s, v) = ∞로 설정한다.
• Breadth-first search correctly computes all δ(s, v) and P(v) by induction
너비 우선 탐색(BFS)은 모든 정점 v에 대해 s로부터의 거리 δ(s, v)와 부모 정점 P(v)를 수학적 귀납법(induction)으로 정확히 계산한다.
이전 레벨에서 정확하게 계산된 정보를 기반으로 다음 레벨도 정확하게 계산되므로 전체 결과가 옳다.
• Running time analysis:
실행 시간 분석입니다.
– Store each Lᵢ in data structure with Θ(|Lᵢ|)-time iteration and O(1)-time insertion
(i.e., in a dynamic array or linked list)
각 레벨 집합 Lᵢ는 다음 조건을 만족하는 자료구조에 저장함
- 순회(iteration)는 Θ(|Lᵢ|)
- 삽입은 O(1)
동적 배열(dynamic array)이나 연결 리스트(linked list)를 사용한 경우
– Checking for a vertex v in any Lⱼ for j < i can be done by checking for v in P
v가 이미 이전 레벨에 등장했는지 확인하려면, P(v)가 설정되어 있는지만 보면 된다.
부모가 설정돼 있다는 건 이미 방문했다는 뜻이므로 P를 이용해 효율적 확인 가능.
– Maintain δ and P in Set data structures supporting dictionary ops in O(1) time
(i.e., direct access array or hash table)
δ와 P는 각 정점에 대해 값을 저장하는 딕셔너리(혹은 해시맵/배열)로 구현된 경우
이 자료구조는 O(1) 시간에 삽입, 조회 가능해야 한다.
– Algorithm adds each vertex u to ≤ 1 level and spends O(1) time for each v ∈ Adj(u)
각 정점 u는 최대 한 번만 어떤 레벨 집합 Lᵢ에 추가되고,
u의 인접 정점 v 각각에 대해 O(1) 시간 사용.
–Work upper bounded by O(1) × ∑ _(u∈V) deg(u) = O(|E|) by handshake lemma
그래프의 모든 정점 u에 대해 작업량은 deg(u) 만큼이며, 총합은 O(|E|)가 된다.
"악수 법칙(handshake lemma)"에 의해 모든 정점의 차수 합은 2|E| 또는 |E| 수준이므로 선형임.
– Spend Θ(|V|) at end to assign δ(s, v) for vertices v ∈ V not reachable from s
도달할 수 없는 정점 v들에 대해 δ(s, v) = ∞로 설정하는 데 Θ(|V|) 시간이 든다.
전체 정점을 순회하며 체크해야 하므로.
– So breadth-first search runs in linear time! O(|V| + |E|)
따라서 BFS는 그래프의 크기에 비례하는 선형 시간에 동작한다.
정점 수와 간선 수의 합만큼만 시간이 든다.
• Run breadth-first search from s in the graph in Example 3
예제 3의 그래프에서 시작 정점 s로부터 BFS를 실행하자.
앞에서 설명한 이론을 실제 예제에 적용하자
출처
자료 https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec9/
Lecture 9: Breadth-First Search | Introduction to Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare
MIT OpenCourseWare is a web based publication of virtually all MIT course content. OCW is open and available to the world and is a permanent MIT activity
ocw.mit.edu
참고 자료