合并元组（如果它们具有一个公共元素）

Question

考虑以下列表：

tuple_list = [('c', 'e'), ('c', 'd'), ('a', 'b'), ('d', 'e')]

我该如何实现？

new_tuple_list = [('c', 'e', 'd'), ('a', 'b')]

我试过了：

for tuple in tuple_list:
    for tup in tuple_list:
        if tuple[0] == tup[0]:
            new_tup = (tuple[0],tuple[1],tup[1])
            new_tuple_list.append(new_tup)

但是，只有当我按一定顺序具有元组的元素时，它才起作用，这意味着它将导致以下结果：

new_tuple_list = [('c', 'e', 'd'), ('a', 'b'), ('d', 'e')]

Answer 1

您可以将元组视为图形中的边，而将目标视为在图形中查找连接的组件。然后，您可以简单地遍历顶点（元组中的项），并为尚未访问的每个顶点执行DFS生成组件：

from collections import defaultdict

def dfs(adj_list, visited, vertex, result, key):
    visited.add(vertex)
    result[key].append(vertex)
    for neighbor in adj_list[vertex]:
        if neighbor not in visited:
            dfs(adj_list, visited, neighbor, result, key)

edges = [('c', 'e'), ('c', 'd'), ('a', 'b'), ('d', 'e')]

adj_list = defaultdict(list)
for x, y in edges:
    adj_list[x].append(y)
    adj_list[y].append(x)

result = defaultdict(list)
visited = set()
for vertex in adj_list:
    if vertex not in visited:
        dfs(adj_list, visited, vertex, result, vertex)

print(result.values())

输出：

[['a', 'b'], ['c', 'e', 'd']]

注意，在上面，组件和组件中的元素都是随机顺序。