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

Answer 2

下面的代码不是一种有效的方法，但可以完成您的示例。唯一解的假设就是在这个意义上理解“唯一边”。

lst = [[0, 5], [2, 4], [4, 5], [1, 2], [0, 6]]
l=len(lst)
#Your function gives ini and end:
ini = [0, 6]
end = [1, 2]
sol = [ini]
lst.remove(ini)
lst.remove(end)
while len(sol) < l - 1:
    for x in lst:
        if any(y in x for y in sol[-1]):
            sol.append(x)
            lst.remove(sol[-1])
            break
sol.append(end)
print("sol", sol)