Trouver tous les chemins possibles entre deux nœuds dans un graphe non orienté

Quelqu’un peut-il me donner un code C pour trouver tous les chemins possibles entre deux nœuds? par exemple. si le graphique a les arêtes suivantes 1-2 1-3 2-3 2-4 3-4

tous les chemins entre 1 et 4 sont:

1-2-3-4

1-2-4

1-3-4

1-3-2-4

Une recherche en profondeur d’abord fait ce travail.

(Je suppose que vous ne voulez pas de nœuds répétés dans votre chemin, sinon le nombre de chemins possibles est infini.)

Vous pouvez faire une détente:

while (there is a change) { for (v in nodes(G)) { for (e in edges(v)) { paths_to[v] = paths_to[v] union ((paths_to[e.to] not containing v) append v) } } } 

Le résultat peut toujours être exponentiel dans la taille du graphe en entrée. Obtenir tous les chemins n’est probablement pas ce que vous voulez faire.

C’est un algorithme simple au problème. Ce n’est pas un algorithme optimal.

 static struct { int value1; int value2; int used; } data[] = { { 1, 2 }, { 1, 3 }, { 2, 3 }, { 2, 4 }, { 3, 4 }, }; enum { DATA_SIZE = sizeof data / sizeof *data }; static int output[DATA_SIZE]; int traverse(int from, int to, int depth) { output[depth++] = from; int i; if (from == to) { for (i = 0; i < depth; i++) { if (i) { printf("-"); } printf("%d", output[i]); } printf("\n"); } else { for (i = 0; i < DATA_SIZE; i++) { if (!data[i].used) { data[i].used = 1; if (from == data[i].value1) { traverse(data[i].value2, to, depth); } else if (from == data[i].value2) { traverse(data[i].value1, to, depth); } data[i].used = 0; } } } } int main() { traverse(1, 4, 0); } 

une méthode récursive:

 findPaths(path = startNode, goal) paths = [] if the last node in path is goal: return path for each node n connected to the last node in path: if n is not already on the path: paths.append(findPaths(path.append(node), goal)) return paths //may still be [] 

Il est trop tard et pas le code C mais peut aider les autres. Cette montre aussi comment je l’implémente en java.

 findPath(start) Childs = getDirectChildsOf(start) foreach child in Childs tempRoute; tempRoute.add(start) if (child == end) return tempRoute.add(child) else tempRoute.add(findPath(child)) if (tempRoute.last() == end) return tempRoute; 

Ici, tempRoute peut être une classe Route qui gère une liste de nœuds. Possibilité d’append un seul node et une autre route à tempRoute . Il ne trouve pas non plus tous les chemins possibles. pour cela, vous devez conserver un indicateur visité pour chaque nœud.