Wie bekomme ich den Cut-Set mit dem Edmonds-Karp-Algorithmus?

Wenn Sie bereits über den Flow verfügen, berechnen Sie den Restgraphen. Dann mache eine Tiefensuche zuerst von der Quelle (oder breite erste Suche, ich glaube nicht, dass es wichtig ist), um die Ecken in einer Hälfte des Schnitts zu berechnen (S). Die restlichen Ecken sind in der anderen Hälfte deines Schnitts, T.

Dies gibt Ihnen Ihren Schnitt (S, T). Wenn Sie speziell die Kanten zwischen S und T wollen, könnten Sie alle Kanten durchlaufen und diejenigen auswählen, die S und T verbinden. (Obwohl es eine elegantere Art geben kann, diesen letzten Teil zu machen.)

Wenn Sie bereits den maximalen Fluss kennen, dann ist der minimale Schnitt (S, T), wobei S die Menge an Knoten ist, die von der Quelle im Restnetzwerk erreichbar sind, T ist die komplementäre Menge. Kanten, die einen Eckpunkt von S und einen Eckpunkt von T verbinden, gehören zum Schnitt.

Hier sind einige Hinweise, die verdeutlichen sollen, wie dies in Zukunft für jeden zu tun ist.

1. Um die S-Scheitelpunkte zu finden, führen Sie eine BFS- (oder DFS-) Suche vom Quellknoten durch, wobei Sie nur Kanten folgen, bei denen noch etwas Kapazität für den Fluss übrig ist. (Mit anderen Worten, die nicht gesättigten Kanten). Diese können definitionsgemäß nicht im Mincut enthalten sein.

2. Um die T-Scheitelpunkte zu finden, führen Sie eine BFS- (oder DFS-) Suche aus dem Sink -Scheitelpunkt durch und verbinden Sie nur mit Scheitelpunkten, die nicht bereits zum S-Satz hinzugefügt wurden. Diese können einen Restfluss haben oder könnten vollständig gesättigt sein, es spielt keine Rolle. Da Sie BFS aus der Senke ausführen, müssen Sie sicherstellen, dass Sie der entgegengesetzten Richtung folgen, in der die Kante ausgerichtet ist, wenn der Graph ausgerichtet ist. HINWEIS: Es ist wichtig, nur Vertices einzubeziehen, die von der Senke in Ihrem T-Set erreicht werden können, andernfalls werden Sie Kanten in Ihrem Min-Cut einschließen, die nicht dorthin gehören. (Das ist, was mich für eine lange Zeit warf.)

3. Sobald Sie diese zwei Scheitelpunkte haben, können Sie über alle Kanten des Graphen iterieren. Jeder, der einen Quellknoten in S und einen Zielknoten in T hat, ist Teil Ihres Min-Cut. Es ist jedoch wichtig anzumerken, dass dies nur ein ein vieler möglicher Min-Schnitte ist. Es ist viel zeitaufwändiger, alle möglichen S-T Min-Schnitte in einem Graphen zu finden.

Hoffen wir, dass dies zukünftigen Internetnutzern hilft, dies herauszufinden! Viel Glück!