Traversal de graphe orienté cyclique

Question

I ai un diagramme cyclique dirigé. À partir des feuilles, je souhaite propager des données attachées à chaque noeud aval à tous les nœuds qui sont accessibles à partir de ce nœud. En particulier, je dois continuer à pousser les données autour des cycles qui sont atteints jusqu'à ce que les cycles se stabilisent.

Je suis tout à fait sûr que ce soit un problème de traversal graphique de stock. Cependant, je vais avoir un peu de difficulté juste essayer de trouver un algorithme approprié --- Je pense que je manque quelques mots-clés de recherche cruciaux.

Avant que je tente d'écrire mon propre demi-assed O (n ^ 3) algorithme, quelqu'un peut me pointer à une bonne solution? Et que ce problème particulier appelé?

Answer 1

Etant donné que le graphique est cyclique (à savoir peut contenir des cycles), je voudrais tout d'abord de le décomposer en composants fortement connectés. Un d'un graphe orienté est un sous-graphe dans lequel chaque noeud est accessible à partir de chaque autre nœud le même sous-graphe. Cela donne un ensemble de sous-graphes. Notez qu'une composante fortement connexe de plus d'un noeud est en fait un cycle.

Maintenant, dans chaque composant, toute information dans un nœud finira par se retrouver dans tous les autres noeuds du graphique (car ils sont tous accessibles). Ainsi, pour chaque sous-graphe nous pouvons simplement prendre toutes les données de tous les nœuds et que chaque nœud ont le même ensemble de données. Pas besoin de continuer à travers les cycles. En outre, à la fin de cette étape, tous les noeuds du même composant contient exactement les mêmes données.

L'étape suivante consiste à réduire chaque composant fortement connecté en un seul noeud. Comme les noeuds du même composant ont tous les mêmes données, et sont donc essentiellement les mêmes, cette opération ne change pas vraiment le graphique. Le « super noeud » nouvellement créé hérite de tous les bords sortir ou entrer en nœuds de l'extérieur du composant nœuds du composant.

Puisque nous avons effondrés tous les composants connectés fortement, il n'y aura pas de cycles dans le graphe résultant (pourquoi? Parce que il y avait eu un cycle formé par les noeuds qui en résultent, ils ont tous été placés dans le même composant, en premier lieu ). Le graphique qui en résulte est maintenant un graphe acyclique orienté . Il n'y a pas de cycles, et une profondeur simple, premier traversal de tous les noeuds avec degré entrant = 0 (nœuds qui ont pas de bords entrants), propageant des données de chaque noeud à ses noeuds adjacents (par exemple ses « enfants »), devraient faire le travail .