脚本宝典收集整理的这篇文章主要介绍了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.)
Solution
BFS + Hashmap -------- get all nodes by BFS, record visited by hashmap
public class Solution {
/**
* @param nodes a array of Undirected graph node
* @return a connected set of a Undirected graph
*/
//优化点------boolea[] visited instead of arraylist.contains()
public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
int m = nodes.size();
Map<UndirectedGraphNode, Boolean> visited = new HashMap<>();
for (UndirectedGraphNode node : nodes){
visited.put(node, false);
}
List<List<Integer>> result = new ArrayList<>();
for (UndirectedGraphNode node : nodes){
if (visited.get(node) == false){
bfs(node, visited, result);
}
}
return result;
}
public void bfs(UndirectedGraphNode node, Map<UndirectedGraphNode, Boolean> visited, List<List<Integer>> result){
List<Integer>row = new ArrayList<>();
Queue<UndirectedGraphNode> queue = new LinkedList<>();
visited.put(node, true);
queue.offer(node);
while (!queue.isEmpty()){
UndirectedGraphNode u = queue.poll();
row.add(u.label);
for (UndirectedGraphNode v : u.neighbors){
if (visited.get(v) == false){
visited.put(v, true);
queue.offer(v);
}
}
}
Collections.sort(row);
result.add(row);
}
}
以上是脚本宝典为你收集整理的Find the Connected Component in the Undirected Graph全部内容,希望文章能够帮你解决Find the Connected Component in the Undirected Graph所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。