找到两个特定节点之间的路径？ [英] Find the paths between two given nodes?
问题描述
说我有连接在下面的流行时尚节点，我怎么得出的特定点之间存在路径的数量，以及路径的详细信息？
1,2 //节点1和2连接
2,3
2,5
4,2
5,11
11,12
6,7
5,6
3,6
6,8
8,10
8,9
查找以7 1的路径：
答： 发现2道，他们是
1,2,3,6,7
1,2,5,6,7
下面是用Python上面的链接
代码段 ＃样品图
图= {'A'：'B'，'C'，'E']，
'B'：'A'，'C'，'D']，
'光盘']，
'D'：'C']，
'E'：'F'，'D']，
F：[C]}
类myQueue中：＃队列的只是实现
高清__init __（个体经营）：
self.holder = []
高清入队（个体经营，VAL）：
self.holder.append（VAL）
DEF出队（个体经营）：
VAL =无
尝试：
VAL = self.holder [0]
如果len（self.holder）== 1：
self.holder = []
其他：
self.holder = self.holder [1：]
除：
通过
返回VAL
高清的IsEmpty（个体经营）：
结果=假
如果len（self.holder）== 0：
结果=真
返回结果
path_queue = MyQueue的（）＃现在我们做一个队列
高清BFS（图，开始，结束，Q）：
temp_path = [开始]
q.enqueue（temp_path）
而q.IsEmpty（）==错误：
tmp_path = q.dequeue（）
last_node = tmp_path [LEN（tmp_path）-1]
打印tmp_path
如果last_node ==结束：
打印VALID_PATH：tmp_path
对于link_node在图[last_node]：
如果link_node不tmp_path：
#new_path = []
new_path = tmp_path + link_node]
q.enqueue（new_path）
BFS（图中，A，D，path_queue）
-------------结果-------------------
['一个']
['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']
广度优先搜索横梁的曲线图，实际上发现从一个起始节点的所有路径。通常情况下，BFS不保留所有路径，但是。相反，它更新一个prededecessor功能π保存的最短路径。您可以轻松地修改算法，使π（N）并不仅仅店的一个的predecessor但可能$ P $名单pdecessors。
然后，所有可能的路径都设有codeD在此功能，并通过遍历π递归你得到所有可能的路径组合。
一个良好的伪code，它使用这个符号可以在介绍发现算法通过Cormen 等的，并已在关于这个问题很多大学脚本随后被使用。阿谷歌搜索 BFS伪code predecessorπ连根拔起的this先打。
Say I have nodes connected in the below fashion, how do I arrive at the number of paths that exist between given points, and path details?
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
Find the paths from 1 to 7:
Answer: 2 paths found and they are
1,2,3,6,7
1,2,5,6,7
implementation found here is nice I am going to use the same
Here is the snippet from the above link in 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']
Breadth-first search traverses a graph and in fact finds all paths from a starting node. Usually, BFS doesn't keep all paths, however. Instead, it updates a prededecessor function π to save the shortest path. You can easily modify the algorithm so that π(n) doesn't only store one predecessor but a list of possible predecessors.
Then all possible paths are encoded in this function, and by traversing π recursively you get all possible path combinations.
One good pseudocode which uses this notation can be found in Introduction to Algorithms by Cormen et al. and has subsequently been used in many University scripts on the subject. A Google search for "BFS pseudocode predecessor π" uproots this first hit.
这篇关于找到两个特定节点之间的路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
