[그래프 알고리즘]사이클 탐지

그래프에서의 사이클

한 노드에서 다른 노드들을 거쳐 처음 노드로 돌아올 수 있으면, 그 그래프에는 사이클이 존재한다고 합니다.

무향 그래프에서의 사이클 존재 여부 확인

1. DFS

DFS로 그래프를 순회하면서, 이미 방문한 노드로 이어지는 엣지가 있을 때,

그 무향그래프는 사이클이 존재합니다.

	#include <iostream>
	#include <vector>
	using namespace std;
	#define N_NODE 5
	vector<int> adjList[N_NODE];
	bool visited[N_NODE];
	bool cycleCheck(int here, int prev){
	// 이미 방문한적 있다면 사이클 존재
	if(visited[here]) return true;
	visited[here] = true;
	for(int there : adjList[here]){
	// 바로 직전 노드인 경우는 제외한다.
	if(there != prev && cycleCheck(there, here)) return true;
	}
	return false;
	}
	void addEdge(int u, int v){
	// 양방향 엣지
	adjList[u].push_back(v);
	adjList[v].push_back(u);
	}
	int main(){
	// 사이클 존재하는 그래프
	addEdge(0, 1);
	addEdge(1, 2);
	addEdge(1, 4);
	addEdge(3, 4);
	addEdge(2, 3);
	bool hasCycle = false;
	for(int i=0;i<N_NODE;i++){
	if(!visited[i] && cycleCheck(i, -1)) hasCycle = true;
	}
	cout << hasCycle;
	return 0;
	}

view raw cycle_check_undirect.cpp hosted with ❤ by GitHub

2. Disjoint Set(Union and Find)

한 엣지가 연결하는 두 노드를 하나의 그룹으로 묶어가는 방식으로도 사이클의 존재 여부를 확인할 수 있습니다.

처음에는 모든 노드들이 서로 다른 그룹에 속한 것으로 가정합니다.

모든 엣지들을 확인하며, 한 엣지가 연결하는 두 노드를 같은 그룹으로 묶습니다.

그러다가 어느 엣지가 연결하는 두 노드가 이미 같은 그룹에 속한 노드들이라면, 이미 이전에 확인한 다른 엣지들을 통해 두 노드가 연결될 수 있음을 의미하므로 사이클이 존재한다는 것을 알 수 있습니다.

이를 구현하기 위해 union and find 알고리즘을 이용합니다.

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	#define N_NODE 5
	struct Edge {
	int u, v;
	Edge(int u, int v): u(u), v(v) {}
	};
	vector<Edge> edges;
	void addEdge(int u, int v){
	edges.emplace_back(u, v);
	}
	vector<int> parent(N_NODE, 0);
	int find(int u){
	if(parent[u] == u) return u;
	return parent[u] = find(parent[u]);
	}
	void merge(int u, int v){
	int up = find(u);
	int vp = find(v);
	if(up != vp) parent[vp] = up;
	}
	bool cycleCheck() {
	for(auto e : edges) {
	// 이미 같은 그룹에 속해있으면 사이클이 존재한다.
	if(find(e.u) == find(e.v)) return true;
	// 두 노드를 같은 그룹으로 묶는다.
	merge(e.u, e.v);
	}
	return false;
	}
	int main(){
	// 모든 노드를 서로다른 그룹으로 초기화
	for(int i=0;i<N_NODE;i++) parent[i] = i;
	addEdge(0, 1);
	addEdge(1, 2);
	addEdge(1, 4);
	addEdge(3, 4);
	addEdge(2, 3);
	cout << cycleCheck();
	return 0;
	}

view raw cycle_check_undirect_union_and_find.cpp hosted with ❤ by GitHub

방향 그래프에서의 사이클 존재 여부 확인

방향 그래프에서는 back edge 의 존재 여부로 사이클이 존재하는지 확인할 수 있습니다.

back edge란 DFS로 그래프를 탐색 하다가, 아직 DFS 재귀 함수가 종료하지 않은 노드로 다시 방문을 하게 될때,

그 엣지를 back edge라고 합니다.

노드 1, 2, 3이 1->2->3 처럼 연결되어 있고, 1번 노드부터 DFS 를 한다고 할 때,

DFS 함수의 호출 순서는 1, 2, 3이고, 종료 순서는 3, 2, 1입니다.

근데 만약 노드 2번에서 DFS 함수가 종료하기 전에 방문 된다면, 이는 2번 노드에 연결된 엣지를 통해 다시 2번으로 올 수 있음을 의미하므로, 사이클이 존재한다고 할 수 있습니다.

DFS로 순회하면서, 노드들의 방문순서와 DFS 함수 종료 여부를 기록합니다.

이미 이전에 방문한 적이 있고, DFS 함수가 종료되지 않은 노드를 다시 방문한다면 사이클이 존재합니다.

	#include <iostream>
	#include <vector>
	using namespace std;
	#define N_NODE 5
	int cnt = 0;
	vector<int> adjList[N_NODE];
	vector<int> visitOrder(N_NODE, 100);
	vector<bool> finished(N_NODE, false);
	void addEdge(int u, int v){
	adjList[u].push_back(v);
	}
	bool cycleCheck(int here) {
	// here 의 방문한 순서를 기록한다.
	visitOrder[here] = cnt;
	cnt++;
	for(int there : adjList[here]){
	// 이미 이전에 방문 했고, 재귀가 끝나지 않았으면 back edge다. -> 사이클 존재
	if(visitOrder[there] < visitOrder[here] && !finished[there]) return true;
	// 이후에 사이클이 존재한다면 true 리턴
	if(cycleCheck(there)) return true;
	}
	// here 에서의 재귀가 끝났음을 표시
	finished[here] = true;
	// 사이클이 없으므로 false 리턴
	return false;
	}
	int main(){
	addEdge(0, 1);
	addEdge(1, 2);
	addEdge(1, 4);
	addEdge(4, 3);
	addEdge(3, 1);
	bool ret = false;
	for(int i=0;i<N_NODE;i++) {
	if(visitOrder[i] == 100 && cycleCheck(i)) ret = true;
	}
	cout << ret;
	return 0;
	}

view raw cycle_check_back_edge.cpp hosted with ❤ by GitHub