2

如果图中只有一个循环，如何找到无向图中的哪些顶点是循环的？

我有在图中查找循环的代码，但现在我需要能够找到生成哪些顶点循环的代码。

这是用于查找循环的代码（在 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

一种天真的方法 - 只需丢弃任何度数为 1 的节点，直到所有节点的度数为 2。这就是图中的循环。

于 2013-07-07T22:23:56.220 回答
0

如果我是对的，那么 parent[] 是一个数组（parent[i] 是您在访问第 i 个之前直接激活的节点的编号）。

然后你知道如果图包含循环（你访问一个你已经访问过的节点），你知道循环中至少有一个节点（假设它是第 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 回答
0

运行dfs时，如果之前dfs()时标记了一个顶点，则一定有一个循环。

     A
   /
  B
 |  \
 C  E
  \ /
   D

如果图中只有一个环，无论dfs的起始顶点是什么，前面标记的顶点都是环的入口，如下图B。在你的代码中，

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

在第一个if() {}， parent 和 t 是不必要的，更改为：

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

此外，您的代码需要一个return true;外部for的dfs().

于 2013-07-08T01:02:40.287 回答