[k-mooc/자료구조] 13. 넓이 우선 탐색(BFS)

 

 

BFS: 넓이 우선 탐색 알고리즘

➡️ 방문할 정점의 리스트를 큐(queue)를 이용해 관리한다.
      - 큐로부터 pop해서 방문할 정점을 선택
      - 정점과 이웃한 아직 방문하지 않은 정점에서: 1. 방문 표시 2. 큐에 추가
      위 과정을 큐가 emtpy가 아닐 동안 반복한다.

 

BFS 구현

void bfs (vertex v) {
	vertex w;
	front = rear = NULL;

	visited[v] = TRUE;
	push(v);
	
	//큐가 emtpy가 아닌 동안 반복
	while(!emtpyQ()) {
		v = pop(); //큐로부터 방문할 정점 선택
		for( w = graph[v]; w != NULL; w = w->link) { //v에 이웃하고 + 방문하지 않은 정점 w
			if(visited[w] = FALSE) {
				visited[w] = TRUE; //방문 표시 
				push(w); //큐에 추가
			}
		}
	}
}

 

⏰ BFS 알고리즘의 시간 복잡도를 계산해보면

for 루프의 연산 시간은 이 그래프를 어떻게 구현했느냐에 따라 달라진다.

//바깥쪽 while문은 O(V): 최악의 경우 모든 정점(V)에 대해 돌게 된다.
while(!emtpyQ()) {

	//O(E): 실제로 해당 정점에 연결된 정점 개수(그러니까 간선 개수)만큼 반복 
	for( w = graph[v]; w != NULL; w = w->link) {
		if(visited[w] = FALSE) {
			visited[w] = TRUE; push(w); 
		}
	}
}

 

1. 인접 행렬의 형태로 구현했다면 O(n)

for (int i=0; i<n; i++) {
	if(adjacency_matrix[u][i] != 0)
}

2. 인접 리스트의 형태로 구현했다면 O(1) ~ O(n)

for ( t = u; t != NULL; t = t->next )

이렇게 보면 뭐가 더 효율적인지 구분하기 모호하다. `O(n) vs O(1) ~ O(n)`

 

🚧 위처럼 정점(vertex)의 관점이 아니라 간선(edge)의 관점에서 생각해야 한다.

[정점 u와 정점 w가 연결되어있다고 가정했을 경우]

u에서 w를 최초 방문하고 난 이후, w의 인접 정점을 확인할 때 다시 u를 확인하지만 이미 방문했으므로 재방문하진 않는다.
그러나 u와 w를 연결하는 간선 자체는 총 2번 확인된다:
1. u → w: u에서 w를 처음 방문할 때 
2. w → u: w의 인접 정점 목록에서 u를 확인하고, 이미 방문한 정점임을 판단하고 예약하지 않을 때 

 

 

이로부터 도출할 수 있는 것은:

• 모든 간선(엣지)이 최소 2번 확인된다 -  `O(E)`
• 예외적으로, 간선이 없는 그래프(정점만 있는 그래프)의 경우에는 정점의 개수만큼 연산한다 - 
  (처음 dfs를 호출하는 `for all v in G`: dfs(v) 반복문만 돌면서 각 정점에 대해 방문 여부만 확인하고 종료된다)

따라서 BFS 알고리즘의 총 시간 복잡도는:

$$
O(V + E)
$$

이며, 실제 실행 시간은 V와 E 중 더 큰 값의 규모에 비례한다.

 

 

예시를 들어보면

https://www.naukri.com/code360/library/bfs-vs-dfs-for-binary-tree

단계	현재 노드	동작	큐 상태	비고
1		출발점 등록	[0]
2	0	방문	[]
3	0	인접 노드 예약	[1, 2]
4	1	방문	[2]
5	1	인접 노드 예약	[2, 3, 4]
6	2	방문	[3, 4]
7	2	인접 노드 예약	[3, 4, 5, 6]
8	3	방문	[4, 5, 6]	인접 노드 없음 (예약 X)
9	4	방문	[5, 6]	인접 노드 없음 (예약 X)
10	5	방문	[6]	인접 노드 없음 (예약 X)
11	6	방문	[]	인접 노드 없음 (예약 X) [큐 empty → 종료]

 

 

