Encontrar las rutas entre dos nodos?
https://stackoverflow.com/questions/713508
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Decir que tengo los nodos conectados en la continuación de la moda, ¿cómo puedo llegar al número de rutas que existen entre los puntos dados, y la ruta de los detalles?
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
Encontrar las rutas del 1 al 7:
Respuesta:2 rutas de encontrar y son
1,2,3,6,7
1,2,5,6,7
implementación que se encuentran aquí es bueno me voy a utilizar el mismo
Aquí está el fragmento de código desde el enlace de arriba 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']
Solución
primero en amplitud de búsqueda atraviesa un gráfico y, de hecho, encuentra todos los caminos de una partida nodo. Por lo general, BFS no conserva todos los caminos, sin embargo. En su lugar, se actualiza una función π prededecessor para guardar el camino más corto. Usted puede modificar fácilmente el algoritmo de manera que no lo hace π(n) única tienda un predecesor, pero una lista de posibles predecesores.
A continuación, todos los caminos posibles están codificados en esta función, y por la que atraviesa π recursiva obtener todas las combinaciones posibles de ruta.
Una buena pseudocódigo que utiliza esta notación se puede encontrar en Introducción a los algoritmos por Cormen et al. y, posteriormente, se ha utilizado en muchos guiones Universitarios sobre el tema. Una búsqueda en Google de “BFS pseudocódigo predecesor π” arranca este golpe en la pila de cambio .
Otros consejos
Para los que no son expertos Python, el mismo código 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 ]
*/
El algoritmo de Dijkstra se aplica más a caminos ponderados y parece que el cartel fue querer encontrar todos los caminos, no sólo el más corto.
Para esta aplicación, construiría un gráfico (suena su aplicación como si no tendría que ser dirigida) y utilizar su método de búsqueda favorito. Parece que usted desea que todos los caminos, no sólo una conjetura en el más corto, por lo que utiliza un simple algoritmo recursivo de su elección.
El único problema con esto es que si el gráfico puede ser cíclico.
Con las conexiones:
- 1, 2
- 1, 3
- 2, 3
- 2, 4
En la búsqueda de un camino a partir de 1-> 4, usted podría tener un ciclo de 1 -> 2 -> 3 -.> 1
En ese caso, entonces me gustaría mantener una pila que lo atraviesa los nodos. Aquí hay una lista con los pasos para que el gráfico y la pila resultante (lo siento por el formato - no hay opción de tabla):
nodo actual (posibles próximos nodos menos de dónde venimos) [pila]
- 1 (2, 3) [1]
- 2 (3, 4) [1, 2]
- 3 (1) [1, 2, 3]
- 1 (2, 3) [1, 2, 3, 1] // error - duplicar el número en la pila - detectó ciclo
- 3 () [1, 2, 3] // volver-escalonado al nodo tres y reventado 1 de la pila. No hay más nodos para explorar desde aquí
- 2 (4) [1, 2] // volver-caminado al nodo 2 y se metió 1 de la pila.
- 4 () [1, 2, 4] // nodo de destino encontrado - pila récord para un camino. No hay más nodos para explorar desde aquí
- 2 () [1, 2] // volver-escalonado al nodo 2 y aparecido 4 de la pila. No hay más nodos para explorar desde aquí
- 1 (3) [1] // volver-escalonado para el nodo 1 y hecho estallar 2 de la pila.
- 3 (2) [1, 3]
- 2 (1, 4) [1, 3, 2]
- 1 (2, 3) [1, 3, 2, 1] // error - duplicar el número en la pila - detectó ciclo
- 2 (4) [1, 3, 2] // volver-escalonado al nodo 2 y hecho estallar 1 de la pila
- 4 () [1, 3, 2, 4] nodo de destino encontrado - pila récord para un camino. No hay más nodos para explorar desde aquí
- 2 () [1, 3, 2] // volver-escalonado al nodo 2 y aparecido 4 de la pila. No más nodos
- 3 () [1, 3] // volver-escalonado al nodo 3 y hecho estallar 2 de la pila. No más nodos
- 1 () [1] // volver-escalonado para el nodo 1 y aparecido 3 de la pila. No más nodos
- Hecho con 2 caminos registrados de [1, 2, 4] y [1, 3, 2, 4]
El código original es un poco complicado y es posible que desee utilizar el collections.deque su lugar si desea utilizar BFS de encontrar si existe un camino entre 2 puntos en la gráfica. Aquí es una solución rápida Pirateé arriba:
Nota: este método podría continuar infinitamente si no existe una ruta entre los dos nodos. No he probado todos los casos, tu caso es distinto.
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)
En Prolog (específicamente, 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).
prueba:
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 desea que todos los caminos, el uso de la recursividad.
Uso de una lista de adyacencia, preferiblemente, crear una función f () que intenta llenar en una lista actual de vértices visitados. De esta manera:
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);
}
Debido al hecho de que el vector se pasa por valor (y por tanto los cambios realizados más abajo en el procedimiento recursivo no son permanentes), todas las combinaciones posibles se enumeran.
Puede ganar un poco de eficiencia pasando el anterior vector de referencia (y así no tener que copiar el vector una y otra vez), sino que tendrá que asegurarse de que las cosas se ponen popped_back () manualmente.
Una cosa más: si el gráfico tiene ciclos, esto no va a funcionar. (Supongo que en este caso usted quiere encontrar todos los simples caminos, a continuación) Antes de añadir algo en el anterior vector, primer cheque si ya está ahí.
Si desea que todos los más cortos caminos, utilice la sugerencia de Konrad con este algoritmo.
dada la matriz de adyacencia:
{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}
el siguiente Wolfram Mathematica código de resolver el problema de encontrar todos los simples caminos entre dos nodos de un grafo.He utilizado simple repetición, y dos mundiales de var para mantener un seguimiento de los ciclos y almacenar el resultado deseado.el código no ha sido optimizado solo para el bien de la claridad del código.la "impresión" debería ser útil para aclarar cómo funciona.
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]]];
];
];
para llamar al código:initNode = 1;endNode = 6;lcycle = {};árbol = {{initNode}};builtTree[initNode, matriz];
rutas de acceso:{{1}} raíz:1---nodos:{2,3,4}
rutas de acceso:{{1,2},{1,3},{1,4}} raíz:2---nodos:{3,4,5}
rutas de acceso:{{1,3},{1,4},{1,2,3},{1,2,4},{1,2,5}} raíz:3---nodos:{2,4}
rutas de acceso:{{1,4},{1,2,4},{1,2,5},{1,3,4},{1,2,3,4},{1,3,2,4},{1,3,2,5}} raíz:4---nodos:{2,3,6}
rutas de acceso:{{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}} raíz:5---nodos:{6}
RESULTADOS:{{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}}
...Lamentablemente no puedo subir imágenes a mostrar los resultados en una forma mejor :(
Lo que estamos tratando de hacer es esencialmente para encontrar un camino entre dos vértices en un grafo (dirigido?) Echa un vistazo a el algoritmo de Dijkstra si necesita camino más corto o escribir una función recursiva sencilla si necesita cualquier existen caminos.
