Find the Connected Component in the Undirected Gra

Benedict Evans 发布于2019-08-14 17:07 / 2174人阅读

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> connectedSet(ArrayList nodes) {
       int m = nodes.size();
        Map visited = new HashMap<>();
        
       for (UndirectedGraphNode node : nodes){
            visited.put(node, false);
       }
        
        List> result = new ArrayList<>();
        
        for (UndirectedGraphNode node : nodes){
            if (visited.get(node) == false){
                bfs(node, visited, result);
            }
        }
        
        return result;
    }
    
     public void bfs(UndirectedGraphNode node, Map visited, List> result){
        Listrow = new ArrayList<>();
        Queue 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);
        
    }
}

云服务器私有云 the sdp for the webrtc FIND_IN_SET Connected

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66432.html

[LeetCode] 684. Redundant Connection

Problem In this problem, a tree is an undirected graph that is connected and has no cycles. The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one...

lncwwn 2019-08-16 13:55 评论0 收藏0
leetcode310. Minimum Height Trees

摘要：现在要求在这样一棵生成树中，找到生成树的高度最低的所有根节点。然后利用邻接表的相关属性来判断当前节点是否是叶节点。度数为一的顶点就是叶节点。这里使用异或的原因是对同一个值进行两次异或即可以回到最初值。题目 For an undirected graph with tree characteristics, we can choose any node as the root. The...

xiaoxiaozi 2019-08-16 13:46 评论0 收藏0
[基本算法] Detect Cycle in Directed/Undirected Graph 有

摘要：不在的话，表示不构成环，我们应该合并这两个集合因为加上这条边，两个集合就被连起来了，合并成了一个集合注意如果想要复杂度为必须用路径压缩。并查集写法参考注意方法用找的老大哥，合并的是的老大哥。 Detect Cycle in Directed Graph 有向图找环 Given n nodes labeled from 0 to n - 1 and a list of directed...

ymyang 2019-08-14 14:04 评论0 收藏0
323. Number of Connected Components in an Undirect

摘要：题目链接这道题和是一个思路，一个初始化为，每次有新的就两个节点，如果两个节点原来不在一个连通图里面就减少并且连起来，如果原来就在一个图里面就不管。用一个索引来做，优化就是加权了，每次把大的树的当做，小的树的作为。 323. Number of Connected Components in an Undirected Graph 题目链接：https://leetcode.com/pr...

zsy888 2019-08-14 17:27 评论0 收藏0
[LeetCode] Graph Valid Tree [Union Find]

Problem Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. Example Given n = 5 and...

104828720 2019-08-14 15:10 评论0 收藏0