0
My Algorithms 클래스는 가중치 그래프의 최소 스패닝 트리를 찾는 방법으로 Prim의 알고리즘에 대해 설명합니다. 교수님은 Prim 's Algorithm이 풀기 위해 N^2 시간 (N = Vertices 수)이 걸리는 그래프의 예를 생각해 보라고했습니다. 수업 중에 아무도 머리 꼭대기에서 벗어난 사람을 생각할 수 없습니다. 그래서 나는 당신에게 묻고 있습니다. 저는 Prim 's Algorithm = O (N^2)라고 확신합니다. 그래서 이것은 알고리즘의 최악의 시나리오 일 것입니다.Prim의 알고리즘에 대한 최악의 경우 그래프
Prim의 알고리즘이 풀리기 위해 N^2 시간이 걸리는 그래프의 좋은 예는 무엇입니까?
그래프가 완성되면 'O (N^2)'에지가 있기 때문에 그래프를 읽는 것만으로 'O (N^2)'가됩니다. – kraskevich