Comment obtenir l'ensemble de coupe en utilisant l'algorithme d'Edmonds-Karp ?

Question

J'ai implémenté l'algorithme d'Edmonds-Karp en utilisant le pseudocode que j'ai trouvé sur la page wiki de l'algorithme d'Edmonds-Karp : http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm

Cela fonctionne très bien, mais la sortie de l'algorithme est la valeur maximale du flux (valeur minimale de la coupe), j'ai besoin de la liste des arêtes que cette coupe contient.

J'ai essayé de changer l'algorithme, sans succès, pouvez-vous m'aider ?

Merci de votre attention.

Answer 1

Si vous avez déjà le flux, calculez le graphe résiduel. Ensuite, effectuez une recherche en profondeur à partir de la source (ou en largeur, peu importe), pour calculer les sommets dans une moitié de la coupe (S). Les sommets restants se trouvent dans l'autre moitié de votre coupe, T.

Vous obtenez ainsi votre coupe (S, T). Si vous voulez spécifiquement les arêtes entre S et T, vous pouvez itérer à travers toutes les arêtes, en sélectionnant celles qui relient S et T. (Bien qu'il puisse y avoir une façon plus élégante de faire cette dernière partie).

Answer 2

Voici quelques conseils pour aider à clarifier la façon de procéder à l'avenir.

1. Pour trouver les sommets S, effectuez une recherche BFS (ou DFS) à partir du sommet source, en suivant uniquement les arêtes sur lesquelles il reste une certaine capacité de flux. (En d'autres termes, les arêtes non saturées). Par définition, ces arêtes ne peuvent pas se trouver dans la coupe minimale.

2. Pour trouver les T sommets, effectuez une recherche BFS (ou DFS) à partir de l'adresse évier en ne se connectant qu'aux sommets qui n'ont pas déjà été ajoutés à l'ensemble S. Ceux-ci peuvent avoir un flux résiduel ou être complètement saturés, peu importe. Comme vous effectuez le BFS à partir de l'évier, vous devrez vous assurer de suivre la direction opposée de l'arête si le graphe est orienté. REMARQUE : Il est important de n'inclure que les sommets qui peuvent être atteints à partir de l'évier. évier dans votre ensemble T, sinon vous finirez par inclure dans votre coupe minimale des bords qui n'y ont pas leur place. (C'est ce qui m'a longtemps déconcerté).

3. Une fois que vous disposez de ces deux ensembles de sommets, vous pouvez itérer sur toutes les arêtes du graphe. Toute arête ayant un nœud source dans S et un nœud cible dans T fait partie de votre coupe minimale. Il est important de noter, cependant, qu'il ne s'agit que de un de nombreuses coupes minimales possibles. Il est beaucoup plus long de trouver toutes les coupes minimales S-T possibles dans un graphe.

J'espère que cela aidera les futurs internautes qui essaieront de comprendre ce qu'il en est ! Bonne chance !

Answer 3

Si vous connaissez déjà le flux maximal, la coupe minimale est (S, T), où S est l'ensemble des sommets accessibles à partir de la source dans le réseau résiduel, et T est l'ensemble complémentaire. Les arêtes qui relient un sommet de S et un sommet de T appartiennent à la coupe.