<p>在许多情况下,将问题建模为图形可以使相当复杂的任务变得更容易。在这种情况下,从图论的角度来看,我们要寻找的是图的<a href="https://en.wikipedia.org/wiki/Component_(graph_theory)" rel="noreferrer">connected components</a></p>
<p>一个简单的方法是用<a href="https://networkx.github.io/" rel="noreferrer">NetworkX</a>生成一个图,然后用<a href="https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.DiGraph.add_edges_from.html" rel="noreferrer">^{<cd1>}</a>将列表添加为图边。然后使用<a href="https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.components.connected.connected_components.html" rel="noreferrer">^{<cd2>}</a>,它将精确地为您提供图形中连接组件集的列表:</p>
<pre><code>import networkx as nx
L = [['John','Sayyed'], ['John' , 'Simon'] ,['bush','trump']]
G=nx.Graph()
G.add_edges_from(L)
list(nx.connected_components(G))
[{'John', 'Sayyed', 'Simon'}, {'bush', 'trump'}]
</code></pre>
<hr/>
<h3>有多个(>;2)项的子列表如何?</h3>
<p>如果子列表包含超过<code>2</code>个元素,则可以<em>将它们添加为路径</em>,而不是使用<code>nx.add_path</code>的节点,因为它们可以连接多个节点:</p>
<pre><code>L = [['John','Sayyed'], ['John' , 'Simon'] ,['bush','trump'],
['Sam','Suri','NewYork'],['Suri','Orlando','Canada']]
G=nx.Graph()
for l in L:
nx.add_path(G, l)
list(nx.connected_components(G))
[{'John', 'Sayyed', 'Simon'},
{'bush', 'trump'},
{'Canada', 'NewYork', 'Orlando', 'Sam', 'Suri'}]
</code></pre>
<p>我们还可以使用<a href="https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.drawing.nx_pylab.draw.html" rel="noreferrer">^{<cd5>}</a>将这些连接的组件形象化:</p>
<pre><code>pos = nx.spring_layout(G, scale=20, k=2/np.sqrt(G.order()))
nx.draw(G, pos, node_color='lightgreen', node_size=1000, with_labels=True)
</code></pre>
<p><a href="https://i.stack.imgur.com/fV0R4.png" rel="noreferrer"><img src="https://i.stack.imgur.com/fV0R4.png" alt="enter image description here"/></a></p>
<hr/>
<h3>关于连通分量(图论)</h3>
<p>关于<a href="https://en.wikipedia.org/wiki/Connected_component_(graph_theory)" rel="noreferrer">connected components</a>的更详细解释:</p>
<blockquote>
<p>In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph</p>
</blockquote>
<p>因此,本质上,这段代码创建了一个图,带有列表中的边,其中每条边由两个值<code>u,v</code>组成,其中<code>u</code>和<code>v</code>将是该边连接的节点</p>
<p>因此,子列表与至少一个子列表和一个公共元素的并集可以转化为图论问题,因为所有节点都可以通过现有路径相互访问</p>