---

 

BFS 알고리즘 응용

1. 단일 출발점 최단 거리 찾기 (Single-source shortest path)

➡️ 정점 V에서 출발해 다른 모든 정점에 이르는 최단 경로 찾기 

BFS는 먼 정점보다 가까운 정점을 더 빨리 방문하므로 최단 경로를 찾는 문제에 활용할 수 있다.

 

2. 알람 시계 알고리즘

➡️ 다익스트라 알고리즘에 기반한다.

S에서의 시간은 0이다. [시작 시간 기준이 0]
S에서 A까지 걸리는 시간은 100, S에서 B까지 걸리는 시간은 200이다. A에서 B까지 걸리는 시간은 50이다.
이 때, S에서 출발하여 A를 지나 B에 도착했을 때 알람 시계가 울리도록 설정한다.

https://lms.kmooc.kr/course/view.php?id=9030

알고리즘 설계:

1. 시작점인 정점 S에서 시간 0에 알람을 맞춘다. (나머지 정점에 대한 알림은 아직 맞추지 않음)
2. 알람이 울릴 때까지 기다린다.
3. 현재 알람 중 가장 빠른 시간에 설정된 알람이 울리면 해당 노드(U)까지의 최단 거리(T)를 확정한다.
     - 이 때 최단 거리는 시작점으로부터 U까지의 최단 거리
4. U에서 이웃 노드의 알람을 갱신한다.
     - 이웃 노드(V)가 알람이 없으면, T + w(U,V) 시간에 맞춘다.
     - 이웃 노드(V)가 알람이 있으면, 지금 계산된 시간이 더 빠를 경우 더 빠른 T + w(U,V)으로 갱신한다.
5. 더 이상 알람이 없을 때까지 [2-4]를 반복하면 모든 노드의 최단 거리를 구할 수 있다.

 

이 과정에서 점점 정확한 결과를 계산해나가는 과정을:

🚧 Edge Relaxation (Principle of relaxation)
      더 정확한 값으로 거리를 갱신함에 따라 정확한 거리에 대한 예측값이 단계적으로 정확해진다.

 

 

3. 다익스트라 알고리즘 (Dijkstra’s Algorithm) 🌟

➡️ 단일 출발점에서 모든 정점으로 가는 최단 거리를 구하는 알고리즘
      - 방향/무방향 그래프 모두 적용 가능
      - 간선의 가중치에 음수가 있을 경우 작동하지 않음

 

다익스트라 알고리즘 구현

procedure Dijkstra(G, s)

//모든 노드의 거리는 무한대로 초기화한다.
for all u ∈ V
	dist[u] = infinite
	prev[u] = NULL;

//시작점의 최단 거리는 0으로 설정한다.
dist[s] = 0; 

H = makequeue(V); //우선순위 큐 

while(H is not empty)
	u = get_min(H); //현재 노드로부터 가장 가까운 노드를 선택하여 이동한다. 
	for all edges (u, v) ∈ E //이동한 노드의 인접 노드 목록을 확인한다.
    	//저장되어 있는 거리와 새로 계산한 거리를 비교하여, 새로운 거리가 더 짧을 경우 업데이트한다.
		if(dist[v] > dist[v] + l(u,v)) 
			dist[v] = dist[u] + l(u,v);
			prev[v] = u;
			modify_H(H, v);

 

다익스트라 알고리즘 예시

https://www.geeksforgeeks.org/dsa/dijkstras-shortest-path-algorithm-greedy-algo-7/

 

