in LintCode Algorithm Graph BFS ~ read.

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);
    }
}