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" は "bipartite" とも呼ばれます。この場合、DFS を使用するか BFS を使用するかは問題ではありません。グラフのノードにアクセスすると、元の隣接ノードの色に応じて、0 / 1 のラベルを交互に付けます。すでにラベルが付けられているが、訪問したときにラベルを付けるのとは異なるラベルが付けられているノードを見つけた場合、奇数の長さのサイクルがあります。そのようなノードが発生しない場合、奇数長のサイクルはありません。

于 2012-07-03T15:03:53.477 に答える