2 回答

TA貢獻(xiàn)1789條經(jīng)驗(yàn) 獲得超8個(gè)贊
與您的代碼非常相似的邏輯,但經(jīng)過(guò)清理,因?yàn)?Python 可以檢查項(xiàng)目是否在列表中,因此不使用單獨(dú)的 'U' 或 'D' 數(shù)組。
ajs = [[(1, None), (2, None)], [(0, None), (2, None)], [(1, None), (0, None)]]
def paths(node, finish):
routes = []
def step(node, path):
for nb,_ in ajs[node]:
if nb == finish:
routes.append( path + [node, nb] )
elif nb not in path:
step(nb, path + [node])
step(node, [])
return routes
print paths(0,2)

TA貢獻(xiàn)1864條經(jīng)驗(yàn) 獲得超2個(gè)贊
這是獲得所需答案的代碼變體。也就是說(shuō),這是解決問(wèn)題的一種令人困惑的方法。在我看來(lái),該算法分布在兩個(gè)函數(shù)中,而它應(yīng)該可以用單個(gè)遞歸函數(shù)解決。
def main():
adj_list = [
[(1, None), (2, None)],
[(0, None), (2, None)],
[(1, None), (0, None)],
]
paths = sorted(all_paths(adj_list, 0, 2))
print(paths)
def all_paths(adj_list, source, destination):
paths = []
for neighbour, _ in adj_list[source]:
pth = [source, neighbour]
if neighbour == destination:
paths.append(pth)
else:
node = finder(
adj_list,
neighbour,
['U'] * len(adj_list),
pth,
destination,
)
paths.append(pth + [node])
return paths
def finder(adj_list, current, state, pth, end):
for neighbour, _ in adj_list[current]:
if neighbour == end:
state[neighbour] = 'D'
return neighbour
elif state[neighbour] == 'U':
state[neighbour] = 'D'
return finder(adj_list, neighbour, state, pth, end)
main()
例如,這是一個(gè)替代實(shí)現(xiàn):
def main():
# An adjacency matrix for this example:
#
# 0 - 1
# \ /
# 2
#
matrix = [
[(1, None), (2, None)],
[(0, None), (2, None)],
[(1, None), (0, None)],
]
# Print all paths from 0 to 2.
paths = get_paths(matrix, 0, 2)
for p in paths:
print(p)
def get_paths(matrix, src, dst, seen = None):
# Setup:
# - Initialize return value: paths.
# - Get an independent seen set.
# - Add the source node to the set.
paths = []
seen = set(seen or [])
seen.add(src)
# Explore all non-seen neighbors.
for nb, _ in matrix[src]:
if nb not in seen:
seen.add(nb)
# Find the subpaths from NB to DST.
if nb == dst:
subpaths = [[nb]]
else:
subpaths = get_paths(matrix, nb, dst, seen)
# Glue [SRC] to the those subpaths and add everything to paths.
for sp in subpaths:
paths.append([src] + sp)
return paths
main()
添加回答
舉報(bào)