신장트리

신장트리: 하나의 그래프가 있을 때 모든 노드를 포함하면서  사이클이 존재하지 않는 부분 그래프

-> 연결그래프의 부분그래프

 

크루스칼 알고리즘: 최소신장 트리 (최소한의 비용으로 만들 수 있는 신장트리 찾는 알고리즘)의 대표 알고리즘

 

 

크루스칼은 가장 적은 비용으로 모든 노드를 연결할 수 있음. 그리디로 분류된다.

 

 

모든간선에 대해서 정렬을 수행후 가장 거리가 짧은 간선부터 집합에 포함시킨다.

사이클을 발생시킬 수 있는 간선은 집합에 포함하지 않는다.

 

알고리즘:

1.간선 데이터를 비용에 따라 오름차순으로 정렬

 

2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인.

    -1 사이클이 발생하지 않으면 최소신장트리에 포함.

    -2 사이클 발생 시 포함안함

 

3. 모든 간선에 대해서 2번 반복

 

 

노드가 N개면 최종적으로 최소신장트리에 포함되는 간선의 개수는 N-1개이다.

 

 

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

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

#노드, 간선개수입력 받기.
v,e=map(int,input().split())
parent=[0]*(v+1)

#모든 간선 리스트, 최종비용을 담을 변수
edges=[]
result=0

#부모테이블 자신으로 초기화
for i in range(1,v+1):
    parent[i]=i


for i in range(e):
    a,b,cost=map(int,input().split())
    #비용순으로 정렬하기 위해 튜플의 첫번째 원소를 비용으로 지정
    edges.append((cost,a,b))

#간선을 비용순으로 정렬
edges.sort()


#간선 하나씩 확인
for cost,a,b in edges:
    #사이클을 확인해서 안생기면union 생기면 
    if find_parent(parent,a)!=find_parent(parent,b):
        union_parent(parent,a,b)
        #비용 더하기
        result+=cost
     
print(result)

 

시간복잡도: 간선이 E개일 때 O(ElogE).

간선을 정렬하는 작업이 가장 오래걸리는 부분. E개의 데이터를 정렬하는데 걸리는 시간은O(logE)이다.