状态空间搜索

1from collections import deque
2
3def bfs(graph, start, goal):
4    queue = deque([(start, [start])])
5    visited = {start}
6    while queue:
7        node, path = queue.popleft()
8        if node == goal:
9            return path
10        for nxt in graph.get(node, []):
11            if nxt not in visited:
12                visited.add(nxt)
13                queue.append((nxt, path + [nxt]))
14    return None
15
16graph = {
17    "A": ["B", "C"], "B": ["D"], "C": ["E"],
18    "D": ["F"], "E": ["F"], "F": [],
19}
20path = bfs(graph, "A", "F")
21print(" -> ".join(path) if path else "no path")
22print(bfs(graph, "F", "A"))