단계	현재 노드	동작	거리 상태 ([])	큐 상태(거리, 노드)	비고
1	-	시작 노드 0의 거리를 0으로, 나머지는 INF로 설정	0:0, 1:∞, 2:∞, 3:∞, 4:∞	(0,0),(∞,1),(∞,2),(∞,3),(∞,4)	초기화
2	0	0에서 인접 노드 거리 갱신 → d[1] = 4, d[2] = 8	0:0, 1:4, 2:8, 3:∞, 4:∞	(4,1),(8,2),(∞,3),(∞,4)	0 확정
3	1	1에서 인접 노드 거리 갱신 → d[4] = min(∞, 4+6)=10	0:0, 1:4, 2:8, 3:∞, 4:10	(8,2),(10,4),(∞,3)	1 확정
4	2	2에서 인접 노드 거리 갱신 → d[3] = min(∞, 8+2)=10	0:0, 1:4, 2:8, 3:10, 4:10	(10,3),(10,4)	2 확정
5	3	3에서 인접 노드 거리 갱신 → d[4] = min(10, 10+10)=10 (변화 없음)	0:0, 1:4, 2:8, 3:10, 4:10	(10,4)	3 확정
6	4	더 이상 갱신 없음	0:0, 1:4, 2:8, 3:10, 4:10		4 확정, 종료

 

⏰ 다익스트라 알고리즘의 시간 복잡도를 계산해보면

procedure Dijkstra(G, s)

//모든 정점에 대해 초기화가 이루어지므로 O(V)
for all u ∈ V
	dist[u] = infinite
	prev[u] = NULL;
	
dist[s] = 0;

//우선 순위 큐 초기화 O(?): A
H = makequeue(V);

while(H is not empty)
	//최소값을 가져오는 연산은 V번 수행 - n * O(?): B
	u = get_min(H); 

	//모든 노드에 대하여 각각의 노드와 연결된 노드들에 대해 연산되므로 n * O(?) => m * O(?): C 
	for all edges (u, v) ∈ E 
		if(dist[v] > dist[v] + l(u,v))
			dist[v] = dist[u] + l(u,v);
			prev[v] = u;
			modify_H(H, v);

 

그래서 시간 복잡도는:

$$
O(A + B + C)
$$

 

🚧 성능은 그래프의 복잡도와 우선 순위 큐 구현 방식에 따라 달라진다.

A	n개의 원소를 큐에 삽입
B	큐에서 최소값을 찾아 제거
C	큐 갱신

	배열 기반 우선 순위 큐	트리 기반 우선 순위 큐
밀집 그래프 m = O(n^2)	A: O(n) B: O(n^2) C: O(m) = O(n^2) ⇒ O(n^2)	A: O(nlogn) B: O(nlogn) C: O(m) = O(n^2) ⇒ O(n^2)
희소 그래프 m = O(n)	A: O(n) B: O(n^2) C: O(m) = O(n) ⇒ O(n^2)	A: O(nlogn) B: O(nlogn) C: O(m) = O(n) ⇒ O(nlogn)

 

 

4. 플로이드-워셜 알고리즘 (Floyd-Washall Algorithm) 🌟

➡️ 그래프의 모든 정점이 연결된 쌍의 최단 거리(모든 쌍의 최단 거리)를 찾는 알고리즘
      - 음수 가중치를 가진 간선도 허용
      - 그러나 가중치가 음수인 순환 경로(사이클)은 비허용
      - 최단 거리를 저장한 행렬 출력 `G[u][v]: u -> v까지의 최단 거리`
      - 하나의 출발점에서 모든 정점까지의 최단 거리를 찾는 문제의 확장으로 생각 가능
         `for all vertices u: Dikstra(u)`

🔖 동적 프로그래밍 (Dynamic Programming; DP)
      1. 주어진 문제를 여러 개의 작은 문제로 분할한다.
      2. 작은 문제들의 합들 중 최적합을 주는 작은 문제들의 조합을 선택한다.

 

$$
A^k[i][j]
$$

위의 의미:

1. 정점 i에서 j까지 최단 거리 비용

2. k보다 작거나 같은 정점만 지나가는 경로

    [예] `i -> a -> b -> j`라면, `a,b <= k`이다.

 

