kruskal algorithms

1. Kruskal Algorithms?- Greedy Algorithms을 이용하여 MST를 찾아내는 알고리즘이다.- 앞서 알아봤던 Prim Algorithms과 동일하다. 2. 과정- 1) 그래프의 엣지들을 가중치의 오름차순으로 정렬- 2) 정렬된 엣지 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택함-- 가장 낮은 가중치를 먼저 선택-- 사이클을 형성하는 엣지 제외(Disjoint set을 이용함)-3) 해당 엣지를 현재의 MST에 추가한다.- 해당 그래프에서의 MST를 구하는 Kruskal Algorithms을 구현해보자. 3. 코드 구현def Kruskal(edges,vertexes): edge_count = 0 total_weight = 0 result_list = []..
23학번이수현
'kruskal algorithms' 태그의 글 목록