Worst-Case-Graph für Prim-Algorithmus

Question

Meine Algorithmen-Klasse spricht über Prim-Algorithmus als eine Methode zum Auffinden von Minimum Spanning Trees gewichteten Graphen. Unser Professor hat uns gebeten, ein Beispiel für ein Diagramm zu finden, das Prims Algorithmus braucht, um N^2 zu lösen (N = Anzahl der Vertices). Niemand in der Klasse konnte sich einen Kopfweiler vorstellen, also frage ich dich. Ich bin mir ziemlich sicher, Prims Algorithmus = O (N^2), also wäre dies das Worst-Case-Szenario für den Algorithmus.

Was ist ein gutes Beispiel für ein Diagramm, das braucht N^2 Zeit für Prims Algorithmus zu lösen?

Answer 1

Wenn ich Ihre Frage richtig verstehe, ist das Beispiel trivial.

Wenn das Diagramm abgeschlossen ist, gibt es O(N^2) Kanten, also nur das Lesen der Grafik ist O(N^2).