✅ 전략: \(A^-1\)에서 시작하여 연속적으로 \(A^0, A^1, ..., A^n\)을 계산한다.
$$
A^k[i][j] = min \{ A^{k-1}[i][j], A^{k-1}[i][k] + A^{k-1}[k][j] \}
$$

[1] \(A^k[i][j]\): 정점 0, 1, ..., k 까지만 중간 경로로 허용했을 때, 정점 i에서 j로 가는 최단 거리
[2] \(A^{k-1}[i][j]\): 노드 k를 지나지 않고 정점 i에서 j로 가는 최단 거리
[3] \(A^{k-1}[i][k] + A^{k-1}[k][j]\): 노드 k를 반드시 거쳐서 정점 i에서 j로 가는 경로 
[2]와 [3] 중 더 짧은 거리가 [1]최단 거리가 된다.
min([2], [3])은 결국 "혹시 i→k→j로 돌아가는 게 더 짧지 않을까?" 를 검사하는 과정이다.

 

플로이드-워셜 알고리즘 구현

//cost: i > j로 가는 초기 비용(직접 연결된 간선의 가중치)
//dist: 최종 최단 거리 행렬
void Floyd (int cost[][], int dist[][], int n) {
	int i, j, k;
	
  	//cost를 dist 배열에 복사: 다른 정점을 방문하여 우회해서 가지 않고 직접 연결된 경로의 경우만 저장
	for(i=0; i<n; i++) {
		for(j=0; j<n; j++) {
			dist[i][j] = cost[i][j];
		}
	}
	
    //저장된 기존 비용과 k를 거쳐오는 경로의 비용을 비교하여 값 업데이트
	for(k=0; k<n; k++) {
		for(i=0; i<n; i++) {
			for(j=0; j<n; j++) {
				if(dist[i][k] + dist[k][j] < dist[i][j]) 
					dist[i][j] = dist[i][k] + dist[k][j];
			}
		}
	}
}

시간 복잡도는 \(On^3)\)이 된다.

 

플로이드-워셜 알고리즘 예시

https://www.geeksforgeeks.org/c/floyd-warshall-algorithm-in-c/

(1) 초기화: 직접 연결된 간선만 고려한 경우

A^-1	A	B	C	D	E
A	0	4	∞	5	∞
B	∞	0	1	∞	6
C	2	∞	0	3	∞
D	∞	∞	1	0	2
E	1	∞	∞	4	0

 

(2) 중간 노드로 A를 사용한 경우

$$
dist[i][j] = min(dist[i][j], dist[i][0] + dist[0][j])
$$

A^0	A	B	C	D	E
A	0	4	∞	5	∞
B	∞	0	1	∞	6
C	2	6	0	3	12
D	∞	∞	1	0	2
E	1	5	∞	4	0

 

(3) 중간 노드로 B를 사용한 경우

$$
dist[i][j] = min(dist[i][j], dist[i][1] + dist[1][j])
$$

A^1	A	B	C	D	E
A	0	4	5	5	10
B	∞	0	1	∞	6
C	2	6	0	3	12
D	∞	∞	1	0	2
E	1	5	6	4	0

 

(4) 중간 노드로 C를 사용한 경우

$$
dist[i][j] = min(dist[i][j], dist[i][2] + dist[2][j])
$$

A^2	A	B	C	D	E
A	0	4	5	5	10
B	3	0	1	4	6
C	2	6	0	3	12
D	3	7	1	0	2
E	1	5	6	4	0

 

(5) 중간 노드로 D를 사용한 경우

$$
dist[i][j] = min(dist[i][j], dist[i][3] + dist[3][j])
$$

A^3	A	B	C	D	E
A	0	4	5	5	7
B	3	0	1	4	6
C	2	6	0	3	5
D	3	7	1	0	2
E	1	5	5	4	0

 

(6) 중간 노드로 E를 사용한 경우

$$
dist[i][j] = min(dist[i][j], dist[i][4] + dist[4][j])
$$

A^4	A	B	C	D	E
A	0	4	5	5	7
B	3	0	1	4	6
C	2	6	0	3	5
D	3	7	1	0	2
E	1	5	5	4	0