1
Kruskal의 알고리즘이 BFS를 사용하여 사이클을 생성하면서 에지를 추가하는지 확인하기 위해 구현 된 경우, 알고리즘의 전체 Big-O 실행 시간은 얼마입니까?BFS를 사용하여 가장자리를 추가하면 순환이 생성되는지 여부를 확인하는 경우 Kruskal 알고리즘의 전체 Big O 실행 시간은 어떻게됩니까?
A
답변
4
O(V * E + E * log E)이됩니다. 각 BFS는 V - 1 에지가 트리에 있거나 트리가 아직 완전히 빌드되지 않은 경우 더 적으며 각 에지에 대해 실행되기 때문에 O(V) 시간이 걸립니다 (V은 정점 수이며, E은 에지 수입니다). 그래서 그것은 O(V * E)입니다. E * log E 용어는 가장자리 정렬에서옵니다.
+0
새 후보 에지에서 정점 중 하나 인 소스 정점을 가져 와서 다른 정점이 이미 있는지 확인하여 BFS를 수행해야한다고 추가해야합니다 그것으로부터 도달 할 수 있습니다. 이는 부분적으로 구성된 MST가 Kruskal의 알고리즘에서 분리되어야하기 때문입니다. –
왜 그렇게 했습니까? 가장자리를 추가하면 일정한 시간에 사이클이 생성되는지 알 수 있습니다. 이 곳에 O (BFS)를 꽂고 자신을보십시오. – luk32
@ user3910703 당신이 diba miriza와 함께 cse100을 가지고 있다고 말할 수 있습니다. – penu