Find the Connected Component in the Undirected Graph
LintCode-431.Find the Connected Component in the Undirected Graph
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.)
Notice: Each connected component should sort by label.
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}
/**
* 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) {
List<List<Integer>> result = new ArrayList<>();
if (nodes == null || nodes.size() == 0) {
return result;
}
Set<UndirectedGraphNode> visited = new HashSet<>();
for (UndirectedGraphNode node : nodes) {
if (!visited.contains(node)) {
bfs(node, visited, result);
}
}
return result;
}
void bfs(UndirectedGraphNode node, Set<UndirectedGraphNode> visited, List<List<Integer>> result) {
List<Integer> list = new ArrayList<>();
Queue<UndirectedGraphNode> queue = new LinkedList<>();
visited.add(node);
queue.offer(node);
while (!queue.isEmpty()) {
UndirectedGraphNode current = queue.poll();
list.add(current.label);
for (UndirectedGraphNode n : current.neighbors) {
if (!visited.contains(n)) {
visited.add(n);
queue.offer(n);
}
}
}
Collections.sort(list);
result.add(list);
}
}