成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Find the Connected Component in the Undirected Gra

Benedict Evans / 2341人閱讀

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
     */
     
     
     

     //優(yōu)化點(diǎn)------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);
        
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66432.html

相關(guān)文章

  • [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 評論0 收藏0

  • leetcode310. Minimum Height Trees

    摘要：現(xiàn)在要求在這樣一棵生成樹中，找到生成樹的高度最低的所有根節(jié)點(diǎn)。然后利用鄰接表的相關(guān)屬性來判斷當(dāng)前節(jié)點(diǎn)是否是葉節(jié)點(diǎn)。度數(shù)為一的頂點(diǎn)就是葉節(jié)點(diǎn)。這里使用異或的原因是對同一個(gè)值進(jìn)行兩次異或即可以回到最初值。 題目 For an undirected graph with tree characteristics, we can choose any node as the root. The...

    xiaoxiaozi 評論0 收藏0

  • [基本算法] Detect Cycle in Directed/Undirected Graph 有

    摘要：不在的話，表示不構(gòu)成環(huán)，我們應(yīng)該合并這兩個(gè)集合因?yàn)榧由线@條邊，兩個(gè)集合就被連起來了，合并成了一個(gè)集合注意如果想要復(fù)雜度為必須用路徑壓縮。并查集寫法參考注意方法用找的老大哥，合并的是的老大哥。 Detect Cycle in Directed Graph 有向圖找環(huán) Given n nodes labeled from 0 to n - 1 and a list of directed...

    ymyang 評論0 收藏0

  • 323. Number of Connected Components in an Undirect

    摘要：題目鏈接這道題和是一個(gè)思路，一個(gè)初始化為，每次有新的就兩個(gè)節(jié)點(diǎn)，如果兩個(gè)節(jié)點(diǎn)原來不在一個(gè)連通圖里面就減少并且連起來，如果原來就在一個(gè)圖里面就不管。用一個(gè)索引來做，優(yōu)化就是加權(quán)了，每次把大的樹的當(dāng)做，小的樹的作為。 323. Number of Connected Components in an Undirected Graph 題目鏈接：https://leetcode.com/pr...

    zsy888 評論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 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<