什麼是奇數長度循環，我如何知道圖中是否有奇怪的循環？

我是圖論新手。假設有一個連通和無向圖。我想知道是否有一個奇怪的長度週期。我可以使用BFS查找圖表中是否存在循環。我還沒有學過DFS。這裏是我的代碼，只要找到是否有一個循環。提前致謝。什麼是奇數長度循環，我如何知道圖中是否有奇怪的循環？

#include<iostream> 
#include<vector> 
#include<queue> 
#include<cstdio> 
#define max 1000 

using namespace std; 

bool find_cycle(vector<int> adjacency_list[]); 

int main(void) 
{ 
    freopen("input.txt","r",stdin); 
freopen("output.txt","w",stdout); 

int vertex, edge; 
vector<int> adjacency_list[max]; 

cin >> vertex >> edge; 

//Creating the adjacency list 
for(int i=1; i<=edge; i++) 
{ 
    int n1, n2; 
    cin >> n1 >> n2; 

    adjacency_list[n1].push_back(n2); 
    adjacency_list[n2].push_back(n1); 
} 

if(find_cycle(adjacency_list)) 
    cout << "There is a cycle in the graph" << endl; 
else cout << "There is no cycle in the graph" << endl; 

return 0; 
} 

bool find_cycle(vector<int> adjacency_list[]) 
{ 
queue<int> q; 
bool taken[max]= {false}; 
int parent[max]; 

q.push(1); 
taken[1]=true; 
parent[1]=1; 

//breadth first search 
while(!q.empty()) 
{ 
    int u=q.front(); 
    q.pop(); 

    for(int i=0; i<adjacency_list[u].size(); i++) 
    { 
     int v=adjacency_list[u][i]; 

     if(!taken[v]) 
     { 
      q.push(v); 
      taken[v]=true; 
      parent[v]=u; 
     } 
     else if(v!=parent[u]) return true; 
    } 
} 

return false; 
}

來源

2012-07-03 eddard.stark

提示：一個圖沒有奇怪的週期，當且僅當它是[2-colorable]（http://en.wikipedia.org/wiki/Bipartite_graph）。 –

@AdamRosenfield，非常感謝。 –

@AdamRosenfield，我應該搜索整個圖還是僅搜索由循環組成的子圖。因爲圖中可能有多個循環。 –

屬性「2-colorable」也被稱爲「雙色」。在這種情況下，不管你使用DFS還是BFS都不重要;當您訪問圖的節點時，根據您來自的鄰居的顏色，將它們標記爲0/1。如果你發現一個已經被標記的節點，但是標記的方式與訪問時標記的方式不同，則會有一個奇數長度的週期。如果不存在這樣的節點，則不存在奇數長度的循環。

來源

2012-07-03 15:03:53 anonymous

非常感謝。 :) –

什麼是奇數長度循環，我如何知道圖中是否有奇怪的循環？

回答

相關問題