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.)
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}
Solution: BFS
public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) { List<List<Integer>> result = new ArrayList<>(); if (nodes == null || nodes.size() == 0) { return result; } Queue<UndirectedGraphNode> q = new LinkedList<>(); q.offer(nodes.get(0)); List<Integer> component = new ArrayList<>(); Set<UndirectedGraphNode> visited = new HashSet<>(); while (!nodes.isEmpty()) { if (q.isEmpty()) { Collections.sort(component); result.add(new ArrayList<>(component)); q.offer(nodes.get(0)); component = new ArrayList<>(); } else { UndirectedGraphNode curr = q.poll(); if (!visited.contains(curr)) { visited.add(curr); nodes.remove(curr); component.add(curr.label); for (UndirectedGraphNode neighbor : curr.neighbors) { q.offer(neighbor); } } } } if (!component.isEmpty()) { result.add(component); } return result; }