algorithm - 使用 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;
  }
};