minhas2   6년 전

틀렸다는게 제가 프림알고리즘 자체를 잘못 이해하고 있다는것같은데

임의의 시작정점에서 연결된 정점들의 가중치들을 거리배열(distance)에 수정하고,

연결된 정점들중 가장 가중치가 작은 정점을 선택해서 그 정점과 연결된 정점들의 가중치들을 거리배열에 수정하는데, 기존의 가중치보다 작은경우 수정하는 방식을 계속 반복해서

최종적으로 모든 정점들을 방문했을때의 배열 distance[시작정점]을 제외한 모든값들의 합이 최종적으로 최소스패닝트리의 값아닌가요?

아니면 이방식이 맞는데 제가 구현을 잘못한건지.. ㅜㅜ 도와주세용

atomzeno   6년 전

잘은 모르겠는데 프림 알고리즘을 잘못 이해하신 듯 합니다. 

프림 알고리즘은 현재 정점 집합에서 연결되지 않은 정점 집합으로 가는 간선들중 최솟값을 선택하는 방식일겁니다.


minhas2   6년 전

프림알고리즘이 모든 정점들을 방문할 때의 최소비용을 구할때 쓰는 알고리즘으로 알고있는데

그러면 현재 정점집합에서 간선으로 연결된 방문하지 않은 정점으로 갈때의 가중치를 비교하면서 정점집합에 추가하는 방식 아닌가요..?

atomzeno님께서는 간선으로 연결되지 않은 정점들도 모두 같이 탐색해야한다는 말씀이신가요?

댓글을 작성하려면 로그인해야 합니다.