Wir können DFS/BFS von der Quelle aus verwenden, um einen minimalen Schnitt zu finden. Aber können wir BFS/DFS von jedem Knoten aus verwenden, um zu sehen, ob es reichen kann, um einen Min-Cut zu finden? Oder, wie finden wir alle minimalen Schnitte?Finden Sie den minimalen Schnitt im Netzwerkfluss
nicht sicher, dass ich Ihre Frage verstanden habe. Um einen Min-Cut zu finden, können wir den Max-Flow finden und ihn verwenden, um den Min-Cut zu finden (durch den Min-Cut-Max-Flow-Theorem).
Wenn Sie, wenn mehr als eine Minute Schnitt überprüfen wollen, ist, nachdem Sie das restliche Netzwerk erhalten, führen BFS(s) - bei s beginnen, sollten wir diese Gruppe von Eckpunkten X sein. Dann kippen Sie die Kanten des restlichen Netzwerks und führen Sie BFS(t), lassen Sie diese Gruppe von Scheitelpunkten Y sein. Wenn die Vereinigung X und Y alle Eckpunkte des Graphen sind, haben Sie nur einen Schnitt. Sonst - Sie haben mehr als eine (um alle Z min Schnitt zu finden, dauert es mindestens (Z|V|)