Find the Connected Component in the Undirected Gra

Benedict Evans 發布于2019-08-14 17:07 / 2339人閱讀

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);
        
    }
}

GPU云服務器云服務器 the sdp for the webrtc FIND_IN_SET Connected

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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