[알고리즘] 강한 결합 요소 (SCC)

치치·2025년 2월 5일

알고리즘

알고리즘C++

목록 보기

23/24

강한 결합 요소

그래프 안에서 강하게 결합된 정점의 집합을 의미한다 (Strongly Connected Component)
같은 SCC에 속하는 정점은 서로 도달이 가능하다 (강하게 연결되었다)
방향그래프일때 의미가 있다
-> 무방향 그래프는 양방향으로 되어있기에 그래프 전체가 모두 SCC이다 (SCC사용x)
-> 무방향 그래프에서는 모든 정점이 연결된 부분 그래프는 단순히 '연결된 구성 요소'라고 칭함

즉, 사이클이 발생하는 경우는 무조건 SCC에 해당한다

예를 들어, 아래의 방향 그래프에서 SCC를 찾아보자면,

이렇게 나타낼 수 있다

각 집합의 정점끼리는 서로에게 도달할 수 있다
-> 정점1은 사이클을 돈 뒤, 다시 1로 도달할 수 있다
-> 정점4는 사이클을 형성하진 않지만, 다른 정점들과 도달할 수 없기 때문에 자기 자신을 포함한 독립적인 SCC이다

타잔 알고리즘

모든 정점에 대해 DFS를 수행하여 SCC를 찾는 방식의 알고리즘이다 (Tarjan's)

코드를 보면서 자세히 살펴보자

우선 DFS(깊이 우선 탐색)을 사용하려면

해당 노드에 방문 했는지
재귀함수를 사용하여 깊이 들어가기
이 집합이 SCC인지
위상정렬 방식도 사용되는 거 같다

전체적인 과정

전체 과정에서 계속 부모배열안에 들어있는 id값이 처음에 방문하여 배정받고 난 뒤, 해당 값은 임시변수 minNum에 넣어두고, 재귀를 돌리면서 그 값들을 비교해나간다
재귀함수가 종료되면서 minNum의 값이 가장 작은 값으로 바뀌면서 최종적으로 사이클이 돌고있는 집합내의 minNum이 가장 최소의 값으로 통일된다

-> 유니온 파인드와 비슷한 느낌인 줄 알고 부모배열의 값도 바뀌면서 같은 집합에 속하는 줄 알았는데 아니었다 !!!!
-> 그냥 minNum의 값만 변하고 minNum의 값을 비교하여 판단한 것!!!!
-> 부모배열과 id는 단순히 방문여부와, 그 순서대로 id값을 넣어준 것!!!!

1. Search(1) 함수 시작

정점을 탐색한다 -> 가장 처음 탐색한 노드의 id가 가장 작은 값
스택에 해당 정점 넣어주기
minNum임시 변수에 현재 id값 넣어주기(부모배열의 값)
-> 현재 minNum의 값 : 1
-> 노드의 집합에서 가장 작은 값을 저장해두기 위한 용도(사이클 확인용)

아래의 그림에서 노드1을 방문하고 id : 1로 배정하였다. 노드1과 인접한 노드2의 id = 0 으로 아직 배정받지 않은 상태
즉, 아직 방문 하지 않은 상태

노드2를 방문하지 않았다면 minNum의 값을 현재 minNum과 노드2의 minNum을 비교하여 더 최소값으로 갱신해야한다

2. Search(2) 재귀함수 시작

정점2를 방문한뒤, id : 2배정 해주고 스택에 해당 정점을 넣어둔다
minNum의 값을 방문한 노드의 id값 넣어주기(부모배열의 값)
-> 현재 minNum의 값 : 2

아래의 그림에서 정점2와 인접한 노드3의 id는 아직 배정받지 않은 상태
-> 즉, 아직 방문하지 않은 상태

정점3을 방문하여 해당 정점의 minNum과 현재 minNum을 비교하여 갱신해주어야한다

3. Search(3) 재귀함수 시작

정점3을 방문한뒤, id : 3을 배정해주고 스택에 해당 정점을 넣어둔다
현재 minNum의 값 : 3

정점3과 인접한 정점은1인데 이미 방문되어있는 노드임
-> 다른 조건문으로 들어가서 minNum = parent[next] 수행

현재 minNum의 값이 3이었는데 다음 노드의 부모배열값으로 바꿔주는 것
Search(3)의 minNum = 1이고 반환

4. 재귀함수 종료 & minNum값 반환

Search(3), Search(2)가 종료되고, Search(1)에서 minNum 의 값이 부모배열의 값과 같아졌다
-> 시작점으로 되돌아왔다는 뜻 (사이클)
-> SCC가 맞기 때문에 미리 생성해둔 2차원 벡터배열에 해당 정점들 저장

5. SCC 저장

스택에 있는 값들을 top부터 하나씩 벡터에 저장하고, 스택이 모두 비었으면 break해서 반복문 종료
vector<int> clone;안에 해당 SCC 정점들을 저장해두고, 이 집합을 vector<vector<int>> scc; 벡터타입을 받는 이차원 벡터에 저장한다
-> 2차원 벡터는 행과 열을 가진다

-> ex)
{1,2,3},
{4},
{5,6,7}

