Python:比较和排序列表中的元组

Question

我正在尝试对点列表(它们的 ID)进行排序。这些元组是图的最小生成树(使用 networkx)的结果，其中每个节点都连接到每个其他节点，但它们的权重不同。我需要为每棵树提取一条(最短)路径，这将为我提供正确的边缘顺序。但是MST的元组的结果是无序的，如果我按原样使用它，我会得到不好的结果，所以我需要对元组进行排序。我有一些元组示例列表:

L1: [(0, 1), (0, 3), (2, 3)]
L2: [(0, 3), (1, 2), (2, 3)]
L3: [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]

L1 和 L2 没有按我想要的方式排序，L3 是。正如您可能注意到的，我需要列表的顺序是连续的点/元组，以导出树的顺序。 L1 和 L2 需要排序:

L1: [(1, 0), (0, 3), (3, 2)] : order = 1-0-3-2
L2: [(0, 3), (3, 2), (2, 1)] : order = 0-3-2-1

# some way to do this in pseudo code would be
for tuple in list:
    # compare current tuple with previous and next (if exist)
    if tuple[1] != next[0]:
        reverse tuple
    if tuple[0] != prev[1]:
        reverse tuple
    etc...

我尝试通过定义多个 if/elif 语句(见上文)对列表进行排序，但这会变得困惑无序。我见过使用诸如 sorted(L1, key=customsort) 之类的东西进行排序，但我找不到比较多个元组的方法，我希望这样的事情是可能的!

Answer 1

最简单的是找到路径的起​​点，根据注释，该起点是出现一次的两个索引之一，同时构建连续遍历的方法。假设有 n 个节点，我们可以构建一些东西来帮助我们(我认为这个解决方案是清晰的、线性的，但可能不是最好/最优雅的):

path = [[] for _ in range(n)]
stops= [2 for _ in range(n)]
for edge in result:
    for i in range(2):
        path[edge[i]].append(edge[1-i])
        stops[edge[i]] -= 1
for current in range(len(stops)):
    if stops[current]: break

path 这里在每个索引(这是一个节点)中保存它连接到的两个/一个其他节点。内部循环查看边缘中的点 - edge[0],edge[1]。 1-i 只是将 1 与 0 翻转。

stops 计算节点出现的次数。每个节点在路径中出现两次，除了两个 - 这些将是数组中唯一不为 0 的位置。这不是必须的，只是一个简单的起点。

current 查找这样的非零条目作为起始位置。

现在通过遍历路径来重建，以创建所需的正确元组列表:

result = [(current,path[current][0])] #Only one option!
current= path[current][0]
while stops[current]:
   next = path[current][1] if path[current][0] == current else path[current][0]
   result.append((current,next))
   current = next

请注意，我没有使用原始列表中的一些已知信息，例如顺序。您可以使用它来改进这一点。