Pseudocode zum finden von Zyklen in einem Diagramm mit Breite-zuerst-Suche
Geben Sie mir bitte pseudocode für das finden von Zyklen mit dem BFS. Ich weiß, andere Fragen dieser Art sind vorhanden, aber KEINES geben Sie den code.
wenn Sie meine Frage und wie es, daran erinnern, zu voten 🙂
InformationsquelleAutor Programmer | 2010-12-16
Du musst angemeldet sein, um einen Kommentar abzugeben.
Nur für den Fall, DFS ist viel besser geeignet für die Aufgabe, mehr noch in gerichteten Graphen. Wenn Sie bereits wusste, dass Sie das ignorieren.
Als für den pseudocode, gut, in einem ungerichteten Graphen, es ist ein traditionelles BFS, bricht ab und meldet ein Zyklus gefunden, wenn es erreicht einen Knoten, die zuvor als "besucht" markiert. Finden Sie pseudocode für BFS hier.
In einem gerichteten Graphen, es wird schwieriger, denn Sie haben sich daran zu erinnern, welchen Weg waren Sie zu Fuß, wenn Sie erreicht der Knoten, und die räumliche Komplexität Nachteil gegenüber der DFS wird noch schlimmer.
Edit: oh, ich spreche über die Untersuchung eines Graphen nach Zyklen, nicht tatsächlich zu finden, die Zyklus. Finden von Zyklen mit DFS liegt in der Nähe trivial, während der Suche nach Zyklen mit dem BFS ist sehr viel komplexer, sowohl in Bezug auf die eigentliche Algorithmische Komplexität und die Komplexität des Codes. Das ist, warum Sie nicht finden, pseudo-code.
Du meinst K2? Ich sehe nicht das problem =S
In Bezug auf Ihre Methode zum erkennen von Zyklen in ungerichteten Graphen betrachten 2----1. Wenn ich starten BFS von 1 werde ich beginnen, indem Sie es markieren als "besucht" und fügen Sie es in die Warteschlange. Klicken Sie dann in der while-Schleife, I wird wieder aus der Warteschlange aus, und markieren Sie beliebige adjazente, noch nicht besuchte Eckpunkte als "besucht" und fügen Sie Sie in die Warteschlange. in anderen Worten, ich werde hinzufügen 2 in der Warteschlange. Nun, wenn ich wieder 2 aus der Warteschlange, werde ich wieder überlegen, allen seinen benachbarten Eckpunkten. Dabei werde ich auch überlegen 1 bereits besucht. Allerdings bedeutet dies nicht, dass ein Zyklus.
Der BFS-Algorithmus funktioniert nicht so Mann. Sie don ' T re-use Bögen, oder es würde immer am Ende in einer Endlosschleife, egal was Sie tun, mit Ihrem BFS.
Ich denke, Sie Verstand nicht was ich sagte. Was meinst du mit dieser Aussage: "bricht ab und meldet ein Zyklus gefunden, wenn es erreicht einen Knoten, die zuvor als "besucht " markiert". In jeder version des BFS können Sie zu implementieren, besteht eine hohe chance, dass die BFS-Suche wird ein Knoten prviously als "besucht" markiert. Seine nur, dass wir ignorieren Sie diesen Knoten, und fügen Sie es nicht in die Warteschlange. Erklären Sie bitte, was meinen Sie mit "erreicht";
InformationsquelleAutor slezica
Haben Sie wahrscheinlich gedacht, DFS, die weit häufiger im Zyklus-Erkennung, so nehme ich an, dass Sie diesen Fehler. Wechsel zum BFS ist ziemlich einfach, aber der Grundgedanke bleibt der gleiche.
so, do u haben ein pseudo-code für das BFS??
überprüfen Sie CLRS
InformationsquelleAutor marcog