时间戳

首页 > 解决方案 > 合并表示基于公共值的图边的元组列表

python - 合并表示基于公共值的图边的元组列表

问题描述

我正在尝试编写一些 python 代码，如果给定一个表示图上的有向边的元组列表，我将返回所有可能的路径。在这种情况下，图将不包含循环，并且图的每个节点只能连接到另一个节点。输入将采用以下形式

[(1909, 1910), (1910, 1900), (1922, 1920), (1935,1922), (1940, 1939)]

并且应该以以下形式返回一些东西

[(1909,1910,1900), (1935,1922,1920), (1940,1939)]

我不知道如何解决这个问题，因为必须保持顺序，即因为 1922 在 1920 之前，而 1935 在 1922 之前，所以结果答案必须是 (1935,1922,1920)

关于如何实现这一目标的任何想法？

标签： pythongraphtuples

解决方案

您可以将元组转换为以第一项为键的字典，然后通过链接每个项的最后一个元素来逐步合并这些项。

tuples = [(1909, 1910), (1910, 1900), (1922, 1920), (1935,1922), (1940, 1939)]

links = { a:[b] for a,b in tuples }
while True:
    toMerge = [(a,bs[-1]) for a,bs in links.items() if bs[-1] in links]
    for a,b in toMerge:
        links[a].append(b)
        del links[b]
    else: break
result = [ [a,*bs] for a,bs in links.items() ]
print(result)

# [[1909, 1910, 1910], [1935, 1922, 1922], [1940, 1939]]

推荐阅读