如何使用圖論合併互連列表？

合併互連列表：基於圖的解決方案

問題：

考慮一個列表共同元素。任務是合併透過這些共享元素互連的所有列表，直到無法進一步合併為止。

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中文網其他相關文章！