기초 Graph 알고리즘

41 분 소요

Disjoint Set

DFS 랑 Union Find 가 자주 쓰임.

뭐가 더 나을까
DFS 가 더 빠르지만 Graph가 동적으로 변하는 상황에선 Union Find 가 나음.
Directed Graph 에서는 Union Find 를 쓸 수 없음.
Cycle 탐지도 가능하지만, 가장 짧은 Cycle 탐지 는 불가능함.

DFS

코드

vector<int> lines[MAX_IN];
bool stTB[MAX_IN]; bool edTB[MAX_IN];

void DFS(int cur)
{
	stTB[cur] = true;

	for (auto l : lines[cur])
	{
		if (!stTB[l])      // 방문한 노드가 아닐 때만 DFS() 를 함
			DFS(l);
		else if (!edTB[l]) // 현재 노드에서 탐색이 안끝났는데 돌아왔다면 Cyle
			;// detect
	}
	
	edTB[cur] = true;      // 현재 노드에서의 탐색 완료
}

설명

O(\(N\)) 에 끝나며 정적인 그래프에서 사용가능하다.

DFS 에서 Edge 는 4가지 종류가 있다.

DFS Search Tree 구성을 위해 사용된 Edge,
Backward Edge : DFS Search Tree 상에서 Parent Node 로 향하는 Edge
Forward Edge : DFS Search Tree 상에서 Child Node 로 향하는 Edge
Cross Edge : 서로 다른 DFS Search Tree 를 연결하거나 Parent/Child 가 아닌 Node 간을 연결하는 Edge

Backward Edge 가 있으면 Cycle 이 있으며 그 역도 성립한다.

stTB[] == true && edTB[] == false 의 조건이 바로 그것
가장 짧은 Cycle 을 탐색하는건 보장되지 않는다. Forward Edge 를 거쳐서 Backward Edge 를 지날 가능성이 있으나 이 경우는 탐색하지 않기 때문이다.

DFS 를 단순히 Visit 체크로 구현하는 경우도 있다.

Birected Graph 의 경우는 방문체크로도 Cycle 을 찾아낼 수 있다.
Directed Graph 인 경우는 Visit 된 노드가 꼭 Cycle 을 보장하지 않는다.

Union Find

코드

int rootTB[MAX_IN], rankTB[MAX_IN];
void Init(int n)
{
	for(int i = 0; i <=n; i++) rootTB[i] = i;
	fill(rankTB, rankTB+n+1, 0);
}

int Find(int a)
{
	if (rootTB[a] == a) return a;
	return rootTB[a] = Find(rootTB[a]);
}

bool Union(int from, int to)
{
	from = Find(from);
	to = Find(to);
	if (from == to) return false;
	if(rankTB[to] < rankTB[from]) swap(from, to);
	if(rankTB[to] == rankTB[from]) rankTB[to]++;
	rootTB[from] = to;
	return true;
}

설명

여기서 시간복잡도는 보통 \(N\) 번의 Union() 후에 Find() 연산을 할 때의 Amortized Time Complexity 를 구한다.

총 시간복잡도는 아래의 두 최적화를 모두 하면 O(\(\alpha(N)\)), 모두 안하면 O(\(N\)) 이 된다.

Rank Optimization
- Rank 가 합쳐진 Tree 의 최대 깊이를 의미함.
- Append a root of shallow tree to a root of deeper one in Union().
- 알고리즘 특성 상 최소 이진트리의 크기를 유지하게 되어 Amortized O(\(\log{\mathrm{N}}\)) 을 만듬
Path Compression
- 각 정점의 rootTB[] 는 현재 구성한 Tree 의 Root 만을 저장시키는 것.
- 이것만 사용시 O(\(M\log(N)\)) 이라함. SE, Prinston 수업 PPT
자세한건 Samsung SW 블로그 , Wiki 참고
근데 둘다 하면 오버헤드 때문에 더 느려질 가능성이 커지고, 대체로 더 빠른 Path Compression 만 적용하는 경우가 많음.

MST

Minimum Spanning Tree 의 약자.

아래 코드는 이 문제 를 푸는 것임.

아래 두 알고리즘은 시간복잡도가 보여주듯 Graph 의 간선의 수에 따라 선호되는게 다름

Sparse Graph => Kruskal
Dense Graph => Prim

Kruskal Algorithms

코드

int main()
{
	int v, e;
	cin >> v >> e;

	for (int i = 0; i < e; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		lines[i] = { a, b, c };
	}
	sort(lines, lines + e, [](E& a, E& b) { return a.w < b.w; });
	
	int ans = 0;
	Init(v);
	for (int i = 0; i < e; i++)
		if (Union(lines[i].a, lines[i].b))
			ans += lines[i].w;
	cout << ans;
}

