你应该先看看 http://en.wikipedia.org/wiki/Breadth-first_search。

下面是一个快速实现，其中我使用了一个列表来表示路径队列。

# graph is in adjacent list representation
graph = {
'1': ['2', '3', '4'],
'2': ['5', '6'],
'5': ['9', '10'],
'4': ['7', '8'],
'7': ['11', '12']
}


def bfs(graph, start, end):
# maintain a queue of paths
queue = []
# push the first path into the queue
queue.append([start])
while queue:
# get the first path from the queue
path = queue.pop(0)
# get the last node from the path
node = path[-1]
# path found
if node == end:
return path
# enumerate all adjacent nodes, construct a
# new path and push it into the queue
for adjacent in graph.get(node, []):
new_path = list(path)
new_path.append(adjacent)
queue.append(new_path)


print bfs(graph, '1', '11')

指纹: ['1', '4', '7', '11']

另一种方法是维护从每个节点到其父节点的映射，并在检查相邻节点时记录其父节点。搜索完成后，只需根据父映射进行回溯。

graph = {
'1': ['2', '3', '4'],
'2': ['5', '6'],
'5': ['9', '10'],
'4': ['7', '8'],
'7': ['11', '12']
}


def backtrace(parent, start, end):
path = [end]
while path[-1] != start:
path.append(parent[path[-1]])
path.reverse()
return path
        



def bfs(graph, start, end):
parent = {}
queue = []
queue.append(start)
while queue:
node = queue.pop(0)
if node == end:
return backtrace(parent, start, end)
for adjacent in graph.get(node, []):
if node not in queue :
parent[adjacent] = node # <<<<< record its parent
queue.append(adjacent)


print bfs(graph, '1', '11')

上面的代码是基于没有周期的假设。

我觉得我应该试着编写一些有趣的代码:

graph = {
'1': ['2', '3', '4'],
'2': ['5', '6'],
'5': ['9', '10'],
'4': ['7', '8'],
'7': ['11', '12']
}


def bfs(graph, forefront, end):
# assumes no cycles


next_forefront = [(node, path + ',' + node) for i, path in forefront if i in graph for node in graph[i]]


for node,path in next_forefront:
if node==end:
return path
else:
return bfs(graph,next_forefront,end)


print bfs(graph,[('1','1')],'11')


# >>>
# 1, 4, 7, 11

如果你想要周期，你可以添加以下内容:

for i, j in for_front: # allow cycles, add this code
if i in graph:
del graph[i]

我非常喜欢乔的第一个回答！ 这里唯一缺少的是将顶点标记为已访问。 < br > < br > 我们为什么要这么做？
让我们假设有另一个节点编号13从节点11连接。现在我们的目标是找到13号节点。
稍微运行一下，队列就会像这样: < br >

[[1, 2, 6], [1, 3, 10], [1, 4, 7], [1, 4, 8], [1, 2, 5, 9], [1, 2, 5, 10]]

请注意，有两条路径，最后是节点号10。
这意味着从节点号10开始的路径将被检查两次。在这种情况下，它看起来没有那么糟糕，因为10号节点没有任何子节点。.但是它可能非常糟糕(即使在这里，我们也会无缘无故地检查该节点两次。.)
节点编号13不在这些路径中，所以程序在到达第二条路径之前不会返回，最后是节点编号10。.我们会再检查的。.

我们所缺少的只是一个标记已访问节点并且不再检查它们的集合。
这是乔的密码经过修改后的: < br >

graph = {
1: [2, 3, 4],
2: [5, 6],
3: [10],
4: [7, 8],
5: [9, 10],
7: [11, 12],
11: [13]
}




def bfs(graph_to_search, start, end):
queue = [[start]]
visited = set()


while queue:
# Gets the first path in the queue
path = queue.pop(0)


# Gets the last node in the path
vertex = path[-1]


# Checks if we got to the end
if vertex == end:
return path
# We check if the current node is already in the visited nodes set in order not to recheck it
elif vertex not in visited:
# enumerate all adjacent nodes, construct a new path and push it into the queue
for current_neighbour in graph_to_search.get(vertex, []):
new_path = list(path)
new_path.append(current_neighbour)
queue.append(new_path)


# Mark the vertex as visited
visited.add(vertex)




print bfs(graph, 1, 13)

该方案的输出将是:

