在无向图中查找所有无弦循环

Question

如何在无向图中找到所有无弦循环？

例如,给出图表

0 --- 1
|     | \
|     |  \
4 --- 3 - 2

算法应该返回1-2-3和0-1-3-4,但绝不会返回0-1-2-3-4.

---

(注意:[1]这个问题与平面图中的小周期发现不同,因为图不一定是平面的.[2]我已经阅读了文章生成所有周期,无弦周期和哈密顿周期的原理排除,但我不明白他们在做什么:).[3]我已经尝试过CYPATH,但程序只给出了计数,readme.txt中的算法EnumChordlessPath有很大的拼写错误,而且C代码很乱.[4]我并不想找到任意一组基金会周期.循环基础可以有和弦.)

Answer 1

为从1到n的节点分配编号.

1. 选择节点编号1.将其命名为"A".

2. 枚举来自'A'的成对链接.

3. 选一个.让我们用B小于C调用相邻节点'B'和'C'.

4. 如果连接了B和C,则输出循环ABC,返回步骤3并选择另一对.

5. 如果B和C未连接:

   • 枚举连接到B的所有节点.假设它连接到D,E和F.创建向量列表CABD,CABE,CABF.对于以下每一个:
   • 如果最后一个节点连接到除C和B之外的任何内部节点,则丢弃该向量
   • 如果最后一个节点连接到C,则输出并丢弃
   • 如果它没有连接到任何一个,则创建一个新的向量列表,附加最后一个节点所连接的所有节点.

   重复,直到你用完向量.

6. 对所有对重复步骤3-5.

7. 删除节点1以及指向它的所有链接.选择下一个节点并返回步骤2.

编辑:你可以取消一个嵌套循环.

这看起来很有效,可能有bug,但你应该明白这个想法:

void chordless_cycles(int* adjacency, int dim)
{
    for(int i=0; i<dim-2; i++)
    {
        for(int j=i+1; j<dim-1; j++)
        {
            if(!adjacency[i+j*dim])
                continue;
            list<vector<int> > candidates;
            for(int k=j+1; k<dim; k++)
            {
                if(!adjacency[i+k*dim])
                    continue;
                if(adjacency[j+k*dim])
                {
                    cout << i+1 << " " << j+1 << " " << k+1 << endl;
                    continue;
                }
                vector<int> v;
                v.resize(3);
                v[0]=j;
                v[1]=i;
                v[2]=k;
                candidates.push_back(v);
            }
            while(!candidates.empty())
            {
                vector<int> v = candidates.front();
                candidates.pop_front();
                int k = v.back();
                for(int m=i+1; m<dim; m++)
                {
                    if(find(v.begin(), v.end(), m) != v.end())
                        continue;
                    if(!adjacency[m+k*dim])
                        continue;
                    bool chord = false;
                    int n;
                    for(n=1; n<v.size()-1; n++)
                        if(adjacency[m+v[n]*dim])
                            chord = true;
                    if(chord)
                        continue;
                    if(adjacency[m+j*dim])
                    {
                        for(n=0; n<v.size(); n++)
                            cout<<v[n]+1<<" ";
                        cout<<m+1<<endl;
                        continue;
                    }
                    vector<int> w = v;
                    w.push_back(m);
                    candidates.push_back(w);
                }
            }
        }
    }
}