가장 weight 가 낮은 edge 부터 사용해 tree 를 만드는 Gridy Algorithms.

보통 UnionFind 를 사용해 tree 를 구성함
그래서 Spanning Forest 에서도 가능함.

시간 복잡도는 퀵소트 사용시 O(\(E\log{E}\))

Prim’s Algorithms

작동원리는 Graph 를 A(임의의 정점 1개로 시작), B 로 나누고

A 에서 가장 가까운 B 의 한 노드를 A 로 넣는걸 B 가 소멸될때까지 반복하는 것임.

가장 가까운 정점을 찾는 방법에 따라서 시간복잡도가 갈림

수단	복잡도
배열 + 루프	O(\(\vert V \vert ^ 2\))
우선순위 큐 + Edge	O(\(\vert E \vert \log{\vert E \vert }\))
우선순위 큐 + Vertex	O(\(\vert E \vert \log{\vert V \vert }\))
피보나치 큐	O(\(\vert E \vert + \vert V \vert \log{\vert V \vert }\))

우선순위 큐의 경우 O(\(\log{E}\)) 는 O(\(\log{V}\)) 와 같아서 거기서 거기임.
완전그래프에선 우선순위 큐보다 배열과 루프를 쓴 \(\vert V^2 \vert\) 가 더 빠르다는 것에 주의
자세한건 Wiki 참고

O(\(\vert V \vert ^2\)) 버전

코드

struct E { int d, w; };
vector<E> lines[100001]; int prim[100001]; 
bool bSelected[100001];

int main()
{
	fastio;

	int v, e;
	cin >> v >> e;
	
	for (int i = 0; i < e; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		lines[a].push_back({ b, c });
		lines[b].push_back({ a, c });
	}
	
	fill(prim, prim + v+1, 1e9); 
	prim[1] = 0;
	
	int ans = 0;
	for (int i = 1; i <= v; i++)
	{
		int cur = -1, min_w = 1e9;
		for (int j = 1; j <= v; j++)
		{
			if (!bSelected[j] && min_w > prim[j])
			{
				cur = j; 
				min_w = prim[j];
			}
		}
		if (cur < 0) break; // not spanning
		ans += min_w;
		bSelected[cur] = true;
		for (auto& l : lines[cur])
			prim[l.d] = min(prim[l.d], l.w);
	}
	cout << ans;
}

설명

완전 그래프에 가까울수록 큐를 쓰는 버전보다 이 버전이 더 빠름에 주의하자.

O(\(\vert E \vert \log{\vert E \vert }\)) 버전

코드

struct E { int d, w; };
namespace std {

	template<> struct greater<E> {
		bool operator()(const E& a, const E& b) const { return a.w > b.w; }
	};
}
vector<E> lines[100001];
bool bSelected[100001];

int main()
{
	int v, e;
	cin >> v >> e;

	int a, b, c;
	for (int i = 0; i < e; i++)
	{
		cin >> a >> b >> c;
		lines[a].push_back({ b, c });
		lines[b].push_back({ a, c });
	}
	
	int ans = 0;
	priority_queue<E, vector<E>, greater<E>> q; q.push({ 1, 0 });
	for (int i = 1; i <= v && !q.empty(); )  // 최대 갯수만큼 합쳤으면 q 비우기 생략용
	{
		if (bSelected[q.top().d]) {   // q 에 이전 vertex 의 edge 들이 있어 필수
			q.pop(); 
			continue;
		}
		bSelected[q.top().d] = true;
		ans += q.top().w;
		i++;
		
		// 아래에서 queue update 하면 top 이 달리질 수 도 있으니 실수 방지; ranged for loop 에서는 상관 없다.
		int cur = q.top().d; 
		for (auto& l : lines[cur])
			if (!bSelected[l.d])  // 없어도 되는데 약간 느려짐
				q.push(l);

		// if(i <= v && q.empty()) not spanning
	}
	cout << ans;
}

설명

Min Priority Queue 에 Edge 를 저장함

선택된 vertex 마다 priority queue 에 연결된 edge 를 넣음.
queue 의 값을 꺼내면서 지금까지 합치지 않은 가장 가까운 vertex 를 추가함.

사소한 팁으로

이때 이전 vertex 에서 넣은 edge 가 계속 누적되기 때문에 중복여부를 꼭 체크해야함.
edge 를 넣을때 중복여부를 체크하면 약간 빨라짐.
정점 수만큼 루프를 도는건 priority queue 에 남은걸 다 비울 필요 없게하는 용도임.

