Ich habe eine Programmieraufgabe (keine Hausaufgaben), wo ich die Brücken in einem Graphen finden muss. Ich habe selbst ein wenig daran gearbeitet, konnte mir aber nichts Befriedigendes einfallen lassen. Also habe ich es gegoogelt, ich habe etwas gefunden, aber ich kann den Algorithmus nicht verstehen, wie er dargestellt wird. Könnte jemand bitte diesen Code ansehen und mir eine Erklärung geben? "
%Vor%Def: Bridge ist eine Kante, die beim Entfernen den Graphen trennt (oder die Anzahl der verbundenen Komponenten um 1 erhöht).
Eine Beobachtung bezüglich Brücken im Graphen; Keine der Kanten, die zu einer Schleife gehören, kann eine Brücke sein. In einem Diagramm wie A--B--C--A wird das Entfernen der Kanten A--B , B--C und C--A die Grafik nicht trennen. Bei einem ungerichteten Graph bedeutet die Kante A--B jedoch B--A ; und diese Kante könnte immer noch eine Brücke sein, wobei die einzige Schleife, in der sie sich befindet, A--B--A ist. Wir sollten also nur die Schleifen betrachten, die von einer hinteren Kante gebildet werden. Hier hilft die übergeordnete Information, die Sie im Funktionsargument übergeben haben. Es wird Ihnen helfen, die Schleifen wie A--B--A nicht zu verwenden.
Um nun die hintere Kante (oder die Schleife) A--B--C--A zu identifizieren, verwenden wir die Arrays low und pre . Das Array pre ist wie das visited Array im dfs-Algorithmus; aber anstatt nur den Scheitelpunkt als besucht zu kennzeichnen, identifizieren wir jeden Scheitelpunkt mit einer anderen Nummer (entsprechend seiner Position im dfs-Baum). Das low -Array hilft dabei, festzustellen, ob eine Schleife vorhanden ist. Das low -Array identifiziert den Knoten mit der niedrigsten Nummer (ab pre -Array), den der aktuelle Scheitelpunkt erreichen kann.
Läßt uns durch dieses Diagramm A--B--C--D--B arbeiten.
Beginnend bei A
%Vor% An diesem Punkt haben Sie einen Zyklus / eine Schleife in der Grafik gefunden. In deinem Code wird if (pre[w] == -1) dieses Mal falsch sein. Sie betreten also den else-Teil. Die if-Anweisung überprüft, ob B der übergeordnete Scheitelpunkt von D ist. Dies ist nicht der Fall, also D wird B s pre -Wert in low aufnehmen. Fahren Sie mit dem Beispiel fort,
Dieser low -Wert von D wird über den Code C an low[v] = Math.min(low[v], low[w]); weitergegeben.
Nun, da der Zyklus / die Schleife identifiziert ist, stellen wir fest, dass der Vertex A nicht Teil der Schleife ist. Also drucken Sie A--B als Brücke aus. Der Code low['B'] == pre['B'] bedeutet, dass eine Kante zu B eine Brücke ist. Dies liegt daran, dass der kleinste Vertex, den wir von B erreichen können, B selbst ist.
Ich hoffe, diese Erklärung hilft.
Keine neue Antwort, aber ich brauchte das für die JVM / Kotlin. Hier ist eine Übersetzung, die sich auf com.google.common.graph.Graph stützt.
Hoffentlich erleichtert dies jemandem das Leben.