我如何才能找到(遍历)有向图中从/到给定节点的所有周期?

例如,我想要这样的东西:

A->B->A
A->B->C->A

而不是: B - > C > B


当前回答

DFS c++版本的伪代码在二楼的答案:

void findCircleUnit(int start, int v, bool* visited, vector<int>& path) {
    if(visited[v]) {
        if(v == start) {
            for(auto c : path)
                cout << c << " ";
            cout << endl;
            return;
        }
        else 
            return;
    }
    visited[v] = true;
    path.push_back(v);
    for(auto i : G[v])
        findCircleUnit(start, i, visited, path);
    visited[v] = false;
    path.pop_back();
}

其他回答

我在搜索中找到了这个页面,由于循环与强连接组件不相同,我继续搜索,最后,我找到了一个高效的算法,它列出了有向图的所有(基本)循环。这篇论文来自唐纳德·b·约翰逊(Donald B. Johnson),可以在以下链接中找到:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

java实现可以在下面找到:

http://normalisiert.de/code/java/elementaryCycles.zip

约翰逊算法的Mathematica演示可以在这里找到,实现可以从右边下载(“下载作者代码”)。

注:实际上,这个问题有很多算法。本文列举了其中一些:

http://dx.doi.org/10.1137/0205007

根据文章,Johnson的算法是最快的。

关于你关于排列周期的问题,请在这里阅读更多: https://www.codechef.com/problems/PCYCLE

您可以尝试以下代码(输入大小和数字number):

# include<cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);

    int num[1000];
    int visited[1000]={0};
    int vindex[2000];
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);

    int t_visited=0;
    int cycles=0;
    int start=0, index;

    while(t_visited < n)
    {
        for(int i=1;i<=n;i++)
        {
            if(visited[i]==0)
            {
                vindex[start]=i;
                visited[i]=1;
                t_visited++;
                index=start;
                break;
            }
        }
        while(true)
        {
            index++;
            vindex[index]=num[vindex[index-1]];

            if(vindex[index]==vindex[start])
                break;
            visited[vindex[index]]=1;
            t_visited++;
        }
        vindex[++index]=0;
        start=index+1;
        cycles++;
    }

    printf("%d\n",cycles,vindex[0]);

    for(int i=0;i<(n+2*cycles);i++)
    {
        if(vindex[i]==0)
            printf("\n");
        else
            printf("%d ",vindex[i]);
    }
}

DFS c++版本的伪代码在二楼的答案:

void findCircleUnit(int start, int v, bool* visited, vector<int>& path) {
    if(visited[v]) {
        if(v == start) {
            for(auto c : path)
                cout << c << " ";
            cout << endl;
            return;
        }
        else 
            return;
    }
    visited[v] = true;
    path.push_back(v);
    for(auto i : G[v])
        findCircleUnit(start, i, visited, path);
    visited[v] = false;
    path.pop_back();
}

http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf

我曾经在面试中遇到过这样的问题,我怀疑你遇到过这种情况,你来这里寻求帮助。把这个问题分解成三个问题就容易多了。

如何确定下一个有效点 路线 你如何确定一个点是否存在 被使用 你如何避免越过 同样的观点

问题1) 使用迭代器模式提供迭代路由结果的方法。放置获取下一个路由的逻辑的一个好地方可能是迭代器的“moveNext”。要找到有效的路由,这取决于您的数据结构。对我来说,这是一个sql表充满有效的路由可能性,所以我必须建立一个查询,以获得有效的目的地给定的源。

问题2) 当您找到每个节点时,将它们推入一个集合,这意味着您可以通过动态询问正在构建的集合,很容易地查看是否在某个点上“返回”。

问题3) 如果在任何时候你看到你正在折回,你可以从集合中弹出东西并“后退”。然后从这一点开始,再次尝试“前进”。

黑客:如果你正在使用Sql Server 2008,有一些新的“层次结构”的东西,你可以用它来快速解决这个问题,如果你把你的数据结构成树状。