問題:
一部のリストが共有しているリストのリストを考えてみましょう。共通の要素。タスクは、これらの共有要素を通じて相互接続されているすべてのリストを、これ以上マージできなくなるまでマージすることです。
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 サイトの他の関連記事を参照してください。