亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專(zhuān)欄INFORMATION COLUMN

Graph: Detect cycle

eechen / 2030人閱讀

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

Graph: Detect Cycle

Detect if any cycle exists in the graph.

無(wú)向圖

0 - 1
| /
2

對(duì)于無(wú)向圖，需要記錄一個(gè)previous node來(lái)判斷這是不是無(wú)向圖兩個(gè)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é)點(diǎn)會(huì)出現(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)) {
            // 如果同一層的這個(gè)節(jié)點(diǎn)是等待訪問(wèn)的，說(shuō)明這兩個(gè)節(jié)點(diǎn)之間
            // 有連接，所以有環(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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/65233.html

相關(guān)文章

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

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

    ymyang 評(píng)論0 收藏0

  • Graph: Topological Sort

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

    ShevaKuilin 評(píng)論0 收藏0

  • 261. Graph Valid Tree

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

    Jinkey 評(píng)論0 收藏0

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

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

    13651657101 評(píng)論0 收藏0

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

    摘要：感謝您的閱讀如果喜歡這篇文章請(qǐng)點(diǎn)贊。它對(duì)我意義重大，它能幫助其他人看到這篇文章。對(duì)于更高級(jí)的文章，你可以在或上跟隨我。 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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<