Ich habe Probleme beim Implementieren (nicht Code) DFS mit dem Bi-Komponenten-Algorithmus, um Artikulationspunkte in einem Graphen zu finden, der Algorithmus wurde in meiner Vorlesung vorgestellt verstehe die Implementierung nicht. (Nur um zu verdeutlichen, dass ich weiß, wie man DFS implementiert) Lassen Sie mich erklären: Wir bekommen ein Diagramm und müssen ein DFS durchführen, um alle Artikulationspunkte zu finden, mit Rückennummern und der DFS-Nummer. Mein Hauptproblem besteht darin, die Rückennummer jedes Knotens mit dem gegebenen Algorithmus zu finden.Finden von Artikulationspunkten mit DFS und dem Bi-Komponenten-Algorithmus
Wir hatten ein Tutorial als Übung, um den Algorithmus zu implementieren, ich habe es getan, aber ich habe keine Ahnung, ob es richtig ist. Könnte jemand bitte überprüfen, dass ich es richtig gemacht habe und wenn möglich mich korrigieren. Die Frage des Lernprogramms lautet wie folgt
Verwenden Sie den in der Klasse durchgeführten Algorithmus, um einen Tiefensuchbaum des Algorithmus durchzuführen. Für jede Ecke finden:
• die dfs-Nummer
• die Rückennummer
• ob es sich um eine Gelenkstelle
Der Algorithmus und Meine Lösung ist:
Dank. Hoffe jemand kann helfen
Warum denken Sie, dass J ein Gelenkpunkt sein sollte? Es ist nicht eins. B ist auch kein Gelenkpunkt. – kraskevich
Da gemäß der Artikulationspunktbedingung 15> 14, also ein Artikulationspunkt ist, weiß ich jedoch, dass dies nicht wahr ist, denn wenn wir J entfernen, wird die Grafik nicht getrennt. – amine
Sie haben dfs-time = 14 und back- Nummer = 12. Es ist nicht Artikulationspunkt nach Ihrem Algorithmus und es ist in der Tat kein Artikulationspunkt. – kraskevich