0

我是图论的新手。假设有一个连通无向图。我想知道它是否有一个奇数长度的循环。我可以使用 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;
}
4

1 回答 1

3

属性“2-colorable”也称为“二分”。在这种情况下，使用 DFS 还是 BFS 无关紧要。当您访问图形的节点时，将它们标记为 0 / 1，具体取决于您来自的邻居的颜色。如果您发现一个节点已经被标记，但标记与您在访问时标记的不同，则存在一个奇数长度的循环。如果没有出现这样的节点，则不存在奇数长度的循环。

于 2012-07-03T15:03:53.477 回答