[Python] 그래프 최소비용 탐색 - JuyeolRyu/CodingTest GitHub Wiki

1.Kruskal 알고리즘

그래프의 최소 탐색비용을 구하는 알고리즘

2.Kruskal 알고리즘 실행 과정

그래프를 간선비용 기준으로 오름차순 정렬한다.
그래프의 모든 노드가 연결될때 까지 간선을 연결한다.
간선을 연결할때 마다 그래프에 사이클이 생기는지 확인하고 사이클이 생기면 다음 간선으로 넘어간다.
간선 연결은 union-find 알고리즘을 사용한다.

이미지 참고 : https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

3.Kruskal 알고리즘 코드

#그래프의 root를 찾는다.
def find(x):
  if x != parent[x]:
      parent[x] = find(parent[x])
  return parent[x]
#두개의 그래프를 합친다.
def union(x,y):
  x = find(x)
  y = find(y)
  if x<y:
      parent[y] = x
  else:
      parent[x] = y

ans = 0
graph = [[노드1,노드2,cost],[노드1,노드2,cost],[노드1,노드2,cost],...]
graph = sorted(graph, key = lambda x:x[2])
#각 노드의 root저장할 리스트
parent = [i for i in range(노드개수+1)]

#탐색
while graph:
  u,v,c = graph.pop(0)
  #두개의 트리가 같은 root를 가지고 있는 경우 continue
  if find(u) == find(v):
    continue
  #다른 루트를 가진다면 합쳐준다.
  else:
    union(u,v)
    ans += c

4.Kruskal 알고리즘 문제

추가

Union&Find