J'ai un problème de HW qui demande un algorithme qui détecte s'il y a un cycle dans tout graphe non dirigé contenant tout bord donné "E". L'algorithme doit fonctionner dans une période linéaire O (n).
Le problème que j'ai est que je ne sais pas où commencer. J'ai de simples échantillons de graphes, mais je ne sais pas où aller de là.
Toute astuce?
5 Réponses :
Vous commencez avec le bord 'E'. De là, vous devriez obtenir les deux sommets qu'il se connecte. D'après eux, vous obtenez d'autres bords et autres sommets, ainsi que d'autres bords et autres sommets, et ... vous aurez besoin d'un moyen de déterminer si un sommet a déjà été «visité» par votre algorithme. S'il est alors il y a un cycle que «E» fait partie de.
Faire une première recherche de profondeur Ajout de nœuds à une liste au fur et à mesure que vous allez et retirez-les de la liste au fur et à mesure de votre retour.
La liste représente votre chemin actuel de Traversal.
Si vous rencontrez un nœud qui est déjà dans votre liste, il y a une boucle / cycle.
pour le bord (U, V):
1- Effectuer une première vitesse de profondeur à partir de vous, déterminez si V est trouvé et un bord arrière existe le long du chemin de V.
2- Effectuez une première vitesse d'une première recherche de V, si vous êtes trouvé et le bord arrière existe pour vous, il y a un cycle qui inclut à la fois U et V.
En d'autres termes,
1- Effectuez un DFS à partir de vous, vérifiez si le bord du dos existe et v n'est pas encore terminé.
2- Effectuer un DF à partir de V, vérifiez si le bord du dos existe et que vous n'êtes pas encore terminé. Si les deux conditions sont vraies, le bord (U, V) appartient à un cycle.
Sortez ce bord (U, V) de G. 1. Exécutez BFS pour voir si V est toujours accessible de vous. 2. Si oui, le graphique d'origine contient un cycle contenant e. sinon il n'y a pas.
Et s'il y a plusieurs cycles?
Exécuter DFS sur g et procédez comme suit. Considérons la première fois que le bord e est traversé.
Il y a deux cas:
Un soupçon? Sûr. Certains ensembles (comme des hashsets) ont une recherche O (1).
Quelle est la signification de n?