国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Graph: Detect cycle

eechen / 1963人閱讀

摘要：無向圖對于無向圖，需要記錄一個來判斷這是不是無向圖兩個之間的連接。同一層的節(jié)點會出現(xiàn)相連的情況。如果同一層的這個節(jié)點是等待訪問的，說明這兩個節(jié)點之間有連接，所以有環(huán)的出現(xiàn)。有向圖不需要記錄

Graph: Detect Cycle

Detect if any cycle exists in the graph.

無向圖

0 - 1
| /
2

對于無向圖，需要記錄一個previous node來判斷這是不是無向圖兩個node之間的連接。

DFS

// 0:unvisited, 1:visited, 2:visiting
public boolean hasCycle(Node root, Node prev) {
    if(root.state == 2) {
        return true;
    }
    root.state = 2;
    if(adj.get(root) != null) {
        for(Node node : adj.get(root)) {
            if(node != prev) {
                if(node.status != 1 && hasCycle(node, root)) {
                    return true;
                }
            }
        }
    }
    root.state = 1;
    return false;
}

BFS
同一層的節(jié)點會出現(xiàn)相連的情況。

public boolean hasCycle(Node root) {
    Queue q = new LinkedList<>();
    if(root != null) q.offer(root);
    root.state = 2;
    while(!q.isEmpty()) {
        Node cur = q.poll();
        for(Node adj : adjacent.get(cur)) {
            // 如果同一層的這個節(jié)點是等待訪問的，說明這兩個節(jié)點之間
            // 有連接，所以有環(huán)的出現(xiàn)。
            if(adj.state == 2) reture true;
            if(adj.state == 0) {
                q.offer(adj);
                adj.state = 2;
            }
        }
        cur.state = 1;
    }
    return false;
}
有向圖

不需要記錄previous node;

public boolean hasCycle(Node node) {
    if(node.state == 2) return false;
    node.state = 2;
    if(map.get(node) != null) {
        for(Node adj : map.get(node)) {
            if(adj.state != 1 && hasCycle(adj)) {
                return true;
            }
        }
    }
    node.state = 1;
    return false;
}

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/65233.html

相關(guān)文章

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

    摘要：不在的話，表示不構(gòu)成環(huán)，我們應(yīng)該合并這兩個集合因為加上這條邊，兩個集合就被連起來了，合并成了一個集合注意如果想要復(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

  • Graph: Topological Sort

    Graph: Topological Sort 利用和detect cycle類似的思路， 用dfs + recursion解決。并且一定時一個有向圖。 Stack stack = new Stack(); // 0:unvisit, 1:visited, 2:visiting public boolean topologicalSort(Node node) { if(node.stat...

    ShevaKuilin 評論0 收藏0

  • 261. Graph Valid Tree

    摘要：題目鏈接檢查圖的連通性及是否有環(huán)，可以，，從一個點出發(fā)看能不能遍歷所有的點，同時來檢查是否有環(huán)。還可以用檢查是否有環(huán)，最后看的數(shù)量是否等于來判斷是不是。 261. Graph Valid Tree 題目鏈接：https://leetcode.com/problems... 檢查圖的連通性及是否有環(huán)，可以dfs，bfs，從一個點出發(fā)看能不能遍歷所有的點，同時visited來檢查是否有環(huán)。...

    Jinkey 評論0 收藏0

  • 算法（第4版） Chapter 4 練習(xí)題 答案

    摘要：離心率計算題目釋義計算點的離心率，圖的直徑，半徑，中心計算圖的圍長定義點的離心率圖中任意一點，的離心率是圖中其他點到的所有最短路徑中最大值。圖的中心圖中離心率長度等于半徑的點。改動離心率計算，在遍歷中增加的賦值即可。 離心率計算 4.1.16 The eccentricity of a vertex v is the the length of the shortest path fr...

    13651657101 評論0 收藏0

  • 【Change Detection系列一】$digest 在Angular新版本中重生

    摘要：感謝您的閱讀如果喜歡這篇文章請點贊。它對我意義重大，它能幫助其他人看到這篇文章。對于更高級的文章，你可以在或上跟隨我。 I’ve worked with Angular.js for a few years and despite the widespread criticism I think this is a fantastic framework. I’ve started w...

    legendaryedu 評論0 收藏0

發(fā)表評論

0條評論

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