计算元组列表中元素的可达性

Question

我有一个像这样的元组列表.

a = [(1,2),(1,3),(1,4),(2,5),(6,5),(7,8)]

在这个列表中1涉及2然后2涉及5和5涉及6因此1涉及6.类似地,我需要找到元组中其他元素之间的关系.我需要一个获取输入值和输出的函数,如下所示:

input = (1,6) #output = True
input = (5,3) #output = True
input = (2,8) #output = False

我不了解itertools或map函数.它们可以用来解决这些类型的问题吗？为了好奇和兴趣,我在哪里可以找到要解决的这些类型的问题,以及在现实生活中遇到的这些类型的问题在哪里？

Answer 1

这可以通过将元组视为图中的边来轻松完成.然后将问题简化为检查两个节点之间是否存在路径.

有很多很好的库,请参阅例如networkx

import networkx as nx

a = [(1,2),(1,3),(1,4),(2,5),(6,5),(7,8)]

G = nx.Graph(a)

nx.has_path(G, 1, 6)  # True
nx.has_path(G, 5, 3)  # True
nx.has_path(G, 2, 8)  # False