python 无向图中的连通分量

Question

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

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

我用这种方法解决了，但是 returns []

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

这个returns[]。我相信它的逻辑是正确的。运行深度优先搜索检查节点是否未被访问，直到没有节点存在。

输入数据

 {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

python 无向图中的连通分量

Connected Component in Undirected Graph in python

python

algorithm

graph-theory

depth-first-search