Sunday, April 16, 2017

Connected Component in Undirected Graph

Version #1 BFS

/**
 * 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) {
        // Write your code here
        List<List<Integer>> result = new ArrayList<>();
        if (nodes == null || nodes.size() == 0) return result;
        Set<Integer> visited = new HashSet<>();
        for (UndirectedGraphNode node : nodes) {
            if (!visited.contains(node.label)) {
                bfs(node, visited, result);
            }
        }
        return result;
    }
    private void bfs(UndirectedGraphNode node, Set<Integer> visited, List<List<Integer>> result) {
        Queue<UndirectedGraphNode> que = new LinkedList<>();
        List<Integer> subResult = new ArrayList<>();
        que.add(node);
        visited.add(node.label);
        UndirectedGraphNode curr;
        while (!que.isEmpty()) {
            curr = que.poll();
            subResult.add(curr.label);
            for (UndirectedGraphNode neighbor : curr.neighbors) {
                if (!visited.contains(neighbor.label)) {
                    que.offer(neighbor);
                    visited.add(neighbor.label);
                }
            }
        }
        Collections.sort(subResult);
        result.add(subResult);
    }
}

No comments:

Post a Comment