Prim's algorithm을 C (www.bubblellicious.es/prim.tar.gz)에 구현했지만, 이것을 Kruskal's algorithm으로 변환하는 방법을 궁금합니다.Prim의 알고리즘을 Kruskal의 알고리즘으로 변환하는 방법은 무엇입니까?
그들은 꽤 비슷해 보이지만 어떻게하면 기존 코드를 새 코드로 수정할 수 있을지 상상할 수 없습니다. 네가 조언이나 뭔가를 주면 맛있어 질거야. 쉽게 알 수 있겠지만 C 프로그래밍의 n00b입니다 ...
Kruskal을 처음부터 작성하고 자신의 솔루션에서 어떻게 비교하는지보십시오. 배우는 가장 좋은 방법.
변환하려면 단일 트리가 아닌 임시 출력 구조로 포리스트 (즉, 처음에는 각 노드가 트리 인 트리 집합)가 필요합니다. 그런 다음 각 단계에서 현재 연결되지 않은 노드를 트리에 추가하는 가장 저렴한 버텍스를 찾는 것보다 그래프에서 가장 싼 에지를 찾고 새 트리를 만들면 (즉, 두 개의 이전에 연결되지 않은 노드를 연결하는 경우) 해당 트리를 소스 나무를 제거하십시오. 그렇지 않으면 가장자리를 버립니다. Kruskal의 적절한 구현은 적절한 Prim 구현보다 메모리 집약적이지만 시간 집약적입니다.
하지만 둘 사이의 차이는 상당히 큽니다. 아마 여러분이 간직 할 수있는 것은 도우미 기능과 일부 데이터 구조입니다. 전환이 아니라 더 높은 수준의 빌딩 블록을 사용하여 다시 작성합니다.
왜 C++로 전환하고 부스트 그래프 라이브러리를 사용 하시겠습니까? (http://www.boost.org/)?
두 알고리즘에 대한 구현이 매우 잘 포함되어 있습니다. 유형 안전하고 고성능입니다. kruskal_minimum_spanning_tree 및 prim_minimum_spanning_tree
질문에 관련 코드를 삽입하면 유용한 응답을 얻게됩니다. Prim의 알고리즘은 단지 4 줄의 의사 코드이므로 여섯 개의 파일로 구성된 tarball이 필요하다고는 생각하지 않습니다. –
음, 메인 파일 만 읽을 수 있습니다. 모든 파일을 볼 필요는 없습니다. –
IMHO 이러한 알고리즘은 하나에서 다른 것으로 변환하는 것이 유리합니다. Kruskal에는 일종의 우선 순위 대기열이 필요하지만 Kruskal에는 전역 정렬 된 가장자리 목록이 필요합니다. 당신은 처음부터 시작하는 것이 좋습니다. –