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

5 回答

• 1

  为从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 .

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

  这看起来很有效，可能有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);
                  }
              }
          }
      }
  }
  

  回复于 2024-04-29T07:45:02+08:00
• 8

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

  回复于 2024-04-29T07:45:02+08:00
• 1

  这个怎么样 . 首先，将问题减少到找到通过给定顶点A的所有无弦循环 . 一旦找到了所有这些，你就可以从图中删除A，然后用另一个点重复，直到没有任何东西为止 .

  如何找到通过顶点A的所有无弦循环？给定一个允许的顶点列表，将其减少到找到从B到A的所有无弦路径，并搜索广度优先或深度优先 . 请注意，当迭代从B可到达的顶点（在一个步骤中）时，当您选择其中一个顶点时，您必须从允许顶点列表中删除所有其他顶点（当B = A时要特别小心，以免消除三个 - 路径） .

  回复于 2024-04-29T07:45:02+08:00
• 1

  只是一个想法：

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

  如果您对每个给定边进行广度优先搜索，例如0 - 1，你在1处达到一个分叉 . 那么首先达到0的循环是无弦的，其余的不是并且可以被消除......至少我认为是这种情况 .

  你能用这样的方法吗？或者有一个反例吗？

  回复于 2024-04-29T07:45:02+08:00
• 4

  找到所有周期 .

  无弦循环的定义是一组点，其中这些点的子集循环不存在 . 因此，一旦你有所有循环问题就是简单地消除具有子集循环的循环 .

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

  除此之外，只有困难在于弄清楚如何编写一个算法来确定一个集合是否是另一个集合的子集 .

  回复于 2024-04-29T07:45:02+08:00