천천히 빛나는

크루스칼 알고리즘프림 알고리즘https://shine-slowly.tistory.com/96 알고리즘: 최소 신장 트리(MST) (1) - 크루스칼(Kruskal) 알고리즘크루스칼 알고리즘프림 알고리즘Minimum Spanning Tree (최소 신장 트리)그래프의 모든 정점을 포함하는 트리를 신장트리(Spanning Tree)라고 한다.그래프의 최소 연결 부분 그래프로 사이클이 없다. (위shine-slowly.tistory.com최소 신장 트리에 대한 이해가 필요하다면 여기로! 크루스칼을 살짝 정리하고 넘어가자면,간선의 정보를 저장하고, 간선을 기준으로 정렬해서 앞에서부터 연결을 하게 된다. (연결이 되었으면 넘어감)간선이 중심인 알고리즘이다. 프림(Prim) 알고리즘1. 시작 정점을 정해 우선 순위..

크루스칼 알고리즘프림 알고리즘Minimum Spanning Tree (최소 신장 트리)그래프의 모든 정점을 포함하는 트리를 신장트리(Spanning Tree)라고 한다.그래프의 최소 연결 부분 그래프로 사이클이 없다. (위 사진에서는 4개로 모두 연결 가능 = 정점이 5개니까 5-1개) 여기서 가중치 합이 가장 최소인 신장트리를 최소 신장 트리라고 한다.  크루스칼(Kruskal) 알고리즘그래프의 간선을 하나씩 늘리면서 MST를 만든다. 가중치가 최소인 간선부터 선택하는 방법으로 진행한다. 1) 모든 간선을 가중치에 따라 오름차순 정렬을 한다.2) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다. 사이클이 존재하면 다음으로 가중치가 낮은 간선을 선택한다.3) 모두 선택될 때까지 2번을 반복한다...