Minimum Spanning Trees - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:22:35Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:22 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[Graph#Minimum Spanning Trees\|Graph]]		상위 문서: [[Graph#Minimum Spanning Trees\|Graph]]

2025년 10월 17일 (금) 05:56에 Pinkgo님의 편집

2025-10-17T05:56:48Z

← 이전 판		2025년 10월 17일 (금) 05:56 판
37번째 줄:		37번째 줄:

	==Prim’s Algorithm==		==Prim’s Algorithm==
			[[파일:Figure 1. Prim’s Algorithm in Action.png\|가운데\|섬네일\|500x500픽셀\|Figure 1. Prim’s Algorithm in Action]]
	Prim 알고리즘은 탐욕적(Greedy) 접근법을 사용해 MST를 만드는 대표적인 방법이다. 이는 아래와 같은 방법을 따른다:		Prim 알고리즘은 탐욕적(Greedy) 접근법을 사용해 MST를 만드는 대표적인 방법이다. 이는 아래와 같은 방법을 따른다:
	# 시작점 하나를 정하고, 그 정점에서부터 시작해 하나씩 간선을 추가하면서 트리를 확장한다.		# 시작점 하나를 정하고, 그 정점에서부터 시작해 하나씩 간선을 추가하면서 트리를 확장한다.

Pinkgo: /* Fast Component Tests Give Fast MST */

2025-10-17T05:52:37Z

Fast Component Tests Give Fast MST

← 이전 판		2025년 10월 17일 (금) 05:52 판
142번째 줄:		142번째 줄:
	add to T		add to T
	component(v) = component(w)		component(v) = component(w)
	이때 해당 알고리즘에서 [[Data Structures#Union-Find\|Union-Find]] 자료구조을 사용하면 사이클 검사를 O(log n) 이하로 줄여서 전체 시간복잡도를 O(m log(m))으로 개선 가능하다. 이때 O(m log(m))과 O(m log(n))을 비교하면, 그래프가 매우 커질수록 O(m log(n))이 조금 더 빠르다.		이때 해당 알고리즘에서 [[Data Structures#Union-Find\|Union-Find]] 자료구조을 사용하면 사이클 검사를 O(log n) 이하로 줄여서 전체 시간복잡도를 O(m log(m))으로 개선 가능하다. 이때 O(m log(m))과 O(m log(n))을 비교하면, 그래프가 매우 커질수록 O(m log(n))이 조금 더 빠르다. 아래는 Union-Find 자료구조를 이용하여 same_component() 함수를 구현한 예시이다:
			<syntaxhighlight lang="c">
			bool same_component(union_find *s, int s1, int s2) {
			return (find(s, s1) == find(s, s2));
			}
			</syntaxhighlight>

	[[Data Structures#Union-Find\|Union-Find]] 자료구조에 대한 자세한 설명은 해당 문서를 참조하십시오.		[[Data Structures#Union-Find\|Union-Find]] 자료구조에 대한 자세한 설명은 해당 문서를 참조하십시오.

	==각주==		==각주==

Pinkgo: /* Fast Component Tests Give Fast MST */

2025-10-17T05:12:55Z

Fast Component Tests Give Fast MST

← 이전 판		2025년 10월 17일 (금) 05:12 판
142번째 줄:		142번째 줄:
	add to T		add to T
	component(v) = component(w)		component(v) = component(w)
	이때 해당 알고리즘에서 [[Data Structures#Union-Find\|Union-Find]] 자료구조을 사용하면 사이클 검사를 O(log n) 이하로 줄여서 전체 시간복잡도를 O(m log(m))으로 개선 가능하다. 이때 O(m log(m))과 O(m log(n))을 비교하면, 그래프가 매우 커질수록 O(m log(n))이 조금 더 빠르다.		이때 해당 알고리즘에서 [[Data Structures#Union-Find\|Union-Find]] 자료구조을 사용하면 사이클 검사를 O(log n) 이하로 줄여서 전체 시간복잡도를 O(m log(m))으로 개선 가능하다. 이때 O(m log(m))과 O(m log(n))을 비교하면, 그래프가 매우 커질수록 O(m log(n))이 조금 더 빠르다.

			[[Data Structures#Union-Find\|Union-Find]] 자료구조에 대한 자세한 설명은 해당 문서를 참조하십시오.

	==각주==		==각주==

Pinkgo: /* Fast Component Tests Give Fast MST */

2025-10-17T05:03:44Z

Fast Component Tests Give Fast MST

← 이전 판		2025년 10월 17일 (금) 05:03 판
135번째 줄:		135번째 줄:
	* merge_components(C1, C2): 두 컴포넌트를 하나로 합치기 (Union 연산)		* merge_components(C1, C2): 두 컴포넌트를 하나로 합치기 (Union 연산)
	따라서 위 두 연산을 빠르게 수행하여 전체 알고리즘을 훨씬 빠르게 할 수 있다. 아래는 Union-Find(Disjoint Set Union, DSU) 기반으로 kruskal 알고리즘을 구현한 의사 코드이다:		따라서 위 두 연산을 빠르게 수행하여 전체 알고리즘을 훨씬 빠르게 할 수 있다. 아래는 Union-Find(Disjoint Set Union, DSU) 기반으로 kruskal 알고리즘을 구현한 의사 코드이다:
	모든 간선을 heap(priority queue)에 저장<ref>가장 작은 간선을 빠르게 꺼내기 위함이다.</ref>		모든 간선을 [[Priority Queues\|heap(priority queue)]]에 저장<ref>가장 작은 간선을 빠르게 꺼내기 위함이다.</ref>
	count = 0		count = 0
	while (count < n-1)<ref>n개의 정점이 필요하면, n-1개의 간선을 구성해야 한다.</ref>		while (count < n-1)<ref>n개의 정점이 필요하면, n-1개의 간선을 구성해야 한다.</ref>
142번째 줄:		142번째 줄:
	add to T		add to T
	component(v) = component(w)		component(v) = component(w)
	이때 해당 알고리즘에서 Union-Find 자료구조을 사용하면 사이클 검사를 O(log n) 이하로 줄여서 전체 시간복잡도를 O(m log(m))으로 개선 가능하다. 이때 O(m log(m))과 O(m log(n))을 비교하면, 그래프가 매우 커질수록 O(m log n)이 조금 더 빠르다.		이때 해당 알고리즘에서 [[Data Structures#Union-Find\|Union-Find]] 자료구조을 사용하면 사이클 검사를 O(log n) 이하로 줄여서 전체 시간복잡도를 O(m log(m))으로 개선 가능하다. 이때 O(m log(m))과 O(m log(n))을 비교하면, 그래프가 매우 커질수록 O(m log(n))이 조금 더 빠르다.

	==각주==		==각주==

Pinkgo: /* ㅁㄴㅇㄹ */

2025-10-17T04:59:44Z

ㅁㄴㅇㄹ

← 이전 판		2025년 10월 17일 (금) 04:59 판
122번째 줄:		122번째 줄:
	# 이 과정을 n번 반복 → 총 O(n × n) = O(n²)		# 이 과정을 n번 반복 → 총 O(n × n) = O(n²)

	==~~ㅁㄴㅇㄹ~~==		==Kruskal’s Algorithm==
			Kruskal 알고리즘은 Prim 알고리즘과 마찬가지로 greedy 방식의 MST 알고리즘이다. 하지만 kruskal 알고리즘은 prim 알고리즘과는 접근 순서가 다르다. Prim 알고리즘이 정점 중심으로 동작한다면, kruskal 알고리즘은 간선 중심으로 동작하기 때문이다. Kruskal 알고리즘은 간선들을 오름차순으로 정렬 후, 가장 작은 간선부터 사이클이 생기지 않게 추가하는 방식이다. Figure 1을 다시 보면, kruskal 알고리즘이 어떻게 동작하는지 관찰할 수 있으며, 시작 정점이 따로 없다는 것을 알 수 있다.

	~~<syntaxhighlight lang~~=~~"c">~~		===Time Complexity of Kruskal's Algorithm===
			Kruskal 알고리즘에서 모든 간선을 정렬하는데에는 O(m log(m))의 시간 복잡도가 소요된다. 또한 각 간선에 대해 간선을 추가했을 때 사이클이 생기는지 검사하는데, 이를 DFS/BFS 알고리즘으로 수행하면 각 간선에 대해 O(n)의 시간 복잡도가 소요된다. 따라서 모든 간선에 대해서 사이클 여부를 검사하면 O(mn)의 시간 복잡도가 소요된다. 따라서 kruskal 알고리즘의 시간 복잡도는 O(m log(m) + mn) = O(mn)이 된다.

	<~~/syntaxhighlight~~>		이때, 이를 Prim 알고리즘의 시간 복잡도인 O(n<sup>2</sup>)과 비교할 수 있다. 이 두 시간복잡도를 비교하면, 간선의 수가 많은 dense graph에서는 Prim 알고리즘이 유리하다는 결과가 도출된다. 반면 Kruskal 알고리즘은 간선을 정렬해서 하나씩 고르는 방식이라, 간선이 적을수록 더 효율적이다.
	<~~syntaxhighlight lang="c"~~>

	</~~syntaxhighlight~~>		===Fast Component Tests Give Fast MST===
	<~~syntaxhighlight lang="c"~~>		더욱 빠르게 사이클을 검사하여 kruskal 알고리즘을 더 효율적으로 만들 수 있는 방식이 있다. 이는 사이클을 매번 BFS/DFS로 검사하지 않고, “현재 어떤 정점이 어떤 연결요소(component)”에 속해 있는지만 빠르게 확인하는 방식이다. 기본적으로 kruskal 알고리즘은 MST를 만들면서 여러 connected component(트리 조각)를 합친다. 만약 새 간선이 같은 component의 두 정점을 연결한다면 사이클이 생기므로 이를 제외해야 한다. 따라서 kruskal 알고리즘을 구현하기 위해서는 두 가지 연산이 필요하다:
			* same_component(v1, v2): 두 정점이 같은 컴포넌트에 속하는가?
	</~~syntaxhighlight>~~		* merge_components(C1, C2): 두 컴포넌트를 하나로 합치기 (Union 연산)
			따라서 위 두 연산을 빠르게 수행하여 전체 알고리즘을 훨씬 빠르게 할 수 있다. 아래는 Union-Find(Disjoint Set Union, DSU) 기반으로 kruskal 알고리즘을 구현한 의사 코드이다:
			모든 간선을 heap(priority queue)에 저장<ref>가장 작은 간선을 빠르게 꺼내기 위함이다.</ref>
			count = 0
			while (count < n-1)<ref>n개의 정점이 필요하면, n-1개의 간선을 구성해야 한다.</ref>
			get next edge (v, w)
			if (component(v) ≠ component(w)) //다른 컴포넌트에 속하면 연결.
			add to T
			component(v) = component(w)
			이때 해당 알고리즘에서 Union-Find 자료구조을 사용하면 사이클 검사를 O(log n) 이하로 줄여서 전체 시간복잡도를 O(m log(m))으로 개선 가능하다. 이때 O(m log(m))과 O(m log(n))을 비교하면, 그래프가 매우 커질수록 O(m log n)이 조금 더 빠르다.

	==각주==		==각주==

Pinkgo: /* Prim’s Implementation */

2025-10-17T04:25:44Z

Prim’s Implementation

← 이전 판		2025년 10월 17일 (금) 04:25 판
117번째 줄:		117번째 줄:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
			위 알고리즘의 시간 복잡도를 분석하면:
			# 매번 가장 싼 간선을 찾기 위해 distance 배열 전체를 탐색 → O(n)
			# 각 정점을 트리에 추가할 때마다 인접 리스트를 확인 → O(n)
			# 이 과정을 n번 반복 → 총 O(n × n) = O(n²)

			==ㅁㄴㅇㄹ==

	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">

126번째 줄:		133번째 줄:

	</syntaxhighlight>		</syntaxhighlight>

	~~위 알고리즘의 시간 복잡도를 분석하면:~~
	~~# 매번 가장 싼 간선을 찾기 위해 distance 배열 전체를 탐색 → O(n)~~
	~~# 각 정점을 트리에 추가할 때마다 인접 리스트를 확인 → O(n)~~
	~~# 이 과정을 n번 반복 → 총 O(n × n) = O(n²)~~

	==각주==		==각주==

Pinkgo: /* 각주 */

2025-10-17T04:25:16Z

각주

← 이전 판		2025년 10월 17일 (금) 04:25 판
126번째 줄:		126번째 줄:

	</syntaxhighlight>		</syntaxhighlight>

			위 알고리즘의 시간 복잡도를 분석하면:
			# 매번 가장 싼 간선을 찾기 위해 distance 배열 전체를 탐색 → O(n)
			# 각 정점을 트리에 추가할 때마다 인접 리스트를 확인 → O(n)
			# 이 과정을 n번 반복 → 총 O(n × n) = O(n²)

	==각주==		==각주==

Pinkgo: /* Applications of MSTs */

2025-10-17T04:23:18Z

Applications of MSTs

@@ 36번째 줄: / 36번째 줄: @@
 TSP(Traveling Salesman Problem)는 외판원 문제라고도 불리며, 모든 정점(도시)을 한 번씩 방문하고 다시 출발점으로 돌아오는 최소 비용의 경로를 찾는 문제이다. 이때 MST는 TSP의 좋은 heuristic(근사 알고리즘)을 제공한다. MST를 두 번 따라가면 모든 노드를 방문하게 되고, 그 비용은 최적 TSP 경로의 2배 이내이기 때문이다. 즉, MST는 TSP의 하한(lower bound)을 제공하고, 실제 문제 해결의 출발점으로 자주 사용된다.
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 <syntaxhighlight lang="c">

Pinkgo: /* 개요 */

2025-10-17T03:26:07Z

개요

← 이전 판		2025년 10월 17일 (금) 03:26 판
4번째 줄:		4번째 줄:

	==개요==		==개요==
			Spanning Tree는 주어진 그래프 G의 모든 정점을 포함하면서 사이클이 없는 부분 그래프이다. 그 중에서도 MST(Minimum Spanning Tree)는 G의 모든 spanning tree 중 간선 가중치의 총합이 최소인 트리를 의미한다. 이때 동일한 가중치를 가진 간선이 여러 개 있을 경우, 서로 다른 MST들이 존재할 수 있다. 또한 이는 Greedy Algorithm으로 항상 최적의 해를 얻을 수 있는 대표적인 문제이다. 하지만, 이를 해결하기 위해서는 효율적인 자료구조(우선순위 큐, Disjoint Set Union)가 필요하다.

			아래는 해당 문서에서 MST에 대한 코드를 작성할 때 주어지는 그래프를 저장하는 자료구조이다:
			<syntaxhighlight lang="c">
			int y; // 간선이 연결된 정점
			int weight; // 간선의 가중치
			struct edgenode *next; // 다음 간선을 가리키는 포인터
			</syntaxhighlight>
			위는 인접 리스트(adjacency list)에서 각 간선이 가중치(weight) 정보를 가지도록 확장한 형태이다.
			<syntaxhighlight lang="c">
			edgenode *edges[MAXV+1]; // 각 정점의 인접 리스트 시작점
			int degree[MAXV+1]; // 각 정점의 차수 (outdegree)
			int nvertices; // 정점 개수
			int nedges; // 간선 개수
			int directed; // 방향 그래프 여부
			</syntaxhighlight>
			위는 그래프 구조 전체를 정의한 코드이다.

			==Applications of MSTs==
			MST 알고리즘은 여러 도시나 서버를 가장 적은 비용으로 연결하는 네크워크 구축을 하는데 사용된다. 또한 MST를 사용하여 점들을 연결한 뒤 가중치가 큰 간선을 끊어 그룹을 형성하는데 사용되기도 한다. 그 외에도, 친구 관계 그래프에서 자연스러운 친구 집단을 찾는 것과 같은 소셜 그래프 분석에도 사용된다.

			===MSTs and Net Partitioning===
			MST 알고리즘은 그래프를 여러 작은 부분으로 분할(partition)하는데 사용되기도 한다. 이는 아래와 같은 과정을 거친다:
			# 먼저 전체 그래프에서 MST를 만든다.
			#* MST는 전체 정점을 모두 연결하면서도 가장 적은 비용으로 연결된 그래프이다.
			#* 이를 통해 그래프 내의 "가벼운 간선"은 유지되고, "비싼 간선"은 최소화할 수 있다.
			# MST를 만든 뒤, 그 안에서 가장 큰 가중치의 간선을 하나 혹은 여러 개 제거한다.
			#* 이렇게 하면 자연스럽게 그래프가 서로 잘 연결된 여러 작은 덩어리(subgraphs)로 나뉜다.

			===MSTs and TSP===
			TSP(Traveling Salesman Problem)는 외판원 문제라고도 불리며, 모든 정점(도시)을 한 번씩 방문하고 다시 출발점으로 돌아오는 최소 비용의 경로를 찾는 문제이다. 이때 MST는 TSP의 좋은 heuristic(근사 알고리즘)을 제공한다. MST를 두 번 따라가면 모든 노드를 방문하게 되고, 그 비용은 최적 TSP 경로의 2배 이내이기 때문이다. 즉, MST는 TSP의 하한(lower bound)을 제공하고, 실제 문제 해결의 출발점으로 자주 사용된다.

			<syntaxhighlight lang="c">

			</syntaxhighlight>
			<syntaxhighlight lang="c">

			</syntaxhighlight>
			<syntaxhighlight lang="c">

			</syntaxhighlight>
			<syntaxhighlight lang="c">

			</syntaxhighlight>

	==각주==		==각주==