BFS: 두 판 사이의 차이
(차이 없음)
| |
2025년 10월 16일 (목) 05:08 판
상위 문서: 알고리즘 설계와 분석
개요
BFS(Breadth-First Traversal) 알고리즘의 핵심은 그래프를 체계적으로(순서 있게) 탐색하는 것이다. BFS는 모든 vertex와 edge를 한 번씩 방문한다. 이는 아래와 같은 규칙을 따른다.
- “Breadth-First”는 탐색 시 가까운 노드(이웃)를 먼저 방문하고, 그 후에 더 멀리 있는 노드를 탐색하는 방식이다.
- 예를 들어, 루트 노드로부터 거리 1인 정점들을 모두 방문한 뒤, 그 다음으로 거리가 2인 정점, 3인 정점...을 방문하는 방식이다.
- BFS는 queue(큐)를 이용해 이 순서를 보장한다.
이에 따라 BFS는 특히 unweighted 그래프에서 최단 경로(shortest path)를 찾는 데 적합하다. 이는 DFS(깊이 우선 탐색)와 달리, BFS는 각 vertex까지의 최단 거리(간선 개수 기준)를 자연스럽게 구할 수 있기 때문이다.
Implementing BFS
Data Structures for BFS
BFS를 구현하기 위해 필요한 자료구조는 3가지이다:
bool processed[MAXV+1]; // 이미 완전히 처리된 정점
bool discovered[MAXV+1]; // 방문은 했지만 아직 다 보지 않은 정점
int parent[MAXV+1]; // 해당 정점을 방문하기 전의 부모 노드
또한 BFS는 FIFO queue를 이용하므로, 먼저 발견된 노드를 먼저 처리해야 “너비 우선” 순서가 유지된다. 이때 새로운 정점이 발견되면 discovered[y] = true로 표시하고 큐에 추가한다. 즉, queue는 처리할 정점들이 저장되는 to-do list와 같은 존재이다.
BFS Code
아래는 탐색을 시작하기 전에 배열을 초기화하는 함수이다.
void bfs(graph *g, int start) {
queue q; /* 방문할 정점들을 담는 큐 */
int v; /* 현재 방문 중인 정점 */
int y; /* 인접(후속) 정점 */
edgenode *p; /* 인접 리스트를 순회하기 위한 포인터 */
/* 초기화 단계 */
init_queue(&q); // 큐 초기화
enqueue(&q, start); // 시작 정점을 큐에 넣기
discovered[start] = true; // 시작 정점을 "발견됨"으로 표시
/* BFS 메인 루프 */
while (!empty_queue(&q)) {
v = dequeue(&q); // 큐에서 정점을 하나 꺼냄
process_vertex_early(v); // 방문 직후 처리 (예: 출력)
processed[v] = true; // 완전히 처리된 정점으로 표시
/* 인접 정점 순회 */
p = g->edges[v]; // v의 인접 리스트의 첫 노드
while (p != NULL) {
y = p->y; // 인접 정점 번호
/* 간선 (v, y) 처리 */
if ((!processed[y]) || g->directed) {
process_edge(v, y); // 간선 처리 (예: 출력, 트리 생성 등)
}
/* 새로운 정점 발견 시 */
if (!discovered[y]) {
enqueue(&q, y); // 큐에 추가
discovered[y] = true; // 발견됨 표시
parent[y] = v; // BFS 트리 상의 부모 설정
}
p = p->next; // 다음 인접 정점으로 이동
}
process_vertex_late(v); // 정점 처리 완료 후 작업
}
}
Exploiting Traversal
BFS 알고리즘은 그래프의 각 정점과 간선을 정확히 한번씩 방문하며, 이때 훅(hook) 함수들을 끼워 넣으면, 원하는 일을 자동으로 수행할 수 있다. 위에서 정의된 BFS() 함수에서의:
- process_vertex_early(int v): 정점 v를 꺼냈을 때 (BFS면 큐에서 dequeue 직후) 가장 먼저 호출
- 정점 방문 순서 출력, 레벨(거리) 기록, 통계 수집, 색칠 등의 작업을 실행
- process_edge(int x, int y): 정점 x의 인접리스트를 훑는 각 간선 (x, y)를 만날 때마다 호출
- 간선 방문 순서 출력, 선 개수 세기, 사이클 탐지 등을 함
이때 방문 순서를 출력할 경우 각 정점, 간선들은 정확히 한번 씩 출력되므로, 해당 함수들을 단순히 printf로 채우면 방문된 모든 정점과 간선이 중복 없이 출력된다. 하지만 undirected 그래프에서는 간선 (u, v)가 (v, u)와 같이 해석될 수 있으므로 “간선을 한 번만” 처리하려면 보통
if (!processed[y] || g->directed) process_edge(x, y);
와 같은 제약을 사용한다. 이는 위의 BFS() 함수 구현에서도 구현되어 있다.
Finding Paths
BFS는 정점을 처음 발견했을 때 “누가 이 정점을 발견했는지”를 parent[] 배열에 기록한다:
- parent[i] = 정점 i를 처음 큐에 넣게 만든 “직전의” 정점(발견자).
- 시작 정점 s는 보통 parent[s] = -1로 표시함.
- 모든 parent 화살표를 모으면, 시작 정점을 루트 노드로 하는 “발견 트리(discovery tree)”가 생김
- 이 트리는 탐색 순서를 보존함. 즉, 어떤 정점이 어떤 정점을 통해 처음 도달되었는지를 담고 있어, 경로 복원 등에 사용됨.
아래는 parent[]를 이용해 끝점에서 시작점으로 거꾸로 따라가면서 경로를 복원하는 함수이다:
void find_path(int start, int end, int parents[]) {
if ((start == end) || (end == -1)) { //루트 노드에 도달
printf("\n%d", start);
} else {
find_path(start, parents[end], parents); //end의 부모 쪽으로 한 칸 올라가서 해당 경로 출력
printf(" %d", end);
}
}
Shortest Paths and BFS
BFS는 간선 가중치가 모두 동일할 때, 시작 정점으로부터의 최단(간선 수 최소) 경로를 자동으로 보장한다. 이는 BFS가 레이어 순서대로 확장하기 때문이다. 거리 0(시작) → 거리 1 → 거리 2 → … 순서로 큐에서 꺼내 처리하기 때문에, 발견 트리에서 루트 내의 임의의 정점 x 로 내려가는 유일한 트리 경로는, 가능한 경로 중 간선 수가 최소이다. 이는 figure에서 알 수 있듯이 어떤 그래프가 주어졌을 때 parent[] 배열을 이용하여 발견 트리를 구성할 수 있으며, 이때 발견 트리의 어떤 정점에 대한 깊이는 루트에서의 해당 정점까지의 경로의 길이에 비례하기 때문이다.
Applications of BFS
BFS 알고리즘은 그 특성 덕분에 단순한 탐색을 넘어 더 다양한 분야에 사용된다.
Connected components
Connected components는 undirected 그래프를 여러 조각으로 나눈 것으로, 같은 조각 안의 임의의 두 정점 사이에는 경로가 있고, 서로 다른 조각 사이에는 경로가 없다. 이때 어떤 그래프가 주어졌을 때, 해당 그래프 내의 모든 조각들을 찾아내는 문제에 대해 BFS는 좋은 해결책이 된다. 이는 임의의 시작점에서 BFS를 한 번 돌리면 그 시작점과 같은 연결 요소에 있는 모든 정점이 발견되기 때문이다. 또한 아직 안 발견된 정점이 남아 있으면, 거기서 다시 BFS를 시작해 다음 연결 요소를 찾아서 문제를 해결할 수 있다. 이는 이를 구현하는 코드이다:
void connected_components(graph *g) {
int c = 0; // 조각의 숫자를 계산하는 카운터
int i;
initialize_search(g); // discovered[], processed[], parent[] 등 초기화
/* 그래프의 모든 정점을 순회 */
for (i = 1; i <= g->nvertices; i++) {
if (!discovered[i]) { // 아직 방문되지 않은 정점이라면
c++; // 새로운 연결 요소 발견 → 카운터 증가
printf("Component %d:", c); // 몇 번째 조각인지 출력
bfs(g, i); // 해당 정점부터 BFS 탐색 수행
printf("\n"); // 한 컴포넌트 출력 후 줄바꿈
}
}
}
void process_vertex_early(int v) {
printf(" %d", v);
}
void process_edge(int x, int y) {}
Two-Coloring Graphs
Two-Coloring Graphs 문제는 인접한 두 정점이 같은 색이 되지 않도록 색을 배정하는 문제이다. 또한 단 두 색으로도 충돌 없이 색칠 가능한 그래프를 이분 그래프(bipartite)라고 한다. 이는 아래와 같은 코드를 통해 해결할 수 있다:
void twocolor(graph *g) {
int i;
/* 모든 정점을 미색칠 상태로 초기화 */
for (i = 1; i <= g->nvertices; i++) {
color[i] = UNCOLORED;
}
bipartite = true; // 이분 그래프라고 가정하고 시작
initialize_search(g); // BFS용 초기화 (discovered, processed 등)
/* 모든 정점에 대해 BFS 수행 (연결되지 않은 그래프 대비) */
for (i = 1; i <= g->nvertices; i++) {
if (!discovered[i]) { // 아직 방문하지 않은 정점이라면
color[i] = WHITE; // 시작 색은 WHITE로 설정
bfs(g, i); // BFS 탐색 시작
}
}
}
void process_edge(int x, int y) {
if (color[x] == color[y]) { // 같은 색이면 이분 그래프 아님
bipartite = false;
printf("Warning: not bipartite, due to (%d,%d)\n", x, y);
}
color[y] = complement(color[x]); // y를 x의 반대 색으로 칠하기
}
int complement(int color) { //현재 색의 반대색 반환 함수
if (color == WHITE) {
return BLACK;
} else if (color == BLACK) {
return WHITE;
} else return UNCOLORED;
}
