그래프에서 연결 요소 찾기¶
$n$개의 노드와 $m$개의 간선을 가진 무방향 그래프 $G$가 주어집니다. 이 그래프에서 모든 연결 요소, 즉 한 그룹 안에서는 각 정점이 다른 정점에서 도달 가능하고 서로 다른 그룹 사이에는 경로가 존재하지 않는 여러 개의 정점 그룹을 찾아야 합니다.
문제를 해결하는 알고리즘¶
-
이 문제를 해결하기 위해 깊이 우선 탐색이나 너비 우선 탐색을 사용할 수 있습니다.
-
실제로는 DFS를 여러 차례 연속으로 수행하게 됩니다. 첫 번째 차례는 첫 번째 노드에서 시작하며, 첫 번째 연결 요소에 속한 모든 노드를 순회(발견)합니다. 그다음 남은 노드 중 방문하지 않은 첫 번째 노드를 찾아 그 노드에서 깊이 우선 탐색을 수행하여 두 번째 연결 요소를 찾습니다. 모든 노드를 방문할 때까지 이 과정을 반복합니다.
-
이 알고리즘의 전체 점근적 실행 시간은 $O(n + m)$입니다. 실제로 이 알고리즘은 같은 정점에서 두 번 실행되지 않으므로, 각 간선은 정확히 두 번(한쪽 끝에서 한 번, 다른 쪽 끝에서 한 번) 확인됩니다.
구현¶
int n;
vector<vector<int>> adj;
vector<bool> used;
vector<int> comp;
void dfs(int v) {
used[v] = true;
comp.push_back(v);
for (int u : adj[v]) {
if (!used[u])
dfs(u);
}
}
void find_comps() {
used.assign(n, false);
for (int v = 0; v < n; ++v) {
if (!used[v]) {
comp.clear();
dfs(v);
cout << "Component:" ;
for (int u : comp)
cout << ' ' << u;
cout << endl ;
}
}
}
-
사용되는 가장 중요한 함수는 그래프의 연결 요소를 찾아 출력하는
find_comps()입니다. -
그래프는 인접 리스트 형태로 저장됩니다. 즉,
adj[v]에는 정점v에서 간선이 이어지는 정점들의 목록이 들어 있습니다. -
벡터
comp에는 현재 연결 요소에 속한 노드들의 목록이 들어 있습니다.
코드의 반복적 구현¶
깊은 재귀 함수는 일반적으로 좋지 않습니다. 재귀 호출 하나하나가 스택 메모리를 조금씩 필요로 하며, 기본적으로 프로그램이 사용할 수 있는 스택 공간은 제한되어 있습니다. 따라서 노드가 수백만 개인 연결 그래프에서 재귀적인 DFS를 수행하면 스택 오버플로가 발생할 수 있습니다.
스택 자료 구조를 직접 관리하면 재귀 프로그램을 언제나 반복적 프로그램으로 바꿀 수 있습니다. 이 자료 구조는 힙에 할당되므로 스택 오버플로가 발생하지 않습니다.
int n;
vector<vector<int>> adj;
vector<bool> used;
vector<int> comp;
void dfs(int v) {
stack<int> st;
st.push(v);
while (!st.empty()) {
int curr = st.top();
st.pop();
if (!used[curr]) {
used[curr] = true;
comp.push_back(curr);
for (int i = adj[curr].size() - 1; i >= 0; i--) {
st.push(adj[curr][i]);
}
}
}
}
void find_comps() {
used.assign(n, false);
for (int v = 0; v < n ; ++v) {
if (!used[v]) {
comp.clear();
dfs(v);
cout << "Component:" ;
for (int u : comp)
cout << ' ' << u;
cout << endl ;
}
}
}