python - 在 Python 中对边列表进行排序

Question

我正在尝试对 Python 中的唯一边列表进行排序，以便根据具有与下一条边的共享顶点的前一条边按顺序排列边列表。我已经有了获取“开始”和“结束”边缘的功能。

例如，一个未排序的边列表是这样的:

[[0, 5], [2, 4], [4, 5], [1, 2], [0, 6]]

正确排序后，将如下所示:

[[6, 0], [0, 5], [4, 5], [2, 4], [1, 2]]

[6, 0] 为起始边，[1, 2] 为结束边。

根据我见过的排序方法，排序是基于知道你想按列表中的哪个索引进行排序，但在这种情况下，索引可以是 0 或 1。

Answer 1

from collections import defaultdict

followed_by = defaultdict(list)

def follows(edge1, edge2):  # does edge2 follow edge1
    return edge1 != edge2 and not set(edge1).isdisjoint(set(edge2))

def sorted_path(path, end):

    start = path[-1]

    for follower in followed_by[tuple(start)]:

        if follower in path:
            continue  # avoid circularities

        if follower == end:
            return path + [end]  # solution found

        new_path = sorted_path(path + [follower], end)  # recurse

        if new_path:
            return new_path  # solution found

    return None  # solution not found

# build defaultdict of who follows who

for edge in edges:
    for potential_follower in edges:
        if follows(edge, potential_follower):
            followed_by[tuple(edge)].append(potential_follower)

edges = [[0, 5], [2, 4], [4, 5], [1, 2], [0, 6]]

START = [0, 6]

END = [1, 2]

print(sorted_path([START], END))  # pass the path so far and terminal node