如何找到什麼頂點由週期無向圖如果只有一個圖表週期？

如何找到什麼頂點由週期無向圖如果只有一個圖表週期？如何找到什麼頂點由週期無向圖如果只有一個圖表週期？

我有一些代碼在圖中尋找週期，但現在我需要的代碼，將發現的頂點週期是由什麼。

下面是用於發現循環碼（在C++）：

bool dfs(int x) 
{ 
    state[x] = 1; 
    for(int j = 0; j < ls[x].size(); j++) 
    { 
     if(state[ls[x][j]] == 1 and parent[x] != ls[x][j]) 
     { 
      t = 0; // Graph contains cycle. 
      return t; 
     } 
     if(state[ls[x][j]] == 0) 
     { 
      parent[ls[x][j]] = x; 
      dfs(ls[x][j]); 
     } 
    } 
} 

void detect_cycle() 
{ 
    memset(state, 0, sizeof state); 
    memset(parent, 0, sizeof parent); 
    for(int i = 1; i <= n; i++) 
     if(state[i] == false) 
      dfs(i); 
}

感謝。

這是最終的代碼。多謝你們。

bool dfs(int x) 
{ 
    state[x] = 1; 
    for(int j = 0; j < ls[x].size(); j++) 
    { 
     if(state[ls[x][j]] == 1 and parent[x] != ls[x][j]) 
     { 
      if(t) 
      { 
       printf("Cycle entry: %d\n", ls[x][j]); 
       printf("Cycle contains: %d, %d ", ls[x][j], x); 
       int cycleNode = parent[x]; 
       while(cycleNode != ls[x][j]) 
       { 
        printf("%d ", cycleNode); 
        cycleNode = parent[cycleNode]; 
       } 
      } 
      t = 0; 
      return t; 
     } 
     if(state[ls[x][j]] == 0) 
     { 
      parent[ls[x][j]] = x; 
      dfs(ls[x][j]); 
     } 
    } 
}

來源

2013-07-07 user2555240

如果我正確的，那麼父[]是一個數組（父[i]是你vivted您訪問的第i個直前的節點的數量）。

然後你知道，如果圖包含循環（您訪問已訪問節點），你知道在週期中至少一個節點（假設其第k個一個）。在這種情況下，父[k]節點也屬於循環，父母[parent [k]]等。

所以，我們得到了下面的代碼：

#include <iostream> 
#include <vector> 
#include <string> 
#include <algorithm> 
#include <set> 
#include <map> 
using namespace std; 

vector <int> state; 
vector <vector <int> > ls; //graph 
vector <int> parent; 
bool t = 1; 
int theNodeInTheCycle; 

void dfs(int x) 
{ 
    state[x] = 1; 
    for(int j = 0; j < ls[x].size(); j++) 
    { 
      if(state[ls[x][j]] == 1 && parent[x] != ls[x][j]) 
      { 
        parent[ls[x][j]] = x; 
        theNodeInTheCycle = ls[x][j]; //ls[x][j] belongs to the cycle since state[ls[x][j]]==1 
        t = 0; 
      } 
      if(state[ls[x][j]] == 0) 
      { 
        parent[ls[x][j]] = x; 
        dfs(ls[x][j]); 
      } 
    } 
} 

vector <int> GetCycle() 
{ 
    vector <int> cycle; 
    int firstNodeInTheCycle = theNodeInTheCycle; 
    do 
    { 
      theNodeInTheCycle = parent[theNodeInTheCycle]; 
      cycle.push_back (theNodeInTheCycle); 
    } while (theNodeInTheCycle != firstNodeInTheCycle); 

    reverse (cycle.begin(), cycle.end()); //to get them in the right order 
    return cycle; 
} 

int main() 
{ 
    int n; cin>>n; //the number of nodes (from 0 to n-1) 
    int m; cin>>m; //the number of edges 

    state.resize (n); 
    ls.resize (n); 
    parent.resize (n); 

    for (int i = 0; i < m; ++i) 
    { 
      int a, b; cin>>a>>b; 
      ls[a].push_back(b); 
      ls[b].push_back(a); 
    } 

    for (int i = 0; i<n; ++i) 
      if (state[i]==0) 
        dfs(i); 

    if (t==0) 
    { 
      vector <int> cycle = GetCycle(); 
      for (int i = 0; i < cycle.size(); ++i) 
        cout<<cycle[i]<<" "; 
      cout<<"\n"; 
    } 
    else cout<<"No cycle\n"; 
}

來源

2013-07-08 01:21:00 h8red

嘿，tnx。我不知道爲什麼，但是你的代碼運行無限循環。但這是我的代碼。這和你的一樣。謝謝。 – user2555240

是的，對不起。我重寫了它;現在它應該工作並輸出循環中的節點（按照我們訪問過的順序）。代碼：http://ideone.com/xlFo3U – h8red

一種天真的方法 - 扔掉1度的任何節點，直到所有節點都具有2度。這是圖中的週期。

來源

2013-07-07 22:23:56

+1困難得多拿錯比使用遍歷，和一樣快。 –

+1對於一個好主意。但是你如何實現它在'O（E）'中運行？ – banarun

+1好主意和@banarun非常簡單，如果你使用鄰接列表來定義一個圖表\ Matrix –

當您運行DFS，如果一個頂點被標記時，DFS（）之前，必須有一個週期。

 A 
/
    B 
| \ 
C E 
    \/
    D

如果只有一個在圖中週期，標記前頂點是循環的入口，如下面B，無論DFS的開始頂點。並在代碼中，

if(state[ls[x][j]] == 1 and parent[x] != ls[x][j]) 
{ 
    t = 0; // Graph contains cycle. 
    return t; 
}

在第一if() {}，家長和t是不必要的，更改爲：

if(state[ls[x][j]] == 1 and parent[x] != ls[x][j]) 
{ 
    cout<<"cycle's entry:"<<j<<endl; 
    // Graph contains cycle. 
    return false; 
}

之外，你的代碼需要的dfs()的for外return true;。

來源

2013-07-08 01:02:40 vvy

如何找到什麼頂點由週期無向圖如果只有一個圖表週期？

回答

相關問題