[1, 4, 7, 11, 13]

没有不必要的重新检查. 。

我既喜欢“巧第一答案”又喜欢“或者”的加法。为了减少一些处理，我想添加到 Or 的答案中。

在@Or 的回答中记录访问的节点非常好。我们还可以允许程序比目前更快地退出。在 for 循环的某个点上，current_neighbour必须是 end，一旦发生这种情况，找到最短路径，程序就可以返回。

我将按照以下方式修改该方法，密切关注 for 循环

graph = {
1: [2, 3, 4],
2: [5, 6],
3: [10],
4: [7, 8],
5: [9, 10],
7: [11, 12],
11: [13]
}




def bfs(graph_to_search, start, end):
queue = [[start]]
visited = set()


while queue:
# Gets the first path in the queue
path = queue.pop(0)


# Gets the last node in the path
vertex = path[-1]


# Checks if we got to the end
if vertex == end:
return path
# We check if the current node is already in the visited nodes set in order not to recheck it
elif vertex not in visited:
# enumerate all adjacent nodes, construct a new path and push it into the queue
for current_neighbour in graph_to_search.get(vertex, []):
new_path = list(path)
new_path.append(current_neighbour)
queue.append(new_path)


#No need to visit other neighbour. Return at once
if current_neighbour == end
return new_path;


# Mark the vertex as visited
visited.add(vertex)




print bfs(graph, 1, 13)

输出和其他所有内容都是相同的。但是，处理该代码所需的时间较少。这对于较大的图表尤其有用。我希望这对将来的人有所帮助。

非常简单的代码。每次发现一个节点时都要不断追加路径。

graph = {
'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])
}
def retunShortestPath(graph, start, end):


queue = [(start,[start])]
visited = set()


while queue:
vertex, path = queue.pop(0)
visited.add(vertex)
for node in graph[vertex]:
if node == end:
return path + [end]
else:
if node not in visited:
visited.add(node)
queue.append((node, path + [node]))

如果图中包含了周期，那么这样的工作不是更好吗？

from collections import deque


graph = {
1: [2, 3, 4],
2: [5, 6, 3],
3: [10],
4: [7, 8],
5: [9, 10],
7: [11, 12],
11: [13]
}




def bfs1(graph_to_search, start, end):
queue = deque([start])
visited = {start}
trace = {}


while queue:
# Gets the first path in the queue
vertex = queue.popleft()
# Checks if we got to the end
if vertex == end:
break


for neighbour in graph_to_search.get(vertex, []):
# We check if the current neighbour is already in the visited nodes set in order not to re-add it
if neighbour not in visited:
# Mark the vertex as visited
visited.add(neighbour)
trace[neighbour] = vertex
queue.append(neighbour)


path = [end]
while path[-1] != start:
last_node = path[-1]
next_node = trace[last_node]
path.append(next_node)


return path[::-1]


print(bfs1(graph,1, 13))

这种方法只访问新的节点，而且避免了循环。

Javascript 版本和搜索第一/所有路径..。

顺便说一下，带圆周的图表很好用。

你可以 convert它到 python，这很容易

function search_path(graph, start, end, exhausted=true, method='bfs') {
// note. Javascript Set is ordered set...
const queue = [[start, new Set([start])]]
const visited = new Set()
const allpaths = []
const hashPath = (path) => [...path].join(',') // any path hashing method
while (queue.length) {
const [node, path] = queue.shift()
// visited node and its path instant. do not modify it others place
visited.add(node)
visited.add(hashPath(path))
for (let _node of graph.get(node) || []) {
// the paths already has the node, loops mean nothing though.
if (path.has(_node))
continue;
// now new path has no repeated nodes.
let newpath = new Set([...path, _node])
if (_node == end){
allpaths.push(newpath)
if(!exhausted) return allpaths; // found and return
}
else {
if (!visited.has(_node) || // new node till now
// note: search all possible including the longest path
visited.has(_node) && !visited.has(hashPath(newpath))
) {
if(method == 'bfs')
queue.push([_node, newpath])
else{
queue.unshift([_node, newpath])
}
}
}
}
}
return allpaths
}

像这样的输出. 。

[
[ 'A', 'C' ],
[ 'A', 'E', 'C'],
[ 'A', 'E', 'F', 'C' ] // including F in `A -> C`
]