代码之家 › 专栏 › 技术社区 › kennytm

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

graph-theory graph language-agnostic algorithm

kennytm · 技术社区 · 14 年前

例如,给定图

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

算法应该返回1-2-3和0-1-3-4,但决不能返回0-1-2-3-4。

[一] 这个问题和 small cycle finding in a planar graph 因为图形不一定是平面的。 [二] 我看过报纸了 Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion [三] CYPATH 但是程序只给出了计数,readme.txt中的算法EnumChordlessPath有明显的错别字,C代码也一团糟。 [四] 我不是想随便找一套 fundametal cycles

5 回复 | 直到 7 年前

Eugene Smith 14 年前

为节点分配从1到n的数字。

枚举“A”中的链接对。
选一个。让我们调用B小于C的相邻节点'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);
                }
            }
        }
    }
}

Jon Snyder 14 年前

@一切都有道理。找到所有的周期,然后排除那些没有和弦的。这可能效率太低,但搜索空间可以一路剪枝,以降低效率。下面是一个通用算法:

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);
   }
}

Beta 14 年前

如何找到所有通过顶点A的无弦循环?将其简化为在给定允许顶点列表的情况下,查找从B到A的所有无弦路径,并先搜索广度或深度。请注意,在从B迭代可到达的顶点(一步)时,当您选择其中一个顶点时,必须从允许的顶点列表中删除所有其他顶点(当B=A时要特别小心,以免消除三条边路径)。

Jason S 14 年前

只是一个想法:

假设您正在示例图上枚举循环,并且从节点0开始。

你能用这样的方法吗?还是有反例?

Neil 14 年前

找到所有周期。

为了提高效率,对于找到的每个循环,循环遍历所有现有循环,并验证它不是另一个循环的子集,反之亦然,如果是,则消除较大的循环。

除此之外,唯一的困难是如何编写一个算法来确定一个集合是否是另一个集合的子集。