krukshal 알고리즘 또는 Prims Algorithm으로 최소 스패닝 트리를 찾는 것이 좋습니다.

Question

가능한 중복 :
Kruskal vs Prim

krukshal의 알고리즘 또는 프림 알고리즘 어느 최소 스패닝 트리를 찾는 데 더 나은 무엇입니까?

Answer 1

나는 Prim의 알고리즘에 찬성하여 한 점을 추가 할 것이다. 나는 언급하지 않았다. x와 y 사이의 거리에 N 포인트와 거리 함수 d (x, y)가 주어지면 공간 O (N)을 사용하여 Prim의 알고리즘을 구현하는 것이 쉽습니다 (단 N^2 시간).

임의의 점 A부터 시작하여 A에서 다른 모든 점까지의 거리를 제공하는 크기 N-1의 배열을 만듭니다. 스패닝 트리에서 최단 거리와 연관된 점 B와 링크 A와 B를 선택한 다음 배열의 거리를 다른 점까지 이미 기록 된 거리의 최소값으로 업데이트하고 다른 점에서 거리를 업데이트합니다 가장 짧은 링크가 B에서 어디이고 A. Carry가 어디에서 왔는지를 지적합니다. 당신이 시간 동안 인내심이 부족하기 전에 (N^2)

나는 거리 함수에 의해 지정된 밀도 그래프 크루스 칼의 알고리즘을 처리하는 유사한 방법을 알고하지 않으며, 큰 N 당신은 공간 O에서 실행할 수 있습니다 O (N^2).