코드 나눠서 보기

변수와 배열 생성

SCC인지 확인하기 위한 bool 배열
SCC를 저장하기 위한 2차원 벡터 (정점의 집합의 모음을 저장할 배열이기 때문)
그래프 벡터배열 (앞에서 배웠다 - 노드를 서로 연결하기 위한)
방문 & id를 확인하기 위한 부모 배열
정점을 넣어둘 stack

생성자에서 배열의 값을 초기화
Insert() 함수를 사용하여 그래프의 노드들을 서로 연결시켜주기
Search(int start) 함수

해당 그래프안에 SCC가 몇개 있는지 찾기 위한 함수

현재 부모배열의 값은 모두 0으로 초기화 되어있고, 해당 노드에 방문하면 id값을 부여하여 부모배열의 값을 id로 바꿔준다 (방문했다는 의미로 칭함)
스택에 현재 값을 넣어준다
임시변수 x에 id값을 넣어준다 (맨처음에 들어온 id값이 가장 작은 값임 - 재귀종료될때 이 값으로 갱신된다)
해당 정점과 인접한 노드 중 방문하지 않은 노드라면 현재의 x값을 다음 노드와 비교하여 더 작은 값으로 갱신해준다
-> 재귀 호출
-> 더 작은 값을 반환하는 함수인 min(x, y)
만약 다음 정점이 이미 방문 했던 노드이고(id부여된 상태), 아직 SCC가 체크된 상태가 아니라면 x의 값을 다음 노드의 값으로 갱신시킨다
-> 갱신 시킨 이 값이 가장 최소의 값
아래의 조건문들은 만족하지 않기 때문에 return x하고 재귀함수 종료

재귀가 다 종료되고 원래 있던 가장 작은 값으로 돌아오게 된다

현재 x값이 저장되있던 id값과 동일하다면 SCC가 맞기 때문에 1차원 벡터에 값을 저장한다
스택의 가장 위에 있는 값을 top변수에 저장하고 스택에서 값을 뺀다
1차원 벡터에 top변수에 저장한 값을 넣고, SCC체크를 한다
스택이 다 비었으면 반복문을 종료하고 2차원벡터배열인 scc에 값을 삽입한다
-> 만약 가장위의 값이 1이면 top변수에 1을 저장해두고 스택에서 뺀다
-> 그리고 정점SCC체크를 하고 저장된 top변수(1)와 start값(1)이 같기 때문에 종료된다
모든 로직을 다 수행했으니 함수 종료

