如何在无向图中找到所有无弦循环？
例如，给定图表
0 --- 1
| | \
| | \
4 --- 3 - 2
算法应返回 1-2-3 和 0-1-3-4，但绝不返回 0-1-2-3-4。
（请注意，此问题与在平面图中发现小循环不同，因为图形不一定是平面的）
我已经阅读了论文根据排除原理生成所有循环、无弦循环和哈密顿循环，但我不明白他们在做什么。我也尝试过CYPATH，但程序只给出了计数，readme.txt中的算法EnumChordlessPath有明显的拼写错误，而且C代码一团糟。
我并不是想找到一组任意的基本金属周期。循环基础可以有和弦。
为节点分配从 1 到 n 的编号。
选择节点号1。将其命名为“A”。
枚举来自“A”的链接对。
选一个。我们将相邻节点称为“B”和“C”，其中 B 小于 C。
如果B和C连通，则输出循环ABC，返回步骤3并选择不同的对。
如果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);
}
}
}
}
}
@aioobe 有道理。只需找到所有循环，然后排除非无弦循环即可。这可能效率太低，但可以沿途修剪搜索空间以减少效率低下的情况。这是一个通用算法：
void printChordlessCycles( ChordlessCycle path) {
System.out.println( path.toString() );
for( Node n : path.lastNode().neighbors() ) {
if( path.canAdd( n) ) {
path.add( n);
printChordlessCycles( path);
path.remove( n);
}
}
}
Graph g = loadGraph(...);
ChordlessCycle p = new ChordlessCycle();
for( Node n : g.getNodes()) {
p.add(n);
printChordlessCycles( p);
p.remove( n);
}
class ChordlessCycle {
private CountedSet<Node> connected_nodes;
private List<Node> path;
...
public void add( Node n) {
for( Node neighbor : n.getNeighbors() ) {
connected_nodes.increment( neighbor);
}
path.add( n);
}
public void remove( Node n) {
for( Node neighbor : n.getNeighbors() ) {
connected_nodes.decrement( neighbor);
}
path.remove( n);
}
public boolean canAdd( Node n) {
return (connected_nodes.getCount( n) == 0);
}
}
只是一个想法：
假设您正在枚举示例图上的循环，并且从节点 0 开始。
如果您对每个给定的边进行广度优先搜索，例如0 - 1，在1处达到分叉。然后首先再次达到0的循环是无弦的，其余的不是并且可以被消除......至少我认为是这样。
你能使用这样的方法吗？或者有没有反例？
这个怎么样。首先，将问题简化为查找通过给定顶点 A 的所有无弦循环。找到所有这些后，您可以从图中删除 A，并用另一个点重复，直到没有剩余。
如何找到所有经过顶点A的无弦环？在给定允许的顶点列表的情况下，将其简化为查找从 B 到 A 的所有无弦路径，并按宽度优先或深度优先进行搜索。请注意，当迭代从 B （一步）可到达的顶点时，当您选择其中一个时，您必须从允许的顶点列表中删除所有其他顶点（当 B=A 时要特别小心，以免消除三个-边缘路径）。
找到所有周期。
无弦循环的定义是一组点，其中不存在这些点的子集循环。因此，一旦拥有所有循环，问题就是消除具有子集循环的循环。
为了提高效率，对于找到的每个循环，循环遍历所有现有循环并验证它不是另一个循环的子集，反之亦然，如果是，则消除较大的循环。
除此之外，唯一的困难是弄清楚如何编写一个算法来确定一个集合是否是另一个集合的子集。