Connected Component in Undirected Graph in python

user_10262805 0
Viewed 235

Find connected component in undirected graph. Each node in the graph contains a label and a list of its neighbors. this is the link: https://www.lintcode.com/problem/431/ Leetcode requires membership for this question.

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

I solved it this way but it 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

This returns []. I belive its logic correct. Run depth first search checking if the node is not visited, till no node exists.

Input Data

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

Expected Result

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

Result

[]
depth-first-search graph-theory algorithm python
1 Answers

Your condition if not node: doesn't make sense: you're not modifying nodes or making them Falsey. Depth first search explores a forest of rooted trees. Your outer loop over nodes looks for the roots of these trees, so you should just pass a reference to an empty list into dfs, to track all the nodes explored in the search tree for that root:

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
user_167571740
Related