<p>如果由于某种原因不能使用外部库,则可以实现以下算法:</p>
<pre><code>import pandas as pd
def bfs(graph, start):
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
def connected_components(G):
seen = set()
for v in G:
if v not in seen:
c = set(bfs(G, v))
yield c
seen.update(c)
def graph(edge_list):
result = {}
for source, target in edge_list:
result.setdefault(source, set()).add(target)
result.setdefault(target, set()).add(source)
return result
df = pd.DataFrame({'node1': ['2', '4', '17', '17', '205', '208'],
'node2': ['4', '13', '25', '38', '208', '300']})
G = graph(df[['node1', 'node2']].values)
components = connected_components(G)
lookup = {i: component for i, component in enumerate(components, 1)}
df['group'] = [label for node in df.node1 for label, component in lookup.items() if node in component]
print(df)
</code></pre>
<p><strong>输出</strong></p>
^{pr2}$