使用DFS计算有向图中的循环数

Question

我想计算有向图中可用的有向循环总数（只需要计数）。

您可以假设图以邻接矩阵的形式给出。

我知道

DFS

，但无法为这个问题制定一个可行的算法。

请使用

DFS

提供一些伪代码。

Answer 1

这个基于DFS的算法似乎可行，但我没有证明。

该算法是由拓扑排序的dfs修改而来 （https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search）。

class Solution {
  vector<Edge> edges;
  // graph[vertex_id] -> vector of index of outgoing edges from @vertex_id.
  vector<vector<int>> graph;
  vector<bool> mark;
  vector<bool> pmark;
  int cycles;

  void dfs(int node) {
    if (pmark[node]) {
      return;
    }
    if (mark[node]) {
      cycles++;
      return;
    }
    mark[node] = true;

    // Try all outgoing edges.
    for (int edge_index : graph[node]) {
      dfs(edges[edge_index].to);
    }

    pmark[node] = true;
    mark[node] = false;
  }

  int CountCycles() {
    // Build graph.
    // ...

    cycles = 0;
    mark = vector<bool>(graph.size(), false);
    pmark = vector<bool>(graph.size(), false);
    for (int i = 0; i < (int) graph.size(); i++) {
      dfs(i);
    }

    return cycles;
  }
};

Answer 2

void Graph::DFS(int u,vector<int> &color){
    color[u] = 1;
    for(auto v:li[u]){
      if(color[v]==1)
        NoOfCycles++;
      if(color[v]==0)
        DFS(v,color);
    }
   color[u]=2;
}

Answer 3

让我们考虑一下，我们用三种颜色为节点着色。如果节点尚未被发现，则其颜色为白色。如果该节点已被发现，但其任何后代尚未被发现，则其颜色为灰色。否则其颜色为黑色。现在，在进行 DFS 时，如果我们遇到这样的情况，两个灰色节点之间有一条边，那么图就有环。循环总数将是我们面临上述情况的总次数，即我们找到两个灰色节点之间的边缘。