[Algorithm] 그래프 알고리즘 비교(MST, kruskal, prim, dijkstra, floyd-warshall, bellman-ford)
.compare Graph Algorithms .MST(Minimum Spanning Tree), 최소신장트리 정점 -1개의 간선으로 이루어진 신장트리 중에서 가중치의 합이 가장 작은 것고르는 간선은 사이클을 만들지 않아야 하고, 가중치가 작은 것들부터 골라져야 함 * 절대적이진 않지만, 간선이 적으면 KRUSKAL, 간선이 많으면 PRIM 알고리즘이 유리 .KRUSKAL (간선을 고르는 간선 중심)MST 의 목적을 이루기 위해 간선들을 가중치 오름차순으로 정렬해두고,사이클을 만들지 않는 간선이라면 골라나가서 N-1 개를 고르면 완료참고 ㅇ Use edgeList12345678910111213141516171819202122232425262728293031323334353637383940414243444..
PS/Algorithm
2020. 10. 13. 10:46