Welche Art von Problemen in Graphen ist schneller (in Bezug auf Big-O) zu lösen, indem Inzidenzmatrixdatenstrukturen anstelle von weiter verbreiteten Adjazenzmatrizen verwendet werden?Inzidenzmatrix anstelle von Adjazenzmatrix
der Raum Komplexität der Strukturen sind:
Adjacency: O (V^2) Incidence: O (VE)
mit der Folge, dass eine Einfallsstruktur spart Platz, wenn es viele weiteren Eckpunkte als Kanten.
Sie können die Zeit Komplexität einiger typischer Graph Operationen buchen:
alle Knoten zu einem Eckpunkt benachbarten Finde: Adj: O (V) Inc: O (VE)
Überprüfen Sie, ob zwei Eckpunkten benachbart sind: Adj: O (1) Inc: O (E)
die Wertigkeit eines Scheitels Count: Adj: O (V) Inc: O (E)
Und so weiter. Für jeden gegebenen Algorithmus können Sie Bausteine wie oben verwenden, um zu berechnen, welche Darstellung Ihnen eine bessere Gesamtzeitkomplexität gibt.
Als letzte Anmerkung ist die Verwendung einer Matrix jeder Art extrem platzineffizient für alle außer die dichtesten Graphen, und ich empfehle gegen die Verwendung entweder, wenn Sie bewusst Alternativen wie Adjazenzlisten entlassen haben.
Ich habe sehr dichte Graphen mit fast jeder Verbindung. – psihodelia
Gibt es keine Möglichkeiten, Sparse-Matrix effizient zu speichern? – CMCDragonkai
Ich persönlich habe nie eine echte Anwendung der Inzidenzmatrix-Darstellung in einem Programmierwettbewerb oder Forschungsproblem gefunden. Ich denke, das kann nützlich sein, um einige Sätze oder einige sehr spezielle Probleme zu beweisen. Ein Buch gibt ein Beispiel zum "Zählen der Anzahl von Spannbäumen" als ein Problem, bei dem diese Darstellung nützlich ist.
Ein weiteres Problem mit dieser Darstellung ist, dass es keinen Sinn macht, es zu speichern, weil es wirklich einfach ist, es dynamisch aus der Liste der Kanten zu berechnen (um die gegebene Zelle zu beantworten).
Es mag jedoch in Hyper-Graphen nützlicher erscheinen, aber nur wenn es dicht ist.
Also meine Meinung ist - es ist nur für theoretische Arbeiten nützlich.
Ich bin nicht zuversichtlich, dass es einfach ist, eine rechnerische Obergrenze basierend auf der zugrunde liegenden Darstellung zu finden. Der größte Teil der algorithmischen Komplexität wird sich auf die _number_ von Kanten oder Vertices beziehen, nicht auf die zugrunde liegende Repräsentation. Jede Untergrenze für die Komplexität wird gelten, unabhängig davon, ob sie auf Papier und Bleistift oder auf einem Computer implementiert ist. Denken Sie, wenn es bestimmte Klassen von Problemen gibt, die Sie im Sinn haben, dann vielleicht erwähnen Sie diese und wir können versuchen, es herauszufinden? – Gian
Inzidenzmatrix ist MxN und Adjazenzmatrix ist NxN Wenn N sehr groß ist und Ihr Diagramm sehr spärlich ist, haben Sie MxN