Find the Connected Component in the Undirected Graph

Question

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.)

Solution

找了一下資料，跟 graph 有關的題目都可以用 Union Find 來做看看。這題的思路基本上可以分成兩種：

1. DFS：把任何一點放進備選答案中，然後用 HashSet 來記錄有沒有訪問過，如果沒有訪問過，就對他的 neighbor 再進行一次 DFS
2. BFS：把點放進 queue 裡面，poll 出來時，把它加入備選答案裡，然後一樣將 neighbor 加入 queue 中，一直做到 queue 為空

DFS:

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) {
        if (nodes == null || nodes.size() == 0) return null;

        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Set<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
        for (UndirectedGraphNode node : nodes) {
            if (visited.contains(node)) continue;
            List<Integer> temp = new ArrayList<Integer>();
            dfs(node, visited, temp);
            Collections.sort(temp);
            result.add(temp);
        }

        return result;
    }

    private void dfs(UndirectedGraphNode node,
                     Set<UndirectedGraphNode> visited,
                     List<Integer> 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);
        }
    }
}

BFS

public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
        List<List<Integer>> rst = new ArrayList<>();
        if (nodes == null || nodes.size() == 0) {
            return rst;
        }
        //Init:
        Set<UndirectedGraphNode> checked = new HashSet();
        Queue<UndirectedGraphNode> queue = new LinkedList();
        ArrayList<Integer> component = new ArrayList<Integer>();

        queue.offer(nodes.get(0));

        while (!nodes.isEmpty()) {
            if (queue.isEmpty()) {
                Collections.sort(component);
                rst.add(component);
                queue.offer(nodes.get(0));
                component = new ArrayList<Integer>();
            } else {
                UndirectedGraphNode curr = queue.poll();
                if (!checked.contains(curr)) {
                    checked.add(curr);
                    component.add(curr.label);
                    nodes.remove(curr);
                    for (UndirectedGraphNode node : curr.neighbors) {
                            queue.add(node);    
                    }
                }
            }
        }
        if (!component.isEmpty()) {
            rst.add(component);
        }
        return rst;
    }