는 말한다 :최소 확장 포리스트를 찾는 데 사용되는 알고리즘은 무엇입니까? 위키 백과으로
최소 걸쳐 숲 의 연결 구성 요소의 최소 스패닝 트리의 조합이다. 우리가 예를 Prim's algorithm, Kruskal's algorithm, 또는 Borůvka's algorithm에 사용할 수있는 최소 스패닝 트리를 찾는
.
최소 확장 포리스트를 찾기 위해 어떤 알고리즘을 사용할 수 있습니까?
나무에 사용하는 것보다 다른 알고리즘을 어떻게 필요로하는지 알지 못합니다. 조금 적응해야 할 수도 있습니다.
예를 들어 Kruskal 알고리즘을 사용하면 모든 하위 그래프/최소 스패닝 트리에서 가장 저렴한 에지를 얻을 수 있습니다. 또는 Prim의 알고리즘을 사용할 수 있습니다. 반복이 중지되면 아직 연결되지 않은 노드 (즉, 다른 트리)로 다시 시작하십시오.
한 문장으로 "최소 스패닝 포리 스트를 찾는 데 사용되는 알고리즘은 최소 스패닝 트리를 찾는 데 사용되는 알고리즘과 동일합니다. 일부 경우 적응 및 경우에 따라서는 사용하지 않는 것이 좋습니다."
동일한 알고리즘이 연결된 각 구성 요소에 별도로 적용됩니다. –