2

グラフにサイクルが1つしかない場合、無向グラフでサイクルになる頂点を見つける方法は?

グラフでサイクルを見つけるためのコードがありますが、現在、どの頂点サイクルが作成されているかを見つけるコードが必要です。

サイクルを見つけるためのコード (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]);
        }
    }
}
4

3 に答える 3

6

単純な方法 - すべてのノードが次数 2 になるまで、次数 1 のノードを破棄します。これがグラフのサイクルです。

于 2013-07-07T22:23:56.220 に答える
0

私が正しければ、parent[] は配列です (parent[i] は、i 番目のノードにアクセスする直前に、vivted したノードの番号です)。

次に、グラフにサイクルが含まれている場合 (既にアクセスしたノードにアクセスした場合)、サイクル内に少なくとも 1 つのノードがあることがわかります (k 番目のノードと仮定します)。この場合、parent[k] ノードもサイクルに属し、parent[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-08T01:21:00.523 に答える