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

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