Ich versuche zu verstehen, warum Prim und Kruskal unterschiedliche Zeitkomplexitäten haben, wenn es um spärliche und dichte Graphen geht. Nachdem ich ein paar Applets benutzt habe, die zeigen, wie es funktioniert, bin ich immer noch etwas verwirrt darüber, wie sich die Dichte des Graphen auf die Algorithmen auswirkt. Ich hoffe, jemand könnte mir einen Schubs in die richtige Richtung geben.
Wikipedia gibt die Komplexität dieser Algorithmen in Bezug auf E , die Anzahl der Kanten und V , die Anzahl der Ecken, was eine gute Übung ist, weil es erlaubt Du machst genau diese Art von Analyse.
Kruskals Algorithmus ist O ( E log V ). Die Komplexität von Prim hängt davon ab, welche Datenstruktur Sie dafür verwenden. Unter Verwendung einer Adjazenzmatrix ist es O ( V 2 ).
Wenn Sie nun V 2 für E einstecken, erhalten Sie die Komplexitäten, die Sie in Ihrem Kommentar für dichte Graphen und Wenn Sie V für E einbinden, erhalten Sie die spärlichen.
Warum verbinden wir V 2 für einen dichten Graphen? Nun, selbst im dichtest möglichen Graphen kann man nicht mehr als V 2 Kanten haben, also klar E = O ( V 2 ).
Warum verbinden wir V für ein dünnes Diagramm? Nun, Sie müssen definieren, was Sie mit spärlich meinen, aber nehmen wir an, wir nennen ein Diagramm spärlich, wenn jeder Eckpunkt nicht mehr als fünf Kanten hat. Ich würde sagen, solche Graphiken sind ziemlich spärlich: Sobald Sie in die Tausende von Vertices aufsteigen, wäre die Adjazenzmatrix größtenteils leerer Raum. Das würde bedeuten, dass für spärliche Graphen E ≤ 5 V ist, also E = O ( V ).
Sind diese verschiedenen Komplexitäten in Bezug auf die Anzahl der Ecken zufällig?
Es gibt oft ein leicht handgewelltes Argument, das für einen dünnen Graphen die Anzahl der Kanten E = O (V) angibt, wobei V die Anzahl der Vertices für einen dichten Graphen E = O (V ^ 2) ist. Da beide Algorithmen potentiell eine Komplexität haben, die von E abhängt, erhalten Sie, wenn Sie dies in eine von V abhängige Komplexität umwandeln, unterschiedliche Komplexitäten, abhängig von dichten oder spärlichen Graphen
bearbeiten:
verschiedene Datenstrukturen werden auch die Komplexität des Kurses beeinflussen wikipedia hat eine Panne auf diese
Die Algorithmen von Cormen et al. geben in der Tat eine Analyse, wobei in beiden Fällen eine spärliche Darstellung des Graphen verwendet wird. Mit dem Algorithmus von Kruskal (Verknüpfungsscheitelpunkte in disjunkten Komponenten, bis alles zusammengefügt ist) besteht der erste Schritt darin, die Kanten des Graphen zu sortieren, was Zeit (E lg E) benötigt und einfach feststellt, dass nichts länger als das dauert. Mit dem Prim-Algorithmus (den aktuellen Baum durch Hinzufügen des nächsten nicht vorhandenen Eckpunkts erweitern) verwenden sie einen Fibonacci-Heap, um die Warteschlange ausstehender Scheitelpunkte zu speichern und O (E + V lgV) zu erhalten, da bei einem Fibonacci-Baum die Entfernung zu Scheitelpunkten abnimmt in der Warteschlange ist nur O (1) und du machst das höchstens einmal pro Kante.
Tags und Links algorithm graph kruskals-algorithm prims-algorithm