如何在无向图中找到所有chordless cycles?
例如,给定图
0 --- 1
| | \
| | \
4 --- 3 - 2
算法应该返回 1-2-3 和 0-1-3-4,但绝不会返回 0-1-2-3-4。
(注:[1]这道题和small cycle finding in a planar graph不一样,因为图不一定是平面的。[2]我看过Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion的论文,但是我不明白他们在做什么 :)。 [3] 我试过CYPATH但是程序只给出了计数,readme.txt中的算法EnumChordlessPath有明显的错别字,C代码也很乱。 [4] 我并不是想找到一组任意的 fundametal cycles 。循环基础可以有和弦。)
最佳答案
从 1 到 n 给节点分配编号。
选择节点号 1。称其为“A”。
枚举来自“A”的链接对。
选一个。让我们将 B 小于 C 的相邻节点称为“B”和“C”。
如果B和C相连,则输出循环ABC,返回步骤3,选择不同的一对。
如果 B 和 C 没有连接:
- 枚举连接到 B 的所有节点。假设它连接到 D、E 和 F。创建向量 CABD、CABE、CABF 的列表。对于其中的每一个:
- 如果最后一个节点连接到除C和B之外的任何内部节点,则丢弃向量
- 如果最后一个节点连接到C,输出并丢弃
- 如果它没有连接到任何一个,创建一个新的向量列表,附加最后一个节点连接到的所有节点。
重复直到用完向量。
对所有对重复步骤 3-5。
删除节点 1 和所有指向它的链接。选择下一个节点并返回到步骤 2。
编辑:您可以取消一个嵌套循环。
乍一看似乎可行,可能存在错误,但您应该明白:
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);
}
}
}
}
}
关于algorithm - 在无向图中查找所有无弦循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4022662/