各路神仙，求解一个问题

有一个形如
[
['Start', 'A', [['Start', 'C', 'E', 'End'], ['Start', 'F', 'End']], [['Start', 'G', 'I', 'End'], ['Start', 'X', 'End'], ['Start', 'P', 'Q', 'End']], 'D', 'End'],
['Start', 'B', 'End']
]

用来描述图的所有路径的列表，最外层列表的每一个字列表都是一个图从 Start 到 End 的所有路径。例如 ['Start', 'B', 'End'] 表示 Start -> B -> End 但是节点有可能是个子图，此时怎么才能将子图展开，描述成为不具有子图的路径
比如将第一个条路径拆成
Start A C E G I D End
Start A C E X D End
Start A C E P Q D End
Start A C F G I D End
Start A C F X D End
Start A C F P Q D End
这六条路径

这也有可能是个 X-Y 问题，所以我贴上一个 gist
https://gist.githubusercontent.com/deplives/b92f0c0ceddbed7c76cc2829f8174fa1/raw/4e721ef4dace907f2d7d4a421155d44889b01fec/graph.py
或者说 find_all_paths 需要怎么改一下能直接产出这个图的所有不带子图的路径

end'

start'

Start

END

4 条回复

Laussan

2022-11-02 00:13:55 +08:00

要不还是存成邻接矩阵然后遍历吧，你这题里的存法看得人心肺停止...

lookStupiToForce

2022-11-03 19:36:39 +08:00

心肺停止+1+1+1+1+1......................

我挺佩服你写的出来 find_all_paths 还达成效果了👍👍👍👍
但你数据结构写成这样基本没法往里加功能没法维护了：
path 和 paths 存在互相转化且一会儿要包[]后加了才能用，一会儿却只能 append
key 和 value 作为图得节点也需要互相转化
导致可读性 /可理解性稀烂 pro plus max ，往里加任何东西都是工程灾难

而且你自己给出的例子里好像也错了，后面 3 个应该是
Start A F G I D End
Start A F X D End
Start A F P Q D End

下面是我特么脑抽闲的超级蛋疼，在你的屎山上（真的，这个实现足够屎）按照你的要求想破脑袋修改测试后再特意改错得到的 find_all_paths ，你试试如果你不看最后的答案能改对不？
反正我过了今天肯定改不对了，这破 list 和 k-v 转来转去已成天书，我弄完了都记不住也不想记

```python
from itertools import product

def extend_expanded_path(ori, new):
if isinstance(new, list):
if len(new) == 0:
return ori
else:
return [i + j for i, j in product(ori, new)]
else:
return [i + [new] for i in ori]

def print_node_list(node_list):
p_str = ''
for node in node_list:
if isinstance(node, Graph):
p_str += node.name + ','
else:
p_str += node + ','
return p_str

def find_all_paths(graph, start, end, path=None, path_expanded=None, sub_graph_flag=False):
# path_expanded list(list)
# print('当前图名： %s 。位于节点：%s 。后续节点：[%s]。' % (graph.name, start, print_node_list(graph[start]) if start in graph else None))
if path is None:
path = []
if path_expanded is None:
path_expanded = [[]]
if not isinstance(start, Graph):
if sub_graph_flag:
if start not in ('Start', 'End'):
path = path + [start]
path_expanded = [i + [start] for i in path_expanded]
else:
path = path + [start]
path_expanded = [i + [start] for i in path_expanded]
if start == end:
return [path], [path_expanded]
if start not in graph:
return [], [[]]
paths = []
paths_expanded = [[]]
for node in graph[start]:
if node not in path:
if isinstance(node, Graph):
sub_path, sub_expanded_path = find_all_paths(node, "Start", "End", None, None, True)
path = path + [sub_path]
path_expanded = extend_expanded_path(path_expanded, sub_expanded_path)
new_paths, new_paths_expanded = find_all_paths(graph, node, end, path, path_expanded, sub_graph_flag)

for new_path in new_paths:
paths.append(new_path)

for new_path_expanded in new_paths_expanded:
paths_expanded.append(new_path_expanded)
return paths, paths_expanded

print(find_all_paths(g3, "Start", "End")[0])
print(find_all_paths(g3, "Start", "End")[1])
```

lookStupiToForce

2022-11-03 19:52:51 +08:00

v 站贴代码真费事
这个是上面贴过一遍的错误答案的：
https://justpaste.it/9droi

这个是正确答案的：
https://justpaste.it/8ijo2

蛋疼完了，上面的正确答案就算能弄出来也不建议使用，
所以最后 3 点改进建议：
1. 用 1#说的邻接矩阵遍历
2. 把你原先 find_all_paths 的结果拿出来另外做递归解析
3. 把图结构做成单张链表，上数据库用递归查询

deplivesb

2022-11-03 22:38:49 +08:00

@lookStupiToForce 老哥牛逼，我也是接手的。被迫啊，我已经修修补补两周多了，这部分完全不知道咋下手。