グラフ理論を使用して相互接続されたリストをマージするにはどうすればよいですか?

相互接続されたリストのマージ: グラフベースのソリューション

問題:

一部のリストが共有しているリストのリストを考えてみましょう。共通の要素。タスクは、これらの共有要素を通じて相互接続されているすべてのリストを、これ以上マージできなくなるまでマージすることです。

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']] 

解決策:

この問題はグラフとしてアプローチできます。この問題では、リストは共有要素を介して接続されたノードを表します。目標は、このグラフ内の連結成分を見つけることです。グラフ分析用の Python ライブラリである NetworkX の機能を活用して、この問題を効率的に解決できます。

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 中国語 Web サイトの他の関連記事を参照してください。