Ich bin auf der Suche nach einer guten Lösung, um s-t Min-Schnitt-Kanten in ungerichteten und ungewichteten Graphen zu finden. Ich möchte den Push-Relabel-Algorithmus verwenden.implementieren Push-Relabel-Algorithmus s-t Min-Cut-Kanten für ungerichtete ungewichtete Grafik
Aber ich bin mir nicht sicher, wie man es implementiert, um min-cut auf ungerichteten und ungewichteten Graphen zu finden. Haben Sie zwei Kanten in umgekehrter Richtung zwischen jedem Scheitelpunktpaar und erhalten Sie an allen Kanten das gleiche Gewicht und wenden Sie den Push-Relabel-Algorithmus an? kann ich auf diese Weise min-cut bekommen?
Ich habe es in der folgenden Grafik versucht. a (m, n) am Scheitel bedeutet e (a) = m, h (a) = n. und jede Kante Kapazität wird als 1.
eindeutig der min-Schnitt ist die Kante (c, t). aber woher weiß ich (c, t) vom letzten Bild, wie groß die Kanten sind? oder habe ich falsch berechnet.
Kann jemand hier meinen Fehler aufzeigen? Hinweise sind willkommen, danke!
Ja, das wird funktionieren. – HenryLee
@HenryLee, ich habe die Frage aktualisiert und ein Beispiel hinzugefügt, könntest du es dir anschauen? Ich glaube, ich mache irgendwo einen Fehler – arslan
@AmiTavory, ich denke, ich zeichne Restfluss Grafik oben Beispiel, aber Mit-Cut scheint nicht richtig darin – arslan