Ich habe ein ungerichtetes Diagramm mit Vertex V und Edge E . Ich suche nach einem Algorithmus, um alle Zyklusgrundlagen in diesem Diagramm zu identifizieren.
Ich denke, Tarjans-Algorithmus ist ein guter Anfang. Aber die Referenz , die ich habe, heißt, alle Zyklen zu finden , nicht Zyklusbasis ( Definitionsgemäß ist der Zyklus, der nicht durch Vereinigung anderer Zyklen konstruiert werden kann.
Sehen Sie sich zum Beispiel die folgende Grafik an:
Also wäre ein Algorithmus hilfreich. Wenn es eine existierende Implementierung gibt (vorzugsweise in C #), ist es sogar noch besser!
Von dem, was ich sagen kann, ist nicht nur Brians Vorurteil, sondern ein noch stärkerer Vorschlag: jede Kante, die nicht im minimalen Spannbaum ist, fügt genau einen neuen "Basiszyklus" hinzu.
Sehen wir uns an, was passiert, wenn Sie eine Kante E hinzufügen, die nicht in der MST enthalten ist. Lassen Sie uns die beste mathematische Methode anwenden, um Dinge zu komplizieren und eine Notation hinzuzufügen;) Rufen Sie den ursprünglichen Graphen G, den Graphen vor dem Hinzufügen von E G 'und den Graphen nach dem Hinzufügen von E G' 'auf. Also müssen wir herausfinden, wie sich die "Grundzykluszahl" von G 'nach G' ändert.
Das Hinzufügen von E muss mindestens einen Zyklus schließen (andernfalls würde E an erster Stelle in der MST von G stehen). Also muss natürlich zu den bereits vorhandenen in G 'mindestens ein "Basiszyklus" hinzugefügt werden. Aber fügt es mehr als eins hinzu?
Es können nicht mehr als zwei hinzugefügt werden, da keine Kante Mitglied von mehr als zwei Basiszyklen sein kann. Aber wenn E ein Mitglied von zwei Basiszyklen ist, dann muss die "Vereinigung" dieser zwei Basiszyklen ein Basiszyklus in G 'gewesen sein, so dass wiederum die Änderung in der Anzahl der Zyklen immer noch eins ist. p>
Ergo, für jede Kante, die nicht in MST ist, erhalten Sie einen neuen Basiszyklus. Der Teil "count" ist also einfach. Das Finden aller Kanten für jeden Basiszyklus ist ein wenig komplizierter, aber ich folge dem obigen Gedankengang, ich denke, dies könnte es (in Pseudo-Python) tun:
%Vor%Bearbeiten : Der Code sollte alle Basiszyklen in einem Diagramm finden (die unten angegebenen base_cycles). Die Annahmen sind, dass Sie wissen:
Und es folgt hauptsächlich der obigen Diskussion. Für jede Kante, die nicht in der MST ist, gibt es zwei Fälle: entweder bringt sie einen komplett neuen Basiszyklus, oder sie teilt einen vorhandenen in zwei Teile auf. Um zu verfolgen, welcher der beiden Fälle der Fall ist, verfolgen wir alle Basiszyklen, zu denen ein Eckpunkt gehört (unter Verwendung des Zyklen-Wörterbuchs).
Aus der Spitze meines Kopfes, würde ich mit der Suche nach einem Minimum Spanning Tree Algorithmus (Prim, Kruskal, etc) beginnen. Es kann nicht mehr Basiszyklen geben (wenn ich es richtig verstehe) als Kanten, die NICHT in der MST sind ....
Das Folgende ist mein tatsächlicher ungetesteter C # -Code, um alle diese "Basiszyklen" zu finden:
%Vor%Oggy's Code war sehr gut und klar , aber ich bin mir ziemlich sicher, dass er einen Fehler enthält, oder ich verstehe Ihren Pseudo-Python-Code nicht:)
%Vor%kann kein vertex-indexiertes Wörterbuch von Kantenlisten sein. Meiner Meinung nach muss es ein vertex-indexiertes Wörterbuch von Listensätzen von Kanten sein.
Und um eine Präzisierung hinzuzufügen:
%Vor%cycle-to-split ist wahrscheinlich eine geordnete Liste von Kanten, um sie durch Scheitelpunkte zu iterieren, müssen Sie sie in einer Menge von Scheitelpunkten konvertieren. Ordnung hier ist vernachlässigbar, also ist es eine sehr einfache Algorithm.
Ich wiederhole, das ist ungeprüfter und unvollständiger Code, ist aber ein Schritt vorwärts. Es erfordert immer noch eine geeignete Graphenstruktur (ich benutze eine Liste von Arbeitsstellen) und viele Graph-Algorithms, die man in Lehrbüchern wie Cormen finden kann. Ich konnte FindPath () und SplitCycle () nicht in Textbüchern finden und bin sehr schwer in der linearen Anzahl der Kanten + Scheitelpunkte im Diagramm zu codieren. Werde sie hier melden, wenn ich sie testen werde.
Vielen Dank Oggy!
Die Standardmethode zur Erkennung eines Zyklus besteht darin, zwei Iteratoren zu verwenden - für jede Iteration wird einer um einen Schritt vorwärts bewegt und die anderen beiden. Sollte es einen Zyklus geben, werden sie irgendwann zueinander zeigen.
Dieser Ansatz könnte erweitert werden, um die gefundenen Zyklen aufzuzeichnen und weiterzugehen.
Tags und Links graph-theory graph