Prim 또는 Kruskal의 알고리즘을 유향 그래프에 사용할 수없는 이유는 무엇입니까?

Question

Prim 및 Kruskal의 알고리즘은 연결되어 있고 전달되지 않은 그래프의 최소 스패닝 트리를 찾는 데 사용됩니다. 왜 그들이 지시 된 그래프에 사용될 수 없습니까?

Answer 1

이러한 알고리즘이 처음부터 작동한다는 것은 기적입니다. 대부분의 욕심 많은 알고리즘은 일부 인스턴스에서 충돌하고 화상을 입습니다. 최소 스패닝 arborescence (하나의 버텍스에서 다른 버텍스로 향하는 경로)를 찾기 위해 그것들을 사용한다고 가정하면, Kruskal에 대한 하나의 문제가되는 그래프는 다음과 같습니다.

5 
    --> a 
//^ 
s 1| |2 
\ v/
    --> b 
3 

우리는 A-> 비용 1의 B 아크 할게요, 우리는 정말 비용 3의 b를 S-> 원했기 때문에 박히과 프림을 위해 B-> 비용의 2

이 그래프는 문제가됩니다.

5 
    --> a 
//
s 1| 
\ v 
    --> b 
3 

우리는 비용 3의 b를 S-> 할게요,하지만 우리는 정말 비용이 5 A->의 1

Answer 2

프림의와 크루스 칼의 알고리즘 출력 최소 비용 b>을 S- 원 연결된 "무 방향"그래프에 대한 스패닝 트리. 연결되어 있지 않은 경우 최소 스패닝 포리스트를 출력하도록 조정할 수 있습니다.

Prim의 알고리즘에서 그래프를 두 세트의 정점으로 나눕니다. 이미 MST (Set1)를 형성 한 탐색 된 꼭지점 중 하나와 궁극적으로 "스패닝"(Set2)을 완료하기 위해 첫 번째 세트에 합류하는 미개척 점 집합입니다. 매 순간마다 두 개의 분리 된 세트를 결합하는 컷에서 최소 가중 에지를 선택합니다. MST 탐색 노드에서 탐색되지 않은 탐색 에지로 향하는 에지가 없다면 탐색되지 않은 노드에서 MST 탐색 노드까지의 에지가 있어도 알고리즘이 멈추게됩니다.

Kruskal의 알고리즘에서 가중치에 따라 오름차순으로 가장자리를 정렬하고 순서대로 선택하여 탐색 된 노드가 이미주기를 형성하지 않으면 MST 탐색 노드/가장자리에 포함합니다. 이는 Union-Find DS가 수행합니다. 그러나이 방법을 사용하면 유향 그래프의주기 감지가 실패합니다. 예 : 가장자리 [1-> 2] [2-> 3] [1-> 3]을 포함하는 그래프는 Union-Find 메소드가있는 사이클을 포함하는 것으로보고됩니다.

그래서 프리즘은 가정하기 때문에 실패합니다. 모든 노드는 모든 노드에서 도달 할 수 있지만 방향이없는 그래프에 대해서는 유효하지만 다이 그래프에서는 참이 아닐 수도 있습니다. Kruskal은 사이클을 감지하지 못해 실패하고 때로 MST의 "최소"가중 속성을 충족시키는 사이클을 만드는 에지를 추가하는 것이 필수적입니다.

또한 이중 그래프의 경우 MST가 완전하지 않습니다. 쌍극자에 해당하는 것은 "최소 스패닝 arborescence"입니다. 이것은 하나의 정점에서 모든 정점에 도달 할 수있는 트리를 생성합니다.