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