방향 그래프에서 사이클 찾기

Cycle?

사이클은 모두 알다시피 그래프에서 시작과 끝이 같은 형태를 말한다. 그래프에서 사이클은 언제나 성가신 존재인데, 무한루프를 발생 시킬 수도 있고, 쓸 대 없이 몇 번 돌다가 나와서 성능이 안 좋아질 수도 있다.

이것은 현업에서도 골치이고 PS에도 자주 등장하는 문제이다. 이것을 어떻게 판별할 수 있을까

방향 그래프에서 싸이클 판별

• 방향 그래프에서 사이클을 판별할 수 있는 방법은 가장 익숙한 DFS 이다. dfs는 방향이 계속 같기 때문에 다음 노드를 판별하기 용이하기 때문이다.
• 그리고 방향 그래프에서의 사이클이란 Back Edge가 존재하는 것과 같다.
• 이제 문제는 Back Edge를 판별하는 것으로 바뀌게 된다.

void dfs(int NowNode) {
	visited[NowNode] = true;

	int nextNode = node[NowNode];

	if (visited[nextNode] == false) {
		visited[nextNode] = true;
		dfs(nextNode);
	}
	else {
		cout << "사이클 발견" << endl;
		return;
	}
}

• 위 코드처럼 쉽게 사이클을 판별할 수 있다.