부모배열에 접근하기 위한 연산자 오버로딩
-> parent배열은 private에 정의되어 있기 때문에 클래스의 객체를 만들어도 바로 접근이 불가하다
-> 부모 배열의 값을 반환해주는 사용자 정의 연산자 오버로딩이 필요한 것
SCC가 저장되어 있는 2차원 벡터의 크기를 반환해주는 Count함수
-> 반환된 size 값은 SCC의 갯수를 의미한다
SCC에 저장된 집합의 모음을 출력하기 위한 Show()함수
메인함수에서 그래프 객체를 생성하고, 각 노드를 방향그래프로 연결한다
반복문과 조건문을 사용해서 부모배열이 방문되지 않은 노드라면 Search()실행

Search함수를 한번만 실행하면 그 시작 노드와 연결된 사이클을 가진 노드들, SCC 한개만 찾는다
위의 예시 그림에서 Search(1)을 실행하면 사이클을 형성하는 노드 {1, 2, 3} 집합만 찾는다
-> 함수 내에서 모든 로직이 끝났기 때문이다. (재귀도 끝났으니 그럼)
만약, 그래프 내의 모든 SCC를 찾기 위해서는 방문되지 않은 노드들을 쭉 탐색하기 위해 메인함수에서 반복문을 사용하여 접근해야한다

타잔 알고리즘 전체코드

#include <iostream>
#include <vector>
#include <stack>
#define SIZE 12

using namespace std;

class Graph
{
private:

	bool finished[SIZE]; // 방문 배열
	
	vector<vector<int>> scc; // scc저장 2차원벡터

	vector<int> graph[SIZE]; // 그래프

	int parent[SIZE]; // 부모 배열
	
	stack<int> stack;
	
	int id; 
public:
	Graph()
	{
		id = 0;

		for (int i = 0; i < SIZE; i++)
		{
			finished[i] = false;
			parent[i] = 0;
		}
	}

	void Insert(int vertex, int edge)
	{
		graph[vertex].push_back(edge);
	}

	int Search(int start)
	{
		parent[start] = ++id; // 노드마다 고유한 번호

		stack.push(start); // stack에 자기 자신을 삽입합니다.

		int x = parent[start];


		for (int i = 0; i < graph[start].size(); i++)
		{
			int next = graph[start][i];
			
			if (parent[next] == 0) // 방문하지 않은 이웃 노드
			{ 
				x = min(x, Search(next));
			}

			else if (!finished[next]) // 처리중인 이웃 노드
			{
				x = min(x, parent[next]);
			}
		}

		if (x == parent[start]) // 부모 노드가 자기 자신인 경우
		{
			vector <int> clone;

			while (1)
			{
				int top = stack.top();

				stack.pop();

				clone.push_back(top);

				finished[top] = true;

				if (top == start)
				{
					break;
				}
			}

			scc.push_back(clone);
		}

		return x;
	}

	const int & operator [] (int index)
	{
		return parent[index];
	}

	const int & Count()
	{
		return scc.size();
	}

	void Show()
	{
		for (int i = 0; i < scc.size(); i++)
		{
			for (int j = 0; j < scc[i].size(); j++)
			{
				cout << scc[i][j] << " ";
			}
			cout << endl;
		}
	}
};


int main()
{
#pragma region 강한 결합 요소
	// 유향 그래프에서 모든 정점이 모든 다른 정점에 대해
	// 도달 가능한 경우, 그래프는 강하게 연결되었다는 그래프입니다.

	Graph graph;

	graph.Insert(1, 2);
	graph.Insert(2, 3);
	graph.Insert(3, 1);

	graph.Insert(4, 2);
	graph.Insert(4, 5);

	graph.Insert(5, 7);
	graph.Insert(6, 5);
	graph.Insert(7, 6);

	graph.Insert(8, 5);
	graph.Insert(8, 9);

	graph.Insert(9, 10);
	graph.Insert(10, 11);

	graph.Insert(11, 3);
	graph.Insert(11, 8);
	
	for (int i = 1; i < SIZE; i++)
	{
		if (graph[i] == 0)
		{
			graph.Search(i);
		}
	}

	cout << "SCC의 갯수 : " << graph.Count() << endl << endl;
	graph.Show();

#pragma endregion

	return 0;
}