如何使用图论合并互连列表？

合并互连列表：基于图的解决方案

问题：

考虑一个列表列表，其中一些共享共同元素。任务是合并通过这些共享元素互连的所有列表，直到无法进一步合并为止。

Input: [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
Expected Output: [['a','b','c','d','e','f','g','o','p'],['k']] 

解决方案：

问题可以用图表来解决问题，其中列表表示通过共享元素连接的节点。目标是找到该图中的连接组件。我们可以利用 NetworkX（一个用于图形分析的 Python 库）的强大功能来有效地解决这个问题。

import networkx 
from networkx.algorithms.components.connected import connected_components

# Convert the list of lists into a graph
def to_graph(l):
    G = networkx.Graph()
    for part in l:
        # Add nodes
        G.add_nodes_from(part)
        # Add edges between nodes
        G.add_edges_from(to_edges(part))
    return G

# Generate edges from a list of nodes
def to_edges(l):
    it = iter(l)
    last = next(it)
    for current in it:
        yield last, current
        last = current

# Create the graph and find connected components
G = to_graph(l)
components = connected_components(G)

# Print the merged lists (connected components)
print(list(components))

输出：

[['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]

通过利用 NetworkX ，这种方法通过查找连接的组件有效地解决了问题，为基于共享元素的合并列表提供了稳健且正确的解决方案。

以上是如何使用图论合并互连列表？的详细内容。更多信息请关注PHP中文网其他相关文章！