Find the Connected Component in the Undirected Graph
Written on October 21, 2015
Tweet
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.)
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<List<Integer>>();
//if (nodes == null || nodes.size() == 0) return result;
HashMap<UndirectedGraphNode, Boolean> visited = new HashMap<UndirectedGraphNode, Boolean>();
for (UndirectedGraphNode node : nodes) {
visited.put(node, false);
}
for (UndirectedGraphNode node : nodes) {
if (!visited.get(node)) {
result.add(bfs(node, visited));
}
}
return result;
}
public List<Integer> bfs(UndirectedGraphNode node, HashMap<UndirectedGraphNode, Boolean> visited) {
List<Integer> list = new ArrayList<Integer>();
LinkedList<undirectedgraphnode> q = new LinkedList<undirectedgraphnode>();
q.add(node);
visited.put(node, true);
while (!q.isEmpty()) {
node = q.poll();
list.add(node.label);
for (UndirectedGraphNode neighbor : node.neighbors) {
if (!visited.get(neighbor)) {
q.add(neighbor);
visited.put(neighbor, true);
}
}
}
Collections.sort(list);
return list;
}
}