시간복잡도는 queue 를 완전히 비우고, edge 를 넣을 때 중복여부를 체크하지 않는다면, \(\vert E \vert\) 번 queue 에서 넣고 빼야함. 그러므로 O(\(\vert E \vert \log{\vert E \vert }\))

O(\(\vert E \vert \log{\vert V \vert }\)) 버전

코드

PQ<int, MAX_IN> q;

int main()
{
	int v, e;
	cin >> v >> e;

	int a, b, c;
	for (int i = 0; i < e; i++)
	{
		cin >> a >> b >> c;
		lines[a].push_back({ b, c });
		lines[b].push_back({ a, c });
	}
	
	for (int i = 0; i < v; i++) q.Push(10000000);  // 모든 정점을 미리 넣어놓음
	q.keys[1].v = 0; q.DecreaseKey(q.keys[1]);  // 정점 하나만 갈수 있도록 해놓음
	
	int ans = 0;
	while (!q.Empty())  // 넣는건 없고 빼는것만 있어 v 번 반복.
	{
		int cur = q.TopKey();
		ans += q.Pop();
		for (auto& l : lines[cur])
		{
			q.keys[l.d].v = min(q.keys[l.d].v, l.w);   // 선택된 정점의 간선으로 연결된 정점의 비용을 업데이트 후
			q.DecreaseKey(q.keys[l.d]);   // 우선순위 큐를 업데이트
		}
	}
	
	cout << ans;
}

설명

PQ 는 여기 에서 DecreaseKey() 를 하도록 Max -> Min 으로 교체한 것임.

시간복잡도 설명은 유튜브 에서 잘 설명해줌.

Min Priority Queue 에 Vertex 를 넣고, 하나 빼고 대응되는 Weight 를 최대로 넣어 초기화.
Queue 가 빌 때까지 가장 가까운 정점을 꺼내고,
여기와 연결된 간선의 가중치가 기존보다 더 작으면 DecreaseKey() 함.
모든 간선에 대해서 DecreaseKey() 를 수행하므로 O(\(\vert E \vert \times \log{\vert V \vert}\)) 가 됨.
Queue 내에 공간을 전의 방법보다 덜먹는다는게 장점?

Shortest Path

가중치가 없는 경우 BFS 로 해결이 되지만, 아닌 경우 적절한 알고리즘을 사용해야 한다.

Floyd Warshall

코드

fill(dp[0], dp[100] + 101, 100000000);

... // dp[s][e] = weight of Edge(s, e);

for(int d = 1; d <= n; d++)
	for(int s = 1; s <= n; s++)
		for (int e = 1; e <= n; e++)
			if (dp[s][e] > dp[s][d] + dp[d][e])
				dp[s][e] = dp[s][d] + dp[d][e];

설명

모든 가능한 경로에 대해서 가장 짧은 비용을 얻어냄.

경로추적은 dp[s][e] 를 업데이트 시 d 값을 넣어주면 됨.
이후 DFS 를 Inorder 로 해주면 됨.

시간복잡도는 O(\(\vert N^3 \vert\)) 가 자명함

Dijkstra

코드

struct E { int d, w; };
namespace std {

	template<> struct greater<E> {
		bool operator()(const E& a, const E& b) const { return a.w > b.w; }
	};
}

vector<E> lines[MAX_IN]; 
int dp[MAX_IN];
int n; // vertex number

void Dijkstra(int start)
{
	fill(dp, dp + n + 1, 1e9);
	priority_queue<E, vector<E>, greater<E>> q;
	dp[start] = 0; q.push({start, 0});

	while (!q.empty())
	{
		E cur = q.top(); q.pop();
		if (dp[cur.d] < cur.w) continue;  // filter out an outdated edge
		for (E& l : lines[cur.d])
		{
			if (dp[cur.d] + l.w < dp[l.d])
			{
				dp[l.d] = dp[cur.d] + l.w;
				q.push({ l.d, dp[l.d] });
			}
		}
	}
}

설명

Dijkstra 를 수행하면 시작점으로부터 나머지 모든 정점에 대한 거리가 구해짐

작동 방법은 Gridy + DP 가 같이 사용됨

시작점을 제외한 모든 점까지의 거리( dp[] )를 무한대로 지정함
방문하지 않은 모든 정점 중에서 가까운 정점 s 을 남은 정점이 없을 때까지 선택함.
- s 와 연결된 정점 t 마다, dp[t] = min(dp[t], dp[s] + weight of s->t ) 를 수행함.
- 그러면 dp 는 지금까지 방문한 정점들에 대해서 나머지 정점들의 가장 짧은 길이를 저장하고 있음. 이 중 가장 가까운 정점은 지금까지 선택된 정점 다음으로 가까운 정점이 되며 Gridy 를 반복하게 됨.

