python中无向图中的连通组件

Question

在无向图中查找连通分量。图中的每个节点都包含一个标签及其邻居列表。这是链接：https://www.lintcode.com/problem/431/Leetcode需要会员才能回答这个问题。

class UndirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []

我用这种方法解决了它，但它返回[]

class Solution:
def connectedSet(self, nodes):
res=[]
visited=set()
def dfs(node,path):
if not node:
res.append(path.copy())
return
if node in visited:
return
visited.add(node)
for neighbor in node.neighbors:              
if neighbor not in visited:
print(path)
dfs(neighbor,path+[node.label])
for node in nodes:
if node not in visited:
dfs(node,[])
return res

返回[]。我相信它的逻辑是正确的。如果未访问节点，则运行深度优先搜索检查，直到不存在节点为止。

输入数据

{1,2,4#2,1,4#3,5#4,1,2#5,3}

预期结果

[[1,2,4],[3,5]]

结果

[]

Answer 1

您的条件if not node:没有意义：您没有修改节点或使它们成为Falsey。深度优先搜索探索一片有根树木的森林。节点上的外部循环查找这些树的根，因此您应该将对空列表的引用传递到dfs中，以跟踪在搜索树中查找该根的所有节点：

class Solution:
def connectedSet(self, nodes):
res = []
visited = set()
def dfs(node, path):
path.append(node.label)
visited.add(node)
for neighbor in node.neighbors:
if neighbor not in visited:
dfs(neighbor, path)
for node in nodes:
if node not in visited:
path = []
dfs(node, path)
res.append(sorted(path.copy()))
return res