Dans un premier arbre en profondeur, il y a les arêtes définissant larbre (cest-à-dire les arêtes qui ont été utilisées dans le traversal).
Il reste quelques arêtes reliant certains des autres nœuds. Quelle est la différence entre une arête transversale et une arête avant?
De wikipedia:
Sur la base de cet arbre couvrant, les arêtes du graphe original peut être divisé en trois classes: les arêtes avant, qui pointent dun nœud de larbre vers lun de ses descendants, les arêtes arrière, qui pointent dun nœud vers lun de ses ancêtres, et les arêtes croisées, qui ne font ni lun ni lautre. Parfois, les bords des arbres, qui appartiennent à larbre couvrant lui-même, sont classés séparément des bords avant. Si le graphe dorigine nest pas orienté, toutes ses arêtes sont des arêtes darbre ou darrière-plan.
Na « t une arête qui nest pas utilisée dans le parcours qui points dun nœud à un autre établissent une relation parent-enfant?
Commentaires
- Connexes: cs.stackexchange.com/questions/99988/… cherche à établir un algorithme qui, pour un graphe orienté, préférera faire des arêtes avant, plutôt que des arêtes croisées, pendant recherche en profondeur dabord.
Réponse
Wikipédia a la réponse:
Tous les types darêtes apparaissent dans cette image. Tracez le DFS sur ce graphique (les nœuds sont explorés dans lordre numérique), et voyez où vous lintuition échoue.
Ceci explique le diagramme: –
Bord avant: (u, v), où v est un descendant de u, mais pas une arête darbre .Cest un bord non-arbre qui relie un sommet à un descendant dans un arbre DFS.
Arête transversale: toute autre arête. Peut aller entre les sommets dans le même arbre de profondeur dabord ou dans différents arbres de profondeur dabord. (profane)
Cest nimporte quelle autre arête du graphe G. Il relie des sommets dans deux arbres DFS différents ou deux sommets dans le même arbre DFS dont aucun nest lancêtre de lautre. (formel)
Commentaires
- Pourquoi nest-il pas impossible que 6 ait été parcouru en premier (côté droit en premier)? Si cela sétait produit, comment le bord 2- > 3 aurait-il été appelé?
- @soandos, je vous suggère de prendre vous-même le temps de tracer lalgorithme. En supposant que les Wikipédiens nont ‘ pas fait une erreur, limage décrit une exécution de bonne foi de DFS sur ce graphique, et il y a donc un moyen dajuster lalgorithme dans cette trace. Les types darêtes sont décrits assez clairement dans Wikipedia, et vous pouvez également consulter cet exemple.
- Je comprends que cest une manière valable de faire un DFS. Je demande simplement ce que si cétait fait dans lautre sens.
- Les résultats seraient alors différents. Je ‘ désolé, vous ‘ devez vous débrouiller vous-même.
- @soandos En général, il peut très bien être plusieurs traversées DFS. Les notions utilisées ici sont relatives à un parcours donné et différeront pour plusieurs parcours.
Réponse
Un parcours DFS dans un graphe non orienté ne laissera pas darête croisée puisque toutes les arêtes incidentes sur un sommet sont explorées.
Cependant, dans un graphe orienté, vous pouvez rencontrer une arête cela conduit à un sommet qui a été découvert auparavant de telle sorte que ce sommet nest pas un ancêtre ou un descendant du sommet actuel. Un tel bord est appelé un bord croisé.
Commentaires
- Aporov, Merci pour la réponse. Il me semble toujours que lorsque vous arrivez au sommet 6 dans le DFS comme schématisé dans Wikipedia, vous avez trois arêtes à parcourir à partir de 6. À ce stade, le sommet 6 est » courant « . Finalement, vous allez traverser larête jusquau sommet 3. Alors que 3 a déjà été visité, néanmoins puisquil y a une arête de 6 à 3, alors 3 est un descendant du courant » » vertex 6. Si tel est le cas, cela enfreint la définition dune arête transversale. Il doit y avoir quelque chose de plus dans la définition qui nest pas ‘ t rendu très explicite.
- En fait, DFS ne contient que les deux arêtes darbre pour les arêtes arrière (Introduction à Algorithmes Thm. 22.10).
Réponse
Dans un parcours DFS, les nœuds sont terminés une fois que tous leurs enfants sont fini. Si vous marquez les heures de découverte et de fin pour chaque nœud pendant la traversée, vous pouvez vérifier si un nœud est un descendant en comparant les heures de début et de fin. En fait, tout parcours DFS partitionnera ses bords selon la règle suivante.
Soit d [node] le temps de découverte du nœud, de même que f [node] soit le temps de fin.
Théorème des parenthèses Pour tous les u, v, exactement une des conditions suivantes est vérifiée:
1.d [u] < f [u] < d [v] < f [ v] ou d [v] < f [v] < d [u] < f [u] et aucun des u et v nest un descendant de lautre.
d [u] < d [v] < f [v] < f [u] et v est un descendant de u.
d [v] < d [u] < f [u] < f [v] et u est un descendant de v.
Donc, d [u] < d [v] < f [u] < f [v] ne peut pas se produire.
Jaime parenthèses: () [], ([]) et [()] sont OK mais ([)] et [(]) ne sont pas OK.
Par exemple, considérons le graphe à arêtes:
A -> B
A -> C
B -> C
Que lordre de visite soit représenté par une chaîne détiquettes de nœuds, où « ABCCBA » signifie A -> B -> C (terminé) B (terminé) A (terminé), similaire à ((())).
Donc « ACCBBA » pourrait être un modèle pour « (() ()) ».
Exemples:
« CCABBA »: Alors A -> C est une croix bord, puisque le CC nest pas à lintérieur de A.
« ABCCBA »: Alors A -> C est un bord avant (descendant indirect).
« ACCBBA »: Alors A -> C est un bord darbre (descendant direct).
Sources:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Lecure Notes http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm