0

问题

我有一个线段列表：

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 循环，通常是密集的“爬行”。这不是最干净的解决方案，如果点数增加，性能也不是那么好。

问题

在这种情况下，实现目标的最佳/最快/最高性能的方法是什么？

4

1 回答 1

0

我认为您可以通过以下步骤实现它：

  1. 使用neighborsdict 存储图形
  2. 找到所有分支点，其中邻居计数 > 2
  3. 从每个分支点开始，使用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):

于 2019-04-09T12:06:28.430 回答