Etant donné un Spanning Tree et un bord qui ne figure pas sur le Spanning Tree, comment former une base de cycle?

Question

J'ai un graphe avec Edge E et Vertex V. Je peux trouver le spanning tree à l'aide de Algorithme Kruskal (ou tout autre type d’algorithme transversal), je souhaite maintenant rechercher toutes les bases de cycle créées en utilisant cet arbre recouvrant et les arêtes ne figurant pas sur le arbre, tout algorithme qui me permet de le faire, en plus de la recherche par force brute?

Je peux, bien sûr, partir d’un sommet du bord de l’arbre non recouvrant, obtenir tous les bords, les explorer toutes, se rétracter si je trouve une impasse, jusqu’à ce que je revienne à l’autre sommet du bord. Mais c'est un peu, euh… brutal. D'autres idées?

Answer 1

Un algorithme simple que nous utilisons pour trouver des cycles dans les graphiques:

  

Créer un arbre spanning-first   où chaque noeud a un parent.       En parcourant l’arbre, créez un enregistrement des nœuds utilisés.       Lorsqu'un bord pointe vers un noeud précédemment utilisé, stockez-le en tant que   bord cyclique.       Lorsque l'arbre recouvrant est terminé, le nombre de cycliques   bords donne le nombre de cycles.       Pour chaque bord cyclique, recurse à travers les ancêtres des deux nœuds   jusqu'à ce qu'un ancêtre commun soit trouvé. Cette   donnera exactement les cycles.

Il peut être utile de disposer d'un index (hashtable) de tous les ancêtres d'un nœud de bord cyclique afin de trouver rapidement l'ancêtre commun.

Je doute que ce soit le meilleur algorithme, mais il est assez rapide.

MODIFIER dans le réponse au commentaire Chaque nœud de l'arbre recouvrant a un parent. Lorsqu'un nœud dans une arête cyclique est atteint, il calcule sa liste d'ancêtres (List<Node> Cette liste peut être indexée en fonction de la vitesse (ie (contient ()) est < O(n)). Lorsqu'un arête cyclique à deux nœuds (n1, n2) est trouvé, alors parcourir les ancêtres de n1, n1.ancestorList (rapidement car la liste a déjà été créée) et vérifier si l'ancêtre est dans n2.ancestorList. Si tel est le cas (commonAncestor), alors exactement ces ancêtres parcourus correspondent à des cycles. n2 jusqu'à ce que vous atteigniez O(logN) (rapide). Le temps devrait dépendre du nombre d'arêtes cycliques, combiné à la recherche dans les listes (probablement <=> mais bon marché). Il n'est pas nécessaire de réexplorer le graphique. pas de retour en arrière.

Answer 2

Après la construction de Spanning Tree, effectuez une itération sur chaque bord (A, B) qui n’est pas dans l’arbre et recherchez le plus bas ancêtre commun (LCA) pour les nœuds de ce bord, votre cycle sera le chemin de A - & Gt; ACV - & Gt; B - & Gt; Un

vous pouvez utiliser ce lien: http: //www.topcoder .com / tc? module = Static & amp; d1 = didacticiels & amp; d2 = lowerCommonAncestor     pour une implémentation efficace de l'algorithme le plus commun, l'Ancestor Commun.