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

A------B  C
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      D   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;
}

Share