그래프의 비순환성 검사와 사이클 찾기를 $O(M)$에 수행하기¶
루프와 다중 간선이 없는 방향 그래프 또는 무방향 그래프를 생각해 봅시다. 이 그래프가 비순환인지 확인하고, 비순환이 아니라면 임의의 사이클 하나를 찾아야 합니다.
이 문제는 깊이 우선 탐색을 사용하여 $O(M)$에 해결할 수 있습니다. 여기서 $M$은 간선의 개수입니다. 고립된 정점은 절대 사이클 위에 있을 수 없으므로, 간선에 연결된 최대 $2M$개의 정점에서만 탐색을 시작하면 충분합니다. 아래 구현은 단순히 모든 정점을 순회하므로, 알고리즘 자체에는 필요하지 않은 $O(N)$ 항이 추가됩니다.
알고리즘¶
그래프에서 DFS를 여러 번 수행합니다. 처음에는 모든 정점이 흰색(0)으로 칠해져 있습니다. 방문하지 않은(흰색) 각 정점에서 DFS를 시작하여, 정점에 들어갈 때 회색(1)으로 표시하고 나올 때 검은색(2)으로 표시합니다. DFS가 회색 정점으로 이동하면 사이클을 찾은 것입니다(그래프가 무방향이라면 부모로 향하는 간선은 고려하지 않습니다). 사이클 자체는 부모 배열을 사용하여 복원할 수 있습니다.
구현¶
다음은 방향 그래프에 대한 구현입니다.
int n;
vector<vector<int>> adj;
vector<char> color;
vector<int> parent;
int cycle_start, cycle_end;
bool dfs(int v) {
color[v] = 1;
for (int u : adj[v]) {
if (color[u] == 0) {
parent[u] = v;
if (dfs(u))
return true;
} else if (color[u] == 1) {
cycle_end = v;
cycle_start = u;
return true;
}
}
color[v] = 2;
return false;
}
void find_cycle() {
color.assign(n, 0);
parent.assign(n, -1);
cycle_start = -1;
for (int v = 0; v < n; v++) {
if (color[v] == 0 && dfs(v))
break;
}
if (cycle_start == -1) {
cout << "Acyclic" << endl;
} else {
vector<int> cycle;
cycle.push_back(cycle_start);
for (int v = cycle_end; v != cycle_start; v = parent[v])
cycle.push_back(v);
cycle.push_back(cycle_start);
reverse(cycle.begin(), cycle.end());
cout << "Cycle found: ";
for (int v : cycle)
cout << v << " ";
cout << endl;
}
}
다음은 무방향 그래프에 대한 구현입니다. 무방향 버전에서는 정점 v가 검은색으로 칠해지면 DFS가 이 정점을 다시는 방문하지 않는다는 점에 유의하십시오. 이는 v를 처음 방문했을 때 v에 연결된 모든 간선을 이미 탐색했기 때문입니다. DFS가 사이클을 찾지 못한 채 v의 처리를 마쳤다면, (v와 그 부모 사이의 간선을 제거한 후) v를 포함하는 연결 요소는 반드시 트리입니다. 따라서 회색 상태와 검은색 상태를 구분할 필요조차 없습니다. 따라서 char 벡터 color를 불리언 벡터 visited로 바꿀 수 있습니다.
int n;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> parent;
int cycle_start, cycle_end;
bool dfs(int v, int par) { // passing vertex and its parent vertex
visited[v] = true;
for (int u : adj[v]) {
if(u == par) continue; // skipping edge to parent vertex
if (visited[u]) {
cycle_end = v;
cycle_start = u;
return true;
}
parent[u] = v;
if (dfs(u, parent[u]))
return true;
}
return false;
}
void find_cycle() {
visited.assign(n, false);
parent.assign(n, -1);
cycle_start = -1;
for (int v = 0; v < n; v++) {
if (!visited[v] && dfs(v, parent[v]))
break;
}
if (cycle_start == -1) {
cout << "Acyclic" << endl;
} else {
vector<int> cycle;
cycle.push_back(cycle_start);
for (int v = cycle_end; v != cycle_start; v = parent[v])
cycle.push_back(v);
cycle.push_back(cycle_start);
cout << "Cycle found: ";
for (int v : cycle)
cout << v << " ";
cout << endl;
}
}