我们可以使用深度优先搜索算法来解决这个问题。该算法遍历所有的路径,同时记录并回溯到之前的节点。在每个节点,我们可以将其标记为已经访问过,并继续搜索其可到达的节点,直到达到目标节点或者没有可以访问的节点。
以下是一个示例代码实现:
class Node:
def __init__(self, value):
self.value = value
self.edges = []
self.visited = False
def all_paths(node, end_node, path=[]):
path = path + [node]
if node == end_node:
return [path]
paths = []
node.visited = True
for edge in node.edges:
if not edge.visited:
new_paths = all_paths(edge, end_node, path)
for p in new_paths:
paths.append(p)
node.visited = False
return paths
该代码的输入为两个节点和它们之间的无向图,输出为从起始节点到目标节点的所有路径。该算法的时间复杂度为 O(V+E),其中 V 是节点数量,E 是边数量。
下一篇:编写一个程序,使房间能够移动。