Ich weiß, dass es in O (V + E) mit topologischen Sortierung erfolgen kann. Aber ich denke, es kann auch in der gleichen Komplexität mit BFS getan werden.Können wir BFS (auf die optimale Weise) verwenden, um die kürzesten Pfade von einem Quellenknoten zu allen anderen Knoten in einem gewichteten gerichteten azyklischen Graphen zu finden?
Die topologische Sortierung ist nichts anderes als dass es ein DFS-Lauf ist. Dann, wenn jeder Scheitelpunkt fertig ist, legen Sie ihn auf die Vorderseite einer verknüpften Liste. Es hat eine Laufzeit von O (V + E). Wie ich bereits sagte, ist es hier natürlicher, zu fragen "Können wir eine topologische Sortierung mit BFS machen?". Dies wurde bereits gestellt und beantwortet.
Wenn was du meinst ist nur BFS, dann würde ich nein sagen. Schauen Sie sich hierzu example an. Eine topologische Sortierung ist eine lineare Anordnung aller ihrer Ecken, so dass, wenn der Graph G eine Kante (u, v) enthält, u vor v in der Ordnung erscheint. Sie sehen in diesem Beispiel eine Kante von c nach d, aber d erscheint vor c. Ich denke, dass Sie BFS aktualisieren können, um die topologische Sortierung zu finden, aber es hat wieder die gleiche Komplexität wie das Ausführen von DFS. Ich würde Ihnen empfehlen, sich diesen Beitrag anzusehen Using BFS for topological sort
Vergessen wir für einige Zeit topologische Sortierung. Wenn ich die Breite der ersten Traversierung für eine DAG verwende, beginnend mit einem Quellknoten s, dann kann ich die kürzeste Entfernung zu allen anderen Knoten in O (V + E) Zeit finden, indem ich ein Entfernungs-Array (initialisiert mit Unendlich) aufrechterhalte und es aktualisiere Wir erhalten einen Wert kleiner als der aktuell gespeicherte Wert für einen Knoten. Wenn ich also auf meine ursprüngliche Frage zurückkomme, ist das nicht dieser Ansatz von gleicher Komplexität wie die Verwendung einer topologischen Reihenfolge zum Durchqueren von Knoten in einer DAG, um kürzeste Wege zu finden? –
Können Sie mehr ausarbeiten, was meinst du mit (auf die optimale Weise)? Wenn das was du meinst ist die Komplexität dann ja. Eine topologische Sortierung ist die Anwendung von DFS, weshalb sie eine Komplexität von O (V + E) aufweist. Ich denke, es ist natürlicher zu fragen "Können wir eine topologische Sortierung mit BFS machen?". Diese Frage wurde bereits gestellt. – Abdulhakeem
Was ich meinte war, können wir einfach BFS verwenden, anstatt die Knoten in topologischer Reihenfolge zu besuchen. –