8. 기타 그래프 이론: 크루스칼 알고리즘

크루스칼 알고리즘

최소 신장 트리를 찾는 알고리즘

최소 신장 트리는 사이클이 존재하지 않고 모든 노드가 연결되어 있어야 함

 

모든 도시가 연결되어야 하고 도로 건설 비용을 최소화 해야할 때

크루스칼 알고리즘을 사용하면..

도로를 짓는 데 필요한 최소 비용을 계산할 수 있다

 

먼저 간선의 정보를 입력받는다(노드1,노드2,비용)

비용에 대하여 오름차순으로 정렬한다

비용이 적게 드는 순으로 노드1,노드2가 사이클이 아니라면(부모 노드가 같지 않다면) 노드 1,2를 union연산을 수행하고,

노드1,2의 부모노드가 같다면 무시한다

동그라미 안 숫자는 각 간선의 비용에 대하여 오름차순으로 번호를 매긴 것이고,

그래프에서 빨간 선은 연결된 것,

파란 선은 연결하지 않고 무시한 것이다

 

def find_parent(parent,x):
    if parent[x]!=x:
        parent[x]=find_parent(parent,parent[x])
    else:
        return parent[x]

def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a>b:
        parent[a]=b
    else:
        parent[b]=a

v,e=map(int,input().split())

parent=[0]*(v+1)

for i in range(v+1):
    parent[i]=i

edges=[]
for i in range(e):
    a,b,cost=map(int,input().split())
    edges.append((cost,a,b)) #비용이 맨 앞에오게 리스트에 추가함

edges.sort()
result=0
for edge in edges:
    cost,a,b=edge
    if find_parent(parent,a)==find_parent(parent,b):
        continue
    else:
        union_parent(parent,a,b)
        result+=cost

print(result)