>问题
我有一个线段列表：
exampleLineSegments = [(1,2),(2,3),(3,4),(4,5),(5,6),(4,7),(8,7)]
这些段包括单独数组中相应点的索引。
从这个子列表中，可以看到有一个分支点(4)。因此，三个不同的分支正在从这个分支点出现。 (在其他更具体的问题中，n个分支可能存在多个分支点。
目标
我的目标是获取包含有关现有分支信息的字典，例如：
result = { branch_1: [1,2,3,4],
branch_2: [4,5,6],
branch_3: [4,7,8]}
工作/问题的当前状态
目前，我首先通过为每个点设置字典并检查每个条目是否找到超过 2 个相邻点来识别分支点。这意味着有一个分支点。
之后，我正在爬行从这些分支点出现的所有点，检查后续等。
在这些函数中，有一些for循环，通常是一个密集的"爬行"。这不是最干净的解决方案，如果点数增加，性能也不是很好。
问题
在这种情况下，实现目标的最佳/最快/最高性能的方法是什么？
我认为您可以通过以下步骤来实现它：
- 使用
neighbors字典存储图形 - 查找相邻点计> 2 的所有分支点
- 从每个分支点开始，使用DFS查找所有路径
from collections import defaultdict
def find_branch_paths(exampleLineSegments):
# use dict to store the graph
neighbors = defaultdict(list)
for p1, p2 in exampleLineSegments:
neighbors[p1].append(p2)
neighbors[p2].append(p1)
# find all branch points
branch_points = [k for k, v in neighbors.items() if len(v) > 2]
res = []
def dfs(cur, prev, path):
# reach the leaf
if len(neighbors[cur]) == 1:
res.append(path)
return
for neighbor in neighbors[cur]:
if neighbor != prev:
dfs(neighbor, cur, path + [neighbor])
# start from all the branch points
for branch_point in branch_points:
dfs(branch_point, None, [branch_point])
return res
更新大数据的iteration版本，这可能会导致a recursion depth problem：
def find_branch_paths(exampleLineSegments):
# use dict to store the graph
neighbors = defaultdict(list)
for p1, p2 in exampleLineSegments:
neighbors[p1].append(p2)
neighbors[p2].append(p1)
# find all branch points
branch_points = [k for k, v in neighbors.items() if len(v) > 2]
res = []
# iteration way to dfs
stack = [(bp, None, [bp]) for bp in branch_points]
while stack:
cur, prev, path = stack.pop()
if len(neighbors[cur]) == 1 or (prev and cur in branch_points):
res.append(path)
continue
for neighbor in neighbors[cur]:
if neighbor != prev:
stack.append((neighbor, cur, path + [neighbor]))
return res
测试和输出：
print(find_branch_paths([(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (4, 7), (8, 7)]))
# output:
# [[4, 3, 2, 1], [4, 5, 6], [4, 7, 8]]
希望对您有所帮助，如果您有其他问题，请发表评论。
更新：如果有许多分支点，路径将呈指数级增长。因此，如果您只需要不同的段，则可以在遇到另一个分支点时结束路径。
将此行if len(neighbors[cur]) == 1:
更改为if len(neighbors[cur]) == 1 or (prev and cur in branch_points):