# Find the Connected Component in the Undirected Graph ### Source - lintcode: [(431) Find the Connected Component in the Undirected Graph](http://www.lintcode.com/en/problem/find-the-connected-component-in-the-undirected-graph/) ### Problem Find the number connected component in the undirected graph. Each node in thegraph contains a label and a list of its neighbors. (a connected component (orjust component) of an undirected graph is a subgraph in which any two verticesare connected to each other by paths, and which is connected to no additionalvertices 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](# "Depth-First Search, 深度優先搜索") 深搜加哈希表（因為有環，必須記錄節點是否被訪問過） ### Java ~~~ /** * Definition for Undirected graph. * class UndirectedGraphNode { * int label; * ArrayList<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * } */ public class Solution { /** * @param nodes a array of Undirected graph node * @return a connected set of a Undirected graph */ public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) { if (nodes == null || nodes.size() == 0) return null; List<List<Integer>> result = new ArrayList<List<Integer>>(); Set<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>(); for (UndirectedGraphNode node : nodes) { if (visited.contains(node)) continue; List<Integer> temp = new ArrayList<Integer>(); dfs(node, visited, temp); Collections.sort(temp); result.add(temp); } return result; } private void dfs(UndirectedGraphNode node, Set<UndirectedGraphNode> visited, List<Integer> result) { // add node into result result.add(node.label); visited.add(node); // node is not connected, exclude by for iteration // if (node.neighbors.size() == 0 ) return; for (UndirectedGraphNode neighbor : node.neighbors) { if (visited.contains(neighbor)) continue; dfs(neighbor, visited, result); } } } ~~~ ### 源碼分析 注意題目的輸出要求，需要為 Integer 和有序。添加 node 至 result 和 visited 時放一起，且只在 [dfs](# "Depth-First Search, 深度優先搜索") 入口，避免漏解和重解。 ### 復雜度分析 遍歷所有節點和邊一次，時間復雜度 O(V+E)O(V+E)O(V+E), 記錄節點是否被訪問，空間復雜度 O(V)O(V)O(V). ### 題解2 - [BFS](# "Breadth-First Search, 廣度優先搜索") 深搜容易爆棧，采用 [BFS](# "Breadth-First Search, 廣度優先搜索") 較為安全。[BFS](# "Breadth-First Search, 廣度優先搜索") 中記錄已經訪問的節點在入隊前判斷，可有效防止不重不漏。 ### Java ~~~ /** * Definition for Undirected graph. * class UndirectedGraphNode { * int label; * ArrayList<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * } */ public class Solution { /** * @param nodes a array of Undirected graph node * @return a connected set of a Undirected graph */ public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) { if (nodes == null || nodes.size() == 0) return null; List<List<Integer>> result = new ArrayList<List<Integer>>(); // log visited node before push into queue Set<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>(); for (UndirectedGraphNode node : nodes) { if (visited.contains(node)) continue; List<Integer> row = bfs(node, visited); result.add(row); } return result; } private List<Integer> bfs(UndirectedGraphNode node, Set<UndirectedGraphNode> visited) { List<Integer> row = new ArrayList<Integer>(); Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>(); q.offer(node); visited.add(node); while (!q.isEmpty()) { UndirectedGraphNode qNode = q.poll(); row.add(qNode.label); for (UndirectedGraphNode neighbor : qNode.neighbors) { if (visited.contains(neighbor)) continue; q.offer(neighbor); visited.add(neighbor); } } Collections.sort(row); return row; } } ~~~ ### 源碼分析 略 ### 復雜度分析 同題解一。 ### Reference - [Find the Connected Component in the Undirected Graph 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/find-the-connected-component-in-the-undirected-graph/)