그래프 사이클 판별

DFS의 장점 중 하나는 각 노드를 순회하면서 다양한 정보를 남길 수 있다는 것이다. 이를 활용해서 그래프의 사이클이 생겼을 때 이를 감지하는 기능을 구현할 수 있다. 이 기능은 DeadLock 즉, 교착상태를 확인할 때 매우 유용하다. DeadLock에 대한 설명은 생략하고 이 사이클을 판별하는 조건에 대해서 알아보도록 하자.

사이클이 생긴다고 하는 상황을 판별하기 위해서는 총 3가지 단계를 거쳐야 한다.

1. 순방향 간선인가? ( 이 경우 사이클이 생길 수 없음 )
2. 순방향 간선이 아니라면 교차 간선인가? ( 교차 간선일 경우 사이클이 아님 )
3. 그렇다면 역방향 간선이고 이 경우 무조건 사이클이 생겼다고 할 수 있다.

순방향 간선

순방향 간선이란 위 그림과 같이 한 방향으로 쭉 흘러가는 경우 이다. 0을 기준으로 순회 하면 0 -> 1 -> 3 -> 2가 될거고 이 경우 사이클이 생길 수 없다.

교차 간선

교차 간선이란 이미 특정 노드를 기준으로 탐색이 완료되었고, 다른 노드를 기준으로 순회를 시작했을 때 방문한 곳을 탐색한 경우이다. 즉 이미 0번을 기준으로 순회 하여 2번은 탐색이 된 상황인데 4번을 기준으로 한번 더 순회를 했을 때 2번으로 들어오게 된 경우가 교차 간선에 해당한다.

역방향 간선

이제 다음과 같은 그림처럼 처음 0번을 기준으로 순회한다고 했을 때 순방향, 교차 간선이 아니니 역방향 간선에 해당하여 사이클이 발생했다고 판단할 수 있다. DFS에서 해당 조건만 추가해주면 사이클을 판별할 수 있다.

#include <iostream>
using namespace std;
#define endl "\n"

#include <map>
#include <unordered_map>
#include <set>
#include <vector>

vector<vector<int>>			_vec;
map<int, set<int>>			_history;
vector<int>					_visitedOrder;
int							_visitedCount;
vector<bool>				_finished;
vector<int>					_parent;

void DFS(int here)
{
	// 이미 방문한 곳이면 pass
	if (_visitedOrder[here] != -1)
		return;

	// 몇 번째로 방문한 곳인지를 기입
	cout << here << "는(은) " << _visitedCount + 1 << "번째" << endl;
	_visitedOrder[here] = _visitedCount++;

	auto findIt = _history.find(here);
	if (findIt == _history.end())
	{
		// 연결된 노드들이 없다.
		_finished[here] = true;
		return;
	}

	// 연결된 노드가 있다.
	set<int>& next = findIt->second;
	for (int there : next)
	{
		if (_visitedOrder[there] == -1)
		{
			// 연결된 노드를 아직 방문한 적이 없다
			// 연결된 노드의 부모를 현재 위치로 설정 (추적용)
			_parent[there] = here;
			DFS(there);
			continue;
		}

		// 순방향 간선인 상황 (방문 순번으로 판단)
		if (_visitedOrder[here] < _visitedOrder[there])
			continue;

		// 역방향 간선
		if (_finished[there] == false) 
		{
			// DFS가 아직 끝나지 않은 상황 
			// 만약 _finished[there]이 true라면 교차간선임
			cout << "Cycle Detected!!" << endl;
			cout << here << " -> " << there << endl;

			int now = here;
			while (now != there)
			{
				// 부모를 추적해서 어떻게 사이클이 형성되었는지 출력
				cout << _parent[now] << " -> " << now << endl;
				now = _parent[now];
			}
		}
	}
	_finished[here] = true;
}

void Push(int node, int edge)
{
	_vec[node].push_back(edge);
	set<int>& history = _history[node];
	history.insert(edge);
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	_visitedOrder = vector<int>(5, -1);
	_visitedCount = 0;
	_finished = vector<bool>(5, false);
	_parent = vector<int>(5, -1);

	_vec.resize(5);
	Push(0, 1);
	Push(0, 2);
	Push(1, 3);
	Push(3, 0);
	Push(4, 2);

	DFS(0);
}

 

데이터는 위의 그림과 같이 그래프가 형성되도록 하였고, 0번 기준으로 순회를 했을 때 사이클을 잘 발견한다는 것을 확인할 수 있다.