Ich benutze den DFS Algorithmus und möchte jede Kante als besucht markieren. Ein Ansatz wäre, nach dem Knoten zu suchen und ihn durch einen Sentinel zu ersetzen, aber das wäre teuer, wenn ich eine Adjazenzliste mache Speichere den Wert, der dem besuchten Knoten entspricht, der die Suchzeit erhöhen würde. Eine Matrix würde viel Speicherplatz verbrauchen. Was ist der beste Algorithmus dafür?Kanten in einem Graphen betrachten
Sie müssen nur eine Reihe von Vertex-Paaren pflegen. Zum Beispiel in Java HashMap<Pair<Vertex, Vertex>>. In Python, ein Set von 2-Element Tupeln.
Der Besuch einer Kante tritt auf, wenn Sie die Nachkommen eines gerade gefundenen neuen Scheitelpunkts aufzählen und zum DFS-Stapel hinzufügen. Wenn Sie ein rekursives DFS verwenden, geschieht dies, indem Sie einen rekursiven Aufruf für jeden Nachkommen ausführen. Hier ist die Stack-Version:
dfs(graph)
visitedVertices = \emptyset
visitedEdges = \emptyset
// Try all vertices as search roots
for each vertex r in graph
push r onto empty stack
while notEmpty(stack)
u = pop stack
if u not in visitedVertices
add u to visitedVertices
foreach v such that u->v is in graph
add (u,v) to visitedEdges // Visit the edge
push v on stack
Nachdem gesagt, ich bin mir nicht sicher, warum Sie das tun möchten. Ein korrekt implementiertes DFS durchläuft natürlich jede Kante genau einmal. Sie können dies selbst beweisen, indem Sie sich den obigen Algorithmus ansehen. Der Besuch von (u,v) ist nur möglich, wenn u noch nie zuvor besucht wurde.
Vielleicht haben Sie einen anderen Thread, der den Fortschritt der Suche beobachtet oder während des Besuchs tatsächlich andere Informationen zu den Kanten hinzufügt?
Ich möchte einen Graph Euler Schaltung durch Umleiten von Kanten und Fleury Algorithmus ist zu komplex (zeitaufwendig) für meine Einschränkung, kann ich nicht leisten, eine Kante entfernen und dfs erneut anwenden, um zu überprüfen, ob es Bridge oder nicht war. Denken Sie über Algorithmus scheitert in einem Fall, wenn ich versuche, den Knoten mehr als einmal zu besuchen? und wenn 1-> 2 markiert ist, ist eine Kante 2-> 1 immer noch möglich, weil es nicht in markierten Kanten war, aber das würde eine ungerichtete Kante erzeugen? – idk
@idk Es tut mir leid, ich kann nicht verstehen, was Sie fragen. – Gene
Bei einer Euler-Schaltung, die verzerrt ist, wurden die Kanten neu angeordnet, und ich möchte sie noch einmal in eine neue Schaltung umwandeln, indem ich die Kanten umordne, die in falscher Reihenfolge angeordnet wurden, um den Graph-Euler-Schaltkreis zu bilden. – idk
Müssen Sie Kanten als besucht aufzeichnen? Damit Sie eine Kante zweimal durchlaufen können, müssen Sie zweimal denselben Knoten durchlaufen haben. Der Überblick über besuchte Knoten sollte einfacher sein. Was genau versuchst du zu tun? –
@ A.Sokol ich besuche eine Kante und ich muss es aufzeichnen, so würde ich nicht wieder besuchen, obwohl ich würde, wenn Fall wie dies existiert 1-> 2 && 2-> 1.Ich muss die Reihenfolge, in der Ich besuche die Kante, also muss ich sie speichern. – idk
Warum drucken Sie es nicht so, wie Sie es tun? – CodingYoshi