Find the Connected Component in the Undirected Graph

Question

• lintcode: (431) Find the Connected Component in the Undirected Graph

Problem Statement

Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (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.)

Example

Given graph:

A------B  C
 \     |  |
  \    |  |
   \   |  |
    \  |  |
      D   E

Return {A,B,D}, {C,E}. Since there are two connected component which is {A,B,D}, {C,E}

题解1 - DFS

深搜加哈希表（因为有环，必须记录节点是否被访问过）

• reference

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

class Solution:
    # @param {UndirectedGraphNode[]} nodes a array of undirected graph node
    # @return {int[][]} a connected set of a undirected graph
    def dfs(self, x, tmp):
        self.v[x.label] = True
        tmp.append(x.label)
        for node in x.neighbors:
            if not self.v[node.label]:
                self.dfs(node, tmp)

    def connectedSet(self, nodes):
        # Write your code here
        self.v = {}
        for node in nodes:
            self.v[node.label] = False

        ret = []
        for node in nodes:
            if not self.v[node.label]:
                tmp = []
                self.dfs(node, tmp)
                ret.append(sorted(tmp))
        return ret

sol=Solution()
A=UndirectedGraphNode('A')
B=UndirectedGraphNode('B')
C=UndirectedGraphNode('C')
D=UndirectedGraphNode('D')
E=UndirectedGraphNode('E')

A.neighbors=[B,D]
B.neighbors=[A,D]
D.neighbors=[A,B]
C.neighbors=[E]
E.neighbors=[C]
nodes=[A,B,C,D,E]

sol.connectedSet(nodes)

源码分析

注意题目的输出要求，需要为 Integer 和有序。添加 node 至 result 和 visited 时放一起，且只在 dfs 入口，避免漏解和重解。

复杂度分析

遍历所有节点和边一次，时间复杂度 $$O(V+E)$$, 记录节点是否被访问，空间复杂度 $$O(V)$$.

题解2 - BFS

深搜容易爆栈，采用 BFS 较为安全。BFS 中记录已经访问的节点在入队前判断，可有效防止不重不漏。