1. 크루스칼 알고리즘이란? "사이클을 이루지 않는 선에서 n-1개 간선을 탐욕적으로(가중치 순으로) 선택해 나가는 MST알고리즘. 사이클형성여부는 Union-find집합 자료구조로 판별
2. 프림 알고리즘이란? "정점을 탐욕적으로 n개 선택해 나가는 알고리즘이다. 구체적인 방법은 처음에 임의의 정점을 선택하고 선택된 정점을 중심으로 dist배열을 매번갱신하는 것이다."
" 이렇게 기억해 둔다. 좀 더 자세히는 최소신장트리를 해결하는 탐욕적 알고리즘의 하나로 n-1개의 간선을 선택할때까지 가중치 순으로 정렬된 간선을 사이클을 이루지 않는 선에서 하나씩 선택해 가는 알고리즘이다. 여기서 사이클을 이루는지의 여부는 Union-Find집합 자료구조로 알수있다. 크루스칼 알고리즘=굳이 그래프를 만들 필요 없음.
다시 이 글을 볼때면 또 크루스칼이 무엇인지를 잊고 있을때이다. 가장 쉬운 방법은 그림으로 기억하는 것이다. 하지만 크루스칼 알고리즘은 그림이 아니다. 실제로 크루스칼 알고리즘을 구현해 내는데 그래프 모형을 만들 필요가 없다! 크루스칼 알고리즘은 그림이 아닌 그냥 알고리즘이다. 이게 무슨말? "간선을 정렬시키고 그로부터 탐욕적으로 n-1개를 사이클을 형성하지 않는 선에서 선택하는 것" 이라는 것이다. 이것은 그림으로 표현할 수 없는 개념이다.
프림에서는 dist를 매번 갱신해 주기 때문에 feasible 검사를 안하고 크루스칼에서는 모든 간선을 대상으로 무분별 시도하기 때문에 feasible검사를 한다고 생각하면 다른 문제에도 적용할 수 있는 확장성이 생기는 것 같다.
즉, 모든 것을 대상으로 하면 무분별하기 때문에 feasible test를 진행하고 매번 갱신하면 무분별하지 않기 때문에 feasible test를 진행하지 않는다고 우선 기억해 두자.
(또 다시 처음부터 코드 짜는데 도움되는 Tip: 프림은 정점을 선택하기 때문에 dist라는 길이 배열이 있고 이것을 매번 갱신하게 된다. 크루스칼의 핵심은 간선을 정렬한 후 탐욕적으로 선택하는 데 있다.)
Union-Find 집합 자료구조=크루스칼 알고리즘뿐만아니라 여러 알고리즘에서 사용되는 집합 자료구조로 서로소인 집합들을 표현할 때 사용되는 집합자료구조이다(내생각: 집합 자료구조라고는 하지만 set( )이나 트리, 어느것 하나 사용되지 않았다. Union-Find연산을 지원해야하기 때문에 Union-Find집합 자료구조라고 이름이 붙음.
어떤 두 정점이 같은 그래프에 속해 있는지를 parent 리스트를 통해 알수 있다.
구체적인 parent리스트 구성방법. 첫번째로는 parent리스트에 자기자신을 parent[i]값으로 설정한다. union의 과정에서 각 정점의 인덱스에 해당하는 정점들의 parent값을 지정해 줌으로써 부모 자식관계를 성립해 나간다. (두번째 교수의 코드처럼 find함수를 재귀형식으로 짜면 find에서도 부모 자식관계가 성립됨.)
하나의 간선(여기서 말하는 간선이 위에서 말하는 두 정점)을 추가하여 사이클이 형성될지 말지는(정점들의 집합,여기서 실제로 집합은 트리로 구현하게 되는데 실제로는 트리를 따로 구현하지 않아도 됨)집합을 대표하는 루트노드의 비교를 통해 알수 있다. 즉 간선(A,B)라 할때 정점A가 속해있는 집합의 루트노드와 정점B가 속해있는 집합의 루트노드를 비교하여 다르면 서로 다른 집합이므로 간선을 추가 하여도 사이클이 형성되지 않는것이고 같으면 사이클이 형성되는 것이다.
그런데 어떻게 같으면 사이클이 형성된다는 것일까? 사실 루트노드가 자기자신이 아닌 다른 수로 같다는 말은 이미 그 정점 2개가 이전의 어딘가의 과정에서 이미 한 그룹의 집합으로 포함됬다는 의미이다. 즉 (A,B)라는 간선은 새로운 간선일지라도 정점 A,B는 이미 다른 간선에 포함되었던 적이 있었던 정점들인 것이다. 따라서 루트노드가 같으면 해당 간선((A,B))을 추가하였을때 사이클을 형성하게 되는 것이다.
9장 A번 답
#크루스칼 알고리즘
from sys import stdin
def mstkruskal(vertex, eList):
vsize=vertex
uni=Union_find(vsize)
sum=0
eList.sort(key=lambda e:e[2], reverse=True)
edgeAccepted=0
while edgeAccepted<vsize-1:
e=eList.pop(-1)
u=uni.find(e[0])
v=uni.find(e[1])
if(u!=v):
sum+=e[2]
uni.union(u, v)
edgeAccepted+=1
print(sum)
class Union_find:
def __init__(self, vsize):
self.parent = list()
self.set_size = list()
for i in range(vsize):
self.parent.append(i)
for i in range(vsize):
self.set_size.append(1)
def find(self, id):
if id ==self.parent[id]: return id
self.parent[id]=self.find(self.parent[id])
return self.parent[id]
# def union(self, id1, id2):
# if(id1<=id2):
# self.set_size[id1]+=self.set_size[id2]
# self.set_size[id2]=0
# self.parent[id2]=id1
# else:
# self.set_size[id2]+=self.set_size[id1]
# self.set_size[id1]=0
# self.parent[id1]=id2
#교수가 원하는 크기가 더작은 집합을 더 큰집합의 루트노드의 자식노드로 union하는 코드
def union(self, id1, id2):
if(self.set_size[id1]<=self.set_size[id2]):
self.set_size[id2]+=self.set_size[id1]
self.set_size[id1]=0
self.parent[id1]=id2
else:
self.set_size[id1]+=self.set_size[id2]
self.set_size[id2]=0
self.parent[id2]=id1
def main():
num=int(stdin.readline())
for _ in range(num):
vertex, edge=map(int, stdin.readline().split())
edges=list()
arr=list(map(int, stdin.readline().split()))
for a,b,c in zip(arr[0::3], arr[1::3],arr[2::3]):
edges.append((a,b,c))
mstkruskal(vertex,edges)
main()여기서 잠깐! 보통 크루스칼 알고리즘은 간선을 기반으로 하고 프림 알고리즘은 정점을 기반으로 한다고 한다. 위의 코드에서 보듯이 u, v은 엄연한 정점의 인덱스인데 왜 이런 말이 나오는 것일까? 그리고 프림 알고리즘은 명백히 간선의 길이를 비교하는데 왜 정점 기반이라고 할까? 물론 간선의 길이가 getMinVertex함수안에서 비교된다. 하지만 이것은 반환값만 보아도 최소비용간선을 가질수 있는 정점을 반환하기 위한 것이다.
그리고 모든 것을 떠나 가장 중요한 이유는 알고리즘의 결과값을 그려나가는 주요 반복문이 프림은 정점을 기반(for i in range(vsize))으로 하고 크루스칼은 간선을 기반(while edgeAccepted<vsize-1)으로 한다는 것이다!!! 자연스럽게 프림은 정점을 출력하고 크루스칼은 간선을 출력하게 된다.
----------프림----------
vertex=['A','B','C','D','E','F','G']
weight=[[None,29,None,None,None,10, None],
[29, None, 16, None, None, None, 15],
[None, 16, None, 12, None,None, None],
[None, None, 12, None, 22, None, 18],
[None, None, None, 22, None, 27, 25],
[10, None, None, None, 27, None, None],
[None, 15, None, 18, 25, None, None]
]
import sys
INF=sys.maxsize
def getMinVertex(dist, selected):
minv=0
mindist=INF
for v in range(len(dist)):
if not selected[v] and dist[v]<mindist:#or if selected[v]==False ~ ~
mindist=dist[v]
minv=v
return minv
def mstPrim(vertex, adj):
vsize=len(vertex)
dist=[INF]*vsize
selected=[False]*vsize
dist[0]=0
for i in range(vsize):#프림 알고리즘의 결과값을 그려나가는 주요반복문
u=getMinVertex(dist, selected)#그때 그때 그려지는 부분트리에서 최소 가중치 간선을 가질수 있는 정점을 출력(이부분이 탐욕적 알고리즘의 특성을 잘 보여줌)
selected[u]=True
print(vertex[u], end=' ')
for v in range(vsize):
if(adj[u][v]!=None):
if(selected[v]==False and adj[u][v]<dist[v]):#매번 정점(U)을 새로이 선택함으로써 확장되어가는 부분트리에서 최소간선의
#길이(dist[v])를 갱신해 가고 있다.
dist[v]=adj[u][v]
print()
mstPrim(vertex, weight)우선순위 큐를 이용한 프림 알고리즘 (dist배열 없이도 답을 구할수 있음. 하지만 dist배열을 이용하면 우선순위큐에 들어가는 요소를 줄일수 있음)
def mstPrim(adj):
vSize=len(adj)
selected=[False]*vSize
dist=[INF]*vSize
dist[0]=0
heap=[]
heapq.heappush(heap, (0,0))
sum=0
for i in range(vSize):
while(True):
value, u=heapq.heappop(heap)
if(not selected[u]):
break
sum+=value
selected[u]=True
for v in range(vSize):
if(adj[u][v]!=None and not selected[v] and dist[v]>adj[u][v]):
dist[v]=adj[u][v]
heapq.heappush(heap, (dist[v],v))
print(sum)
크루스칼과 프림 알고리즘의 차이점
1. 크루스칼 알고리즘 = 간선 중심, 프림 알고리즘 = 정점 중심
2. 크루스칼 알고리즘의 경우 항상 최소비용의 간선부터 출력되지만, 프림 알고리즘의 경우 내가 선택한 정점부터 출력된3다. 그리고 그 정점부터 시작해 차례대로 출력된 정점들을 연결하면 항상 같은 궤적을 그린다.
3. 프림이 처음에 임의로 선택한 정점을 중심으로 부분트리가 확장되어 가는 그림이라면 크루스칼은 산발적으로 흩어진 간선들을 하나하나씩 선택해가는 개념이다. 따라서 크루스칼에서는 매번 정렬된 랜덤한 간선을 선택하게 되므로 사이클을 형성하는지의 유무를 검사해주어야 한다.
(프림 알고리즘이 정점 중심이라고는 하지만 실질적으로 그 근간에는 간선이 있다. 가장 최소비용의 간선부터 선택해야 하는 것이다. 그리고 간선을 선택했다면 그것이 곧 정점을 선택했다는 것의 의미가 된다. 그렇다. 결국 프림이건 크루스칼이건 모두 간선 중심인 것이다.
어떻게 프림 알고리즘을 우선순위 큐를 이용하여 구현하는 것이 가능한 것일까? 탐욕적 알고리즘이기 때문이다. 우선순위 큐 그 자체가 최소비용을 먼저반환하는 탐욕적 알고리즘 그 자체이기 때문이다.)
최소비용신장트리(MST): 크루스칼, 프림
최단거리문제(Shortest Path): 다익스트라, 벨멘-포드, 플로이드-와샤
