Comment le nombre de chemins dans un graphique dirigé peut-il calculer? Y a-t-il des algorithmes à cette fin?
meilleurs voeux
EDIT : Le graphique n'est pas un arbre.
8 Réponses :
Je ne crois pas qu'il y ait quelque chose plus rapide que de traverser le graphique, à partir de la racine.
en pseudo-code -
Merci. Mais j'ai peur de ne pas avoir compris ce que tu voulais m'expliquer !!
@ Sal1, il voulait dire faire une première recherche de profondeur.
Tous les coups de recherche que je vois sont pour le nombre de chemins d'un nœud donné à un autre nœud donné. Mais voici un algorithme qui devrait trouver le nombre total de chemins n'importe où dans le graphique, pour tout digraphic acyclique. (S'il existe des cycles, il existe un nombre infini de chemins que si vous spécifiez que certains chemins répétitifs sont exclus.)
Étiquetez chaque nœud avec le nombre de chemins qui se terminent à ce nœud: P>
While not all nodes are labeled:
Choose an unlabeled node with no unlabeled ancestors.
(An implementation might here choose any node, and recursively
process any unlabeled ancestors of that node first.)
Label the node with one plus the sum of the labels on all ancestors.
(If a node has no ancestors, its label is simply 1.)
THNAKS. Pouvez-vous me fournir des liens pour ces algorithmes qui donnent le nombre de chemins entre deux chemins particuliers, car chaque graphique dispose de noeud de démarrage et de fin, nous pouvons effectuer ces algorithmes pour calculer le nombre de chemins.
Merci d'avoir répondu! Je sais que c'est assez vieux, mais je tiens à ajouter qu'une méthode BFS pourrait être une implémentation de choisir le prochain nœud non étiqueté car BFS garantit que tous les ancêtres d'un nœud ont été visités avant
Si c'est vraiment un arbre, le nombre de chemins est égal au nombre de nœuds-1 si vous comptez les chemins vers des nœuds internes. Si vous ne comptez que les chemins à feuilles, le nombre de chemins est égal au nombre de feuilles. Donc, le fait que nous parlions d'arbres simplifie les choses à compter juste des nœuds ou des feuilles. Un simple algorithme BFS ou DFS suffira.
Les commentaires de OP ci-dessus ("considérons que le graphique est acyclique") me fait penser que le mot "arbre" a glissé accidentellement.
Si le graphique n'est pas un arbre, il y aura des chemins infinis - marcher une boucle à tout moment.
Deux nœuds déconnectés ont infiniment de nombreux chemins entre eux? Wow! :)
Les DAG ne sont pas des arbres, mais n'ont qu'un nombre fini de chemins (supposant des graphes finis).
Vous pouvez utiliser Profondeur-première recherche . Cependant, vous ne terminez pas la recherche lorsque vous trouverez un chemin de début à destination, la manière dont la première recherche de profondeur est normalement. Au lieu de cela, vous adressez simplement au nombre de chemins et de revenir de ce nœud comme s'il s'agissait d'une impasse. Ce n'est probablement pas la méthode la plus rapide, mais cela devrait fonctionner.
Vous pouvez également utiliser potentiellement une première recherche de la largeur, mais vous devez ensuite vous élaborer un moyen de passer des informations sur Chemin Compte vers l'avant (ou vers l'arrière) à travers l'arborescence lorsque vous le recherchez. Si vous pouviez faire cela, ce serait probablement beaucoup plus rapide.
En supposant que le graphique est acyclique (un DAG), vous pouvez créer un tri topologique des sommets et que la programmation dynamique pour calculer le nombre de chemins distincts. Si vous souhaitez imprimer tous les chemins, il n'est pas très utile de discuter de la grosse notation car le nombre de chemins peut être exponentiel sur le nombre de sommets.
pseudo-code: edit: bogue sur le code
let L'entrée en position Par conséquent:
Il pourrait être sage de vérifier d'abord si G contient un cycle, car dans ce cas, il contient une infinité de plusieurs chemins. Afin de détecter les cycles, définissez tous les poids de bord à -1 et utilisez Bellman-Ford. A la matrice d'adjacence d'un graphique g . Ensuite, a ^ n (i.e. A multiplié n fois avec lui-même) a la propriété intéressante suivante:
(i, j) de A ^ n est égal au nombre de chemins de longueur différente n de vertex i à sommet j .
A
A avec elle-même à plusieurs reprises jusqu'à ce que vous soyez ennuyé
Repérer le motif encore? admis donne la longueur 1 chemin entre les sommets;
admis ^ 2 donne la longueur 2 chemins entre les sommets;
admis ^ 3 donne la longueur 3 chemins entre les sommets;
Juste le nombre de chemins? Ou les chemins eux-mêmes aussi? Le graphique est-il acyclique? Des restrictions sur les chemins considérés?
Duplicailler possible de Stackoverflow.com/questions/1642139/...
@thkala. Considérons que le graphique est acyclique et il n'y a aucune restriction sur les chemins considérés. Quel algorithme existe quand je veux seulement calculer le nombre de chemins et si je veux primer les chemins eux-mêmes ?? Le lien que vous avez fourni est de loin de ce que je cherche!
Vous pouvez recueillir sur les sous-arbres - 1 + le produit du nombre de chemins dans des sous-arbres directement sous la racine