無向圖中的週期屬性是什麼？

我試圖理解這段代碼從檢測週期： http://algs4.cs.princeton.edu/41undirected/Cycle.java.html 無向圖中的週期屬性是什麼？

因此，如果一個頂點W是沒有標記或發現，繼續運行DFS。如果它被發現，它不等於你...爲什麼我在構造函數中傳遞-1？

我很困惑其他如果（w！= u）。爲什麼這會導致一個循環？

public Cycle(Graph G) { 
     if (hasSelfLoop(G)) return; 
     if (hasParallelEdges(G)) return; 
     marked = new boolean[G.V()]; 
     edgeTo = new int[G.V()]; 
     for (int v = 0; v < G.V(); v++) 
      if (!marked[v]) 
       dfs(G, -1, v); 
    } 

private void dfs(Graph G, int u, int v) { 
     marked[v] = true; 
     for (int w : G.adj(v)) { 

      // short circuit if cycle already found 
      if (cycle != null) return; 

      if (!marked[w]) { 
       edgeTo[w] = v; 
       dfs(G, v, w); 
      } 

      // check for cycle (but disregard reverse of edge leading to v) 
      else if (w != u) { 
       cycle = new Stack<Integer>(); 
       for (int x = v; x != w; x = edgeTo[x]) { 
        cycle.push(x); 
       } 
       cycle.push(w); 
       cycle.push(v); 
      } 
     } 
    }

來源

2014-05-19 runners3431

該算法在圖上進行深度優先搜索，並標記它遇到的任何頂點。用先前訪問的頂點（u）和當前訪問的頂點（v）調用方法dfs，其中v是u的後繼。如果v的下一個繼任者未標記（if (!marked[w])），則繼續搜索。否則，我們找到一個圓圈。

但是，如果在兩個方向上都存在邊緣，則此實現的確不是而是將其視爲圓圈。 w是v的鄰居。如果它是u本身（v的先驅），我們有這種情況。因此，代碼檢查這是不是的情況下（w != u），即我們有不是一個biderectional邊緣，所以我們做找到了一個圓圈。

來源

2014-05-19 20:06:32

你能再解釋'你'嗎？對我來說不是很清楚。如果W = U讓我們知道我們已經到達了ccycle？我不明白爲什麼它！=。 – runners3431

方法'dfs'被以前訪問過的頂點（'u'）和下一個要訪問的頂點（'v'）調用，'v'是'u'的後繼。 –

@SimonS請將解釋添加到您的答案中，不要寫在評論中！ –

無向圖中的週期屬性是什麼？

回答

相關問題