Algorithme pour un problème de graphique

Je dois vérifier la connexité des nœuds directionnels dans une liste. Il s'agit essentiellement de questions avec 2 à 7 réponses chacune. La réponse choisie dicte la question suivante. Étant donné que ces paires seront capturées manuellement, je dois vérifier chaque chemin possible pour revenir en arrière (non autorisé) et les impasses (toutes les routes doivent s'arrêter au nœud END) Des pointeurs?Algorithme pour un problème de graphique

start --> n1 --- n2 --- n3 --- n4 --- end 

      \/ \  \ / /

      n5  \  n6------ n7 

       \  \ / /

       n8----n9---n10----n11 

      DIRECTION -->

Source

2009-07-27 callisto

Je suis un peu confus par le graphique. Est-ce que n8 n'a qu'une seule réponse? Qu'en est-il de n9? –

Non, aucune des questions n1-n11 n'a moins de 2 réponses. le graphique est une illustration des différents chemins possibles avec des réponses différentes. Exemple: n1 a 4 réponses, dont 3 pointent vers n2, et le reste pointant vers n5. Les réponses à une question pouvaient pointer vers une Question suivante différente, mais j'ai essayé de garder l'illustration graphique simple. – callisto

Oh Attendez, n6 est montré avec 3 chemins différents. n9 a toutes ses réponses pointant vers n10, n11 ne pointe que vers n7. – callisto

Cela peut être ce que vous cherchez:

Testing whether a graph is acyclic

Votre noeud final est ce que le nœud feuille est dans la terminologie de cette page.

Si le graphe n'a pas de noeud, il est acyclique.
Si le graphique n'a pas de feuille, il est cyclique.
Choisissez une feuille, enlever les feuilles et toutes les transitions vers elle, étape goto 1.

Pour vérifier qu'il n'y a pas d'impasses: Il suffit de faire assurer qu'il n'y a qu'un seul nœud feuille avant d'utiliser l'algorithme ci-dessus.

Source

2009-07-27 12:23:56

Utilisez un algorithme breadth first search, garder une trace de tous les noeuds que vous avez déjà visités. Si, lors de la recherche du prochain nœud à parcourir, l'un des nœuds déjà visités est une possibilité, alors le graphique est faux. De plus, si vous atteignez un noeud qui n'a pas d'autre noeud possible à parcourir jusqu'au prochain, et que vous n'avez pas atteint la fin, alors le graphe n'est pas connecté correctement.

Source

2009-07-27 12:20:07 AlbertoPL

Algorithme pour un problème de graphique

Répondre

Questions connexes