가까운 정점 s 를 선택하는 방법을 최적화 하는 과정에서 Prim’s Algorithms 과 같은 이슈를 가짐.

위 코드는 Priority Queue 에서 현재까지 연결된 모든 간선을 관리한 것.
위에서 살펴보았듯 Priority Queue 에서 모든 정점을 관리하며 DecreaseKey() 를 수행할 수도 있음.

A*

이거 보자

Dijkstra 는 시작점에서 가장 가까운 정점들을 차례로 추가해나감.

추가해나가는 순서대로 가는건 전혀 최단거리가 아님.

A* 는 연결한 정점들로부터 기존 거리 + Huristic 거리 의 합의 값이 제일 낮은 것부터 추가함.

Bellman-Ford

코드

struct E { int d, w; };

vector<E> edges[501];
int n; // vertex number

const int MAX_IN = 501;
long long distTB[MAX_IN];

bool bellman(int start) 
{
	fill(distTB, distTB + n + 1, 1e9);
	distTB[start] = 0;
	bool updated = false;
	for (int i = 0; i < n; i++)
	{
		updated = false;
		for (int s = 0; s < n; s++) 
		{
			if (distTB[s] == 1e9) continue;
			for (auto& l : edges[s]) 
				if (distTB[l.d] > distTB[s] + l.w) 
				{
					distTB[l.d] = distTB[s] + l.w; // edge relaxation
					updated = true;
				}
		}
		if (updated == false) break;
	}
	return updated != true;
}

설명

시간복잡도는 \(O(\vert V \vert \vert E \vert)\) 이다.

다익스트라에서는 사이클 내의 거리가 음수가 되면 무한루프를 돌게된다. 벨만 포드 알고리즘은 그렇지 않으며 그러한 사이클을 탐지해낼 수도 있다.

아이디어는 Edge Relaxation 이 가능한 경우의 수가 최대 \(V-1\) 번이 정상적이고 그 이상이 되면 무한루프라는 것이다. 왜냐하면 다른 정점을 경유해서 거리가 변할 수 있는 경우의 수는 정점 간 간선의 갯수이기 때문이다. 그래서 정점을 점차 추가하면서 추가된 정점과 연결된 모든 간선에 대해서 Edge Relaxation 을 하고, 마지막으로 정점을 추가했을 때도 Edge Relaxation 이 일어나면 Cycle 이라고 알린다.

시작점이 없이 그냥 그래프에서 음수 사이클을 찾을 때도 사용할 수 있다. 이땐 시작점의 거리만 0 으로 초기화 하는게 아니라 모든 정점의 거리를 똑같이 초기화 한 뒤 탐색을 시작하면 된다. 문제, 풀이

DAG 에서 Negative Weight 가 없는 경우 경우 Topological Sort 에 따른 순서로 Edge Relaxation 을 하면 \(O(\vert E \vert)\) 에서 끝낼 수 있다.

SPFA

코드

struct E { int d, w; };
vector<E> edges[501];
int n; // vertex number

const int MAX_IN = 501;
bool inQ[MAX_IN]; 
long long distTB[MAX_IN], relaxTB[MAX_IN];

bool SPFA(int start) 
{
	fill(distTB, distTB + n+1, 1e9);
	queue<int> q;

	q.push(start);  inQ[start] = true;
	distTB[start] = 0;
	
	while (!q.empty()) 
	{
		int cur = q.front(); q.pop(); inQ[cur] = false;
		for (auto& l : edges[cur]) 
		{
			if (distTB[l.d] > distTB[cur] + l.w) 
			{
				distTB[l.d] = distTB[cur] + l.w;  // edge relaxation
				
				if (inQ[l.d]){
					q.push(l.d); 
					inQ[l.d] = true;
				}
				
				if (++relaxTB[l.d] >= n)
					return false;				
			}
		}
	}
	
	return true;
}

설명

벨만포드 알고리즘의 빠른버전. bellman-ford 의 가장 바깥쪽 루프 한번은 queue 에 size 를 저장한 후 그 횟수만큼 dequeue 한 것과 같다.

최악의 시간복잡도는 \(O(\vert V \vert \vert E \vert)\) 으로 동일하지만 평균 시간복잡도가 실험 결과 상 \(O(\vert E \vert)\) 이라고 한다. 위키가 그렇게 어려운 내용도 없으니 한번 읽어보자.

Mona04