[알고리즘/C++] 플로이드(Floyd) - 그래프 내에서 사이클 찾기

각 노드가 하나의 후속노드만을 갖는 그래프에서 사이클이 존재한다고 할 때, 

 

어느 노드에서 사이클이 시작되고, 그 사이클의 길이가 궁금할 수 있다. 

 

플로이드(Floyd) 알고리즘은 두 개의 포인터 정보를 이용해 사이클의 진입점인 노드를 찾을 수 있다. 

 

int floyd(vector<vector<pair<int, int>>> adj) {
	int start = 1;
	//1번째 노드 외에 다른 임의의 노드도 가능
	int oneStep = adj[start][0].first;
	//후속 노드
	int twoStep = adj[oneStep][0].first;
	//후속의 후속 노드
	while (oneStep != twoStep) {
		//서로 만날 때까지 후속 노드를 찾는다.
		oneStep = adj[oneStep][0].first;
		twoStep = adj[adj[twoStep][0].first][0].first;
	}
	oneStep = start;
	//한 포인터를 시작점으로 되돌린다.
	while (oneStep != twoStep) {
		oneStep = adj[oneStep][0].first;
		twoStep = adj[twoStep][0].first;
		//두 포인터가 서로 만날때까지 1보씩 이동한다.
	}
	return oneStep;
	//서로 만난 그 지점이 사이클의 시작 노드
}

플로이드 알고리즘의 전체 코드이다. 

	int start = 1;
	//1번째 노드 외에 다른 임의의 노드도 가능
	int oneStep = adj[start][0].first;
	//후속 노드
	int twoStep = adj[oneStep][0].first;
	//후속의 후속 노드

먼저 시작 노드(start)는 어떤 값으로 해도 상관없다. 임의의 값으로 지정해준다. 

 

두 개의 포인터 중 하나는 한 번에 1보씩만 이동한다. 나머지 하나의 포인터는 한 번에 2보씩 이동한다. 

 

	while (oneStep != twoStep) {
		//서로 만날 때까지 후속 노드를 찾는다.
		oneStep = adj[oneStep][0].first;
		twoStep = adj[adj[twoStep][0].first][0].first;
	}
    
    	oneStep = start;
	//한 포인터를 시작점으로 되돌린다.

두 개의 포인터가 서로 만날때까지 포인터의 이동 조건대로 계속 이동한다. 

 

서로 만나면 하나의 포인터를 시작 노드(start)로 다시 되돌린다. 

 

	while (oneStep != twoStep) {
		oneStep = adj[oneStep][0].first;
		twoStep = adj[twoStep][0].first;
		//두 포인터가 서로 만날때까지 1보씩 이동한다.
	}
	return oneStep;
	//서로 만난 그 지점이 사이클의 시작 노드

그리고 두 포인터를 다시 1보씩만 움직이게하여서 서로 만날 때까지 움직인다. 최초로 만난 그 지점이 사이클의 

 

진입점이 되는 노드이다. 

int calcCycleLen(vector<vector<pair<int, int>>> adj, int gateNode) {
	int next = adj[gateNode][0].first;
	//사이클의 첫 노드의 후속 노드
	int len = 1;
	while (next != gateNode) {
		next = adj[next][0].first;
		len++;
	}
	return len;
}

사이클의 길이를 알고싶다면 이 진입점이 되는 노드 정보를 통해서 길이를 계산할 수 있다. 

 

void makeCycleGraph(vector<vector<pair<int, int>>>& adj) {
	adj.push_back({ {0, 0} });
	//sentinel node
	adj.push_back({ {2, 1} });
	adj.push_back({ {3, 1} });
	adj.push_back({ {4, 1} });
	adj.push_back({ {5, 1} });
	adj.push_back({ {6, 1} });
	adj.push_back({ {7, 1} });
	adj.push_back({ {4, 1} });
}

사이클이 있는 경로가 하나인 그래프를 생성해주고 

	vector<vector<pair<int, int>>> adj;
	makeCycleGraph(adj);
	int gateNode = floyd(adj);
	int cycleLen = calcCycleLen(adj, gateNode);
	cout << gateNode << "\n";
    >> 결과: 4
	cout << cycleLen << "\n";
    >> 결과: 4

결과는 위와 같다.