그래프 기초 - union-find/위상정렬

그래프

개념 간의 연결 관계를 수학적 모델로 단순화하여 표현한 것

주요 용어

• 무향 간선 : 간선의 방향 존재 X
• 유향 간선 : 간선의 방향 존재
• 인접 : 정점 v1, v2에 대해 간선 존재 → 정점 v1과 v2는 인접
• 부속 : 정점 v1, v2에 대해 간선 e 존재 → 간선 e는 정점 v1과 v2에 부속
• 차수 : 정점에 부속된 간선의 수
  • in-degree : 정점에 들어오는 간선의 수
  • out-degree : 정점에서 나가는 간선의 수

서로소 집합 (Disjoint Set, Union-Find)

교집합이 공집합인 집합들의 정보를 확인(Find)하고, 조작(Union) 할 수 있는 자료구조

• Union
  어떤 두 원소 a, b에 대해 union(a,b)는 각 원소가 속한 집합을 하나로 합침
• Find
  어떤 원소 a에 대해 find(a)는 a가 속한 집합의 대표번호를 반환

구현

1. 초기화

vector<int> parent;

void initialize() {
	for(i : nums) {
		parent[i] = i;
	}
}

2. Union 연산

void union(int a, int b){
	aRoot = find(a);
	bRoot = find(b);
	
	if(aRoot != bRoot)
		parent[aRoot] = bRoot;
		// parent[bRoot] = aRoot;
}

3. Find 연산

int find(int a) {
	if(parent[a] == a) return a;
	else return parent[a] = find(parent[a]);
}

DAG (Directed Acyclic Graph)

순환을 가지지 않는 방향 그래프
일반적으로 우선순위를 가진 일련의 작업들은 DAG 구조를 가짐

위상정렬 (Topological Sort)

DAG(비순환 방향그래프)에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 것
각 정점을 우선순위에 따라 배치하는 것
일반적으로 위상정렬의 결과는 유일하지 않음

indegree가 0인 노드 찾아서 노드와 관련 간선 삭제 → 반복
indegree가 0인 노드가 여러개일때 먼저 작업하는 순서에 따라 결과가 여러개가 될 수 있음

구현

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n; // #node
vector<vector<int>> adjList;
vector<int> indegree; 

void topologicalSort() {
	queue<int> q;

	for (int i = 1; i <= n; i++) {
		if (!indegree[i]) q.push(i);
	}

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (int next : adjList[cur]) {
			indegree[next]--;

			if (indegree[next] == 0) q.push(next);
		}

		cout << cur << ' ';
	}
}

int main() {
	int m; //#edge
	cin >> n >> m;

	adjList.resize(n + 1);
	indegree.resize(n + 1, 0);

	while (m--) {
		int a, b;
		cin >> a >> b;

		adjList[a].push_back(b);
		indegree[b]++;
	}

	topologicalSort();

	return 0;
}