Trouver les chemins entre deux nœuds donnés?
https://stackoverflow.com/questions/713508
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Dire que j'ai noeuds connectés de la façon ci-dessous, comment puis-je obtenir le nombre de chemins qui existent entre plusieurs points, et les détails de chemin?
1,2 //node 1 and 2 are connected
2,3
2,5
4,2
5,11
11,12
6,7
5,6
3,6
6,8
8,10
8,9
Trouver les chemins de 1 à 7:
Réponse: 2 chemins trouvés et ils sont
1,2,3,6,7
1,2,5,6,7
est agréable, je vais utiliser le même
Voici l'extrait à partir du lien ci-dessus en python
# a sample graph
graph = {'A': ['B', 'C','E'],
'B': ['A','C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F','D'],
'F': ['C']}
class MyQUEUE: # just an implementation of a queue
def __init__(self):
self.holder = []
def enqueue(self,val):
self.holder.append(val)
def dequeue(self):
val = None
try:
val = self.holder[0]
if len(self.holder) == 1:
self.holder = []
else:
self.holder = self.holder[1:]
except:
pass
return val
def IsEmpty(self):
result = False
if len(self.holder) == 0:
result = True
return result
path_queue = MyQUEUE() # now we make a queue
def BFS(graph,start,end,q):
temp_path = [start]
q.enqueue(temp_path)
while q.IsEmpty() == False:
tmp_path = q.dequeue()
last_node = tmp_path[len(tmp_path)-1]
print tmp_path
if last_node == end:
print "VALID_PATH : ",tmp_path
for link_node in graph[last_node]:
if link_node not in tmp_path:
#new_path = []
new_path = tmp_path + [link_node]
q.enqueue(new_path)
BFS(graph,"A","D",path_queue)
-------------results-------------------
['A']
['A', 'B']
['A', 'C']
['A', 'E']
['A', 'B', 'C']
['A', 'B', 'D']
VALID_PATH : ['A', 'B', 'D']
['A', 'C', 'D']
VALID_PATH : ['A', 'C', 'D']
['A', 'E', 'F']
['A', 'E', 'D']
VALID_PATH : ['A', 'E', 'D']
['A', 'B', 'C', 'D']
VALID_PATH : ['A', 'B', 'C', 'D']
['A', 'E', 'F', 'C']
['A', 'E', 'F', 'C', 'D']
VALID_PATH : ['A', 'E', 'F', 'C', 'D']
La solution
recherche en largeur d'abord un graphique parcourt et trouve en fait tous les chemins d'un départ nœud. Mais en général, BFS ne garde pas tous les chemins,. Au lieu de cela, il met à jour une fonction prededecessor π pour enregistrer le chemin le plus court. Vous pouvez facilement modifier l'algorithme de sorte que π(n) ne stocke pas seulement un prédécesseur, mais une liste des prédécesseurs possibles.
Ensuite, tous les chemins possibles sont codés dans cette fonction, et en traversant π récursive vous obtenez toutes les combinaisons possibles de chemin.
Un bon pseudocode qui utilise cette notation peut être trouvée dans Introduction aux algorithmes par Cormen et al. et a ensuite été utilisé dans de nombreux scripts universitaires sur le sujet. Une recherche Google pour « BFS prédécesseur pseudocode π » déracine ce hit sur Stack Exchange.
Autres conseils
Pour ceux qui ne sont pas experts PYTHON, le même code en C ++
//@Author :Ritesh Kumar Gupta
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<vector<int> >GRAPH(100);
inline void print_path(vector<int>path)
{
cout<<"[ ";
for(int i=0;i<path.size();++i)
{
cout<<path[i]<<" ";
}
cout<<"]"<<endl;
}
bool isadjacency_node_not_present_in_current_path(int node,vector<int>path)
{
for(int i=0;i<path.size();++i)
{
if(path[i]==node)
return false;
}
return true;
}
int findpaths(int source ,int target ,int totalnode,int totaledge )
{
vector<int>path;
path.push_back(source);
queue<vector<int> >q;
q.push(path);
while(!q.empty())
{
path=q.front();
q.pop();
int last_nodeof_path=path[path.size()-1];
if(last_nodeof_path==target)
{
cout<<"The Required path is:: ";
print_path(path);
}
else
{
print_path(path);
}
for(int i=0;i<GRAPH[last_nodeof_path].size();++i)
{
if(isadjacency_node_not_present_in_current_path(GRAPH[last_nodeof_path][i],path))
{
vector<int>new_path(path.begin(),path.end());
new_path.push_back(GRAPH[last_nodeof_path][i]);
q.push(new_path);
}
}
}
return 1;
}
int main()
{
//freopen("out.txt","w",stdout);
int T,N,M,u,v,source,target;
scanf("%d",&T);
while(T--)
{
printf("Enter Total Nodes & Total Edges\n");
scanf("%d%d",&N,&M);
for(int i=1;i<=M;++i)
{
scanf("%d%d",&u,&v);
GRAPH[u].push_back(v);
}
printf("(Source, target)\n");
scanf("%d%d",&source,&target);
findpaths(source,target,N,M);
}
//system("pause");
return 0;
}
/*
Input::
1
6 11
1 2
1 3
1 5
2 1
2 3
2 4
3 4
4 3
5 6
5 4
6 3
1 4
output:
[ 1 ]
[ 1 2 ]
[ 1 3 ]
[ 1 5 ]
[ 1 2 3 ]
The Required path is:: [ 1 2 4 ]
The Required path is:: [ 1 3 4 ]
[ 1 5 6 ]
The Required path is:: [ 1 5 4 ]
The Required path is:: [ 1 2 3 4 ]
[ 1 2 4 3 ]
[ 1 5 6 3 ]
[ 1 5 4 3 ]
The Required path is:: [ 1 5 6 3 4 ]
*/
L'algorithme de Dijkstra applique plus aux chemins pondérés et il semble que l'affiche était de vouloir trouver tous les chemins, et pas seulement les plus brefs.
Pour cette application, je construirais un graphique (votre application sonne comme il aurait pas besoin d'être dirigé) et utilisez votre méthode de recherche préféré. On dirait que vous voulez tous les chemins, non seulement une supposition à une plus courte, donc utiliser un simple algorithme récursif de votre choix.
Le seul problème est si le graphique peut être cyclique.
Avec les connexions:
- 1, 2
- 1, 3
- 2, 3
- 2, 4
Alors que la recherche d'un chemin de 1-> 4, vous pourriez avoir un cycle de 1 -> 2 -> 3 -.> 1
Dans ce cas, je garde une pile comme traversant les noeuds. Voici une liste des étapes de ce graphique et la pile résultante (désolé pour la mise en forme - aucune option de table):
nœud courant (possibles prochains nœuds moins d'où nous venons) [pile]
- 1 (2, 3) [1]
- 2 (3, 4) [1, 2]
- 3 (1) [1, 2, 3]
- 1 (2, 3) [1, 2, 3, 1] // erreur - Numéro double sur la pile - cycle détecté
- 3 () [1, 2, 3] // retour-étagée vers le noeud et trois sauté 1 de la pile. Plus de nœuds d'explorer d'ici
- 2 (4) [1, 2] // retour-étagé vers le noeud 2 et sauté 1 de la pile.
- 4 () [1, 2, 4] // noeud cible disponible - pile enregistrement pour un chemin d'accès. Plus de nœuds d'explorer d'ici
- 2 () [1, 2] // retour-étagée vers le noeud 2 et 4 sauté hors de la pile. Plus de nœuds d'explorer d'ici
- 1 (3) [1] // retour-étagée vers le noeud 1 et 2 sauté hors de la pile.
- 3 (2) [1, 3]
- 2 (1, 4) [1, 3, 2]
- 1 (2, 3) [1, 3, 2, 1] // erreur - dupliquer le numéro sur la pile - cycle détecté
- 2 (4) [1, 3, 2] // retour-étagée vers le noeud 2 et sauté 1 de la pile
- 4 () [1, 3, 2, 4] noeud cible disponible - pile enregistrement pour un chemin d'accès. Plus de nœuds d'explorer d'ici
- 2 () [1, 3, 2] // retour-étagée vers le noeud 2 et 4 sauté hors de la pile. Plus de nœuds
- 3 () [1, 3] // retour-étagée vers le noeud 3 et sauté 2 de la pile. Plus de nœuds
- 1 () [1] // retour-étagée vers le noeud 1 et 3 sauté hors de la pile. Plus de nœuds
- Fait avec 2 trajets enregistrés de [1, 2, 4] et [1, 3, 2, 4]
Le code d'origine est un peu lourd et vous voudrez peut-être utiliser le collections.deque à la place si vous souhaitez utiliser BFS pour trouver si un chemin existe entre 2 points sur le graphique. Voici une solution rapide, je piraté jusqu'à:
Note: cette méthode pourrait continuer à l'infini s'il existe pas de chemin entre les deux nœuds. Je ne l'ai pas testé tous les cas, YMMV.
from collections import deque
# a sample graph
graph = {'A': ['B', 'C','E'],
'B': ['A','C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F','D'],
'F': ['C']}
def BFS(start, end):
""" Method to determine if a pair of vertices are connected using BFS
Args:
start, end: vertices for the traversal.
Returns:
[start, v1, v2, ... end]
"""
path = []
q = deque()
q.append(start)
while len(q):
tmp_vertex = q.popleft()
if tmp_vertex not in path:
path.append(tmp_vertex)
if tmp_vertex == end:
return path
for vertex in graph[tmp_vertex]:
if vertex not in path:
q.append(vertex)
Prolog (en particulier, SWI-Prolog)
:- use_module(library(tabling)).
% path(+Graph,?Source,?Target,?Path)
:- table path/4.
path(_,N,N,[N]).
path(G,S,T,[S|Path]) :-
dif(S,T),
member(S-I, G), % directed graph
path(G,I,T,Path).
test:
paths :- Graph =
[ 1- 2 % node 1 and 2 are connected
, 2- 3
, 2- 5
, 4- 2
, 5-11
,11-12
, 6- 7
, 5- 6
, 3- 6
, 6- 8
, 8-10
, 8- 9
],
findall(Path, path(Graph,1,7,Path), Paths),
maplist(writeln, Paths).
?- paths.
[1,2,3,6,7]
[1,2,5,6,7]
true.
Si vous voulez que tous les chemins, utilisez récursivité.
Utilisation d'une liste d'adjacence, de préférence, de créer une fonction f () qui tente de remplir une liste actuelle des sommets visités. Comme ceci:
void allPaths(vector<int> previous, int current, int destination)
{
previous.push_back(current);
if (current == destination)
//output all elements of previous, and return
for (int i = 0; i < neighbors[current].size(); i++)
allPaths(previous, neighbors[current][i], destination);
}
int main()
{
//...input
allPaths(vector<int>(), start, end);
}
En raison du fait que le vecteur est passé par valeur (et donc toutes les modifications apportées plus bas dans la procédure récursive ne sont pas permanentes), toutes les combinaisons possibles sont énumérées.
Vous pouvez gagner un peu d'efficacité en passant le précédent vecteur par référence (et donc pas besoin de copier le vecteur, encore et encore), mais vous devez vous assurer que les choses se popped_back () manuellement.
Une autre chose: si le graphique a des cycles, cela ne fonctionnera pas. (Je suppose que dans ce cas, vous voulez trouver tous les simples chemins, alors) Avant d'ajouter quelque chose dans le précédent vecteur, vérifiez d'abord si elle est déjà là-dedans.
Si vous voulez que tous les les plus courtes chemins, utilisez la suggestion de Konrad avec cet algorithme.
étant donné la matrice de contiguïté:
{0, 1, 3, 4, 0, 0}
{0, 0, 2, 1, 2, 0}
{0, 1, 0, 3, 0, 0}
{0, 1, 1, 0, 0, 1}
{0, 0, 0, 0, 0, 6}
{0, 1, 0, 1, 0, 0}
le code Mathematica Wolfram suivant résoudre le problème de trouver tous les chemins simples entre deux noeuds d'un graphe. Je récursivité simple, et deux var global pour garder une trace des cycles et pour stocker la sortie désirée. le code n'a pas été optimisé juste pour un souci de clarté du code. le « print » devrait être utile de préciser comment cela fonctionne.
cycleQ[l_]:=If[Length[DeleteDuplicates[l]] == Length[l], False, True];
getNode[matrix_, node_]:=Complement[Range[Length[matrix]],Flatten[Position[matrix[[node]], 0]]];
builtTree[node_, matrix_]:=Block[{nodes, posAndNodes, root, pos},
If[{node} != {} && node != endNode ,
root = node;
nodes = getNode[matrix, node];
(*Print["root:",root,"---nodes:",nodes];*)
AppendTo[lcycle, Flatten[{root, nodes}]];
If[cycleQ[lcycle] == True,
lcycle = Most[lcycle]; appendToTree[root, nodes];,
Print["paths: ", tree, "\n", "root:", root, "---nodes:",nodes];
appendToTree[root, nodes];
];
];
appendToTree[root_, nodes_] := Block[{pos, toAdd},
pos = Flatten[Position[tree[[All, -1]], root]];
For[i = 1, i <= Length[pos], i++,
toAdd = Flatten[Thread[{tree[[pos[[i]]]], {#}}]] & /@ nodes;
(* check cycles!*)
If[cycleQ[#] != True, AppendTo[tree, #]] & /@ toAdd;
];
tree = Delete[tree, {#} & /@ pos];
builtTree[#, matrix] & /@ Union[tree[[All, -1]]];
];
];
pour appeler le code: initNode = 1; nœud terminal = 6; lcycle = {}; arbre = {{initNode}}; builtTree [initNode, matrice];
chemins: {{1}} root: 1 --- noeuds: {2,3,4}
chemins: {{1,2}, {1,3}, {1,4}} racine: 2 --- noeuds: {3,4,5}
chemins: {{1,3}, {1,4}, {1,2,3}, {1,2,4}, {1,2,5}} root: 3 --- noeuds: {2,4}
chemins: {{1,4}, {1,2,4}, {1,2,5}, {1,3,4}, {1,2,3,4}, {1,3 , 2,4}, {1,3,2,5}} root: 4 --- noeuds: {2,3,6}
chemins: {{1,2,5}, {1,3,2,5}, {1,4,6}, {1,2,4,6}, {1,3,4,6 }, {1,2,3,4,6}, {1,3,2,4,6}, {1,4,2,5}, {1,3,4,2,5}, {1 , 4,3,2,5}} root: 5 --- noeuds: {6}
RESULTATS: {{1, 4, 6}, {1, 2, 4, 6}, {1, 2, 5, 6}, {1, 3, 4, 6}, {1, 2, 3 , 4, 6}, {1, 3, 2, 4, 6}, {1, 3, 2, 5, 6}, {1, 4, 2, 5, 6}, {1, 3, 4, 2 , 5, 6}, {1, 4, 3, 2, 5, 6}}
... Malheureusement, je ne peux pas télécharger des images pour afficher les résultats d'une meilleure façon: (
Qu'est-ce que vous essayez de faire est essentiellement de trouver un chemin entre deux sommets dans un graphe (dirigé?) Vérifier l'algorithme de Dijkstra si vous avez besoin chemin le plus court ou écrire une fonction récursive simple si vous avez besoin tout existe des chemins.
