kruskal1

• 

  210708 최소 신장 트리 with Kruskal, Prim 알고리 최소 신장 트리 (Minimum Spannig Tree, MST) 신장 트리(spanning Tree) 중에서 사용된 간선들의 가중치 합이 최소인 트리 //신장 트리(spanning Tree) : 모든 정점을 포함하고, 정점 간 서로 연결이 되며 사이클이 존재하지 않는 그래프 Kruskal, Prim 알고리즘은 최소 신장 트리를 구하기 위한 알고리즘 Kruskal 모든 간선들 중에서 가중치가 가장 낮은 간선부터 선택하는 방식 단, 선택하는 과정에서 사이클이 만들어지는 경우에는 선택하지 않는다 n개의 정점을 가지는 그래프일 경우, n-1 개의 간선 선택하면 종료 시간복잡도 : 간선을 오름차순으로 정렬하는 것에 수행시간 좌우되기에 최선의 선택을 한다고 가정하면, O((간선의 수) * log_2 (간선의 수).. 미가공 필기(알고리즘) 2021. 7. 10.