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/)
';