Find the Connected Component in the Undirected Graph

最后更新于:2022-04-02 01:13:38

# 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 neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList(); } * } */ public class Solution { /** * @param nodes a array of Undirected graph node * @return a connected set of a Undirected graph */ public List> connectedSet(ArrayList nodes) { if (nodes == null || nodes.size() == 0) return null; List> result = new ArrayList>(); Set visited = new HashSet(); for (UndirectedGraphNode node : nodes) { if (visited.contains(node)) continue; List temp = new ArrayList(); dfs(node, visited, temp); Collections.sort(temp); result.add(temp); } return result; } private void dfs(UndirectedGraphNode node, Set visited, List 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 neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList(); } * } */ public class Solution { /** * @param nodes a array of Undirected graph node * @return a connected set of a Undirected graph */ public List> connectedSet(ArrayList nodes) { if (nodes == null || nodes.size() == 0) return null; List> result = new ArrayList>(); // log visited node before push into queue Set visited = new HashSet(); for (UndirectedGraphNode node : nodes) { if (visited.contains(node)) continue; List row = bfs(node, visited); result.add(row); } return result; } private List bfs(UndirectedGraphNode node, Set visited) { List row = new ArrayList(); Queue q = new LinkedList(); 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/)
';