Count number of cycles in directed graph using DFS

Question

I want to count total number of directed cycles available in a directed graph (Only count is required).

You can assume graph is given as adjacency matrix.

I know DFS but could not make a working algorithm for this problem.

Please provide some pseudo code using DFS.

Unesco

Doesn't DFS only work for acyclic graphs...? Otherwise, you'll just keep diving and diving forever. – Heraldry

@Heraldry DFS is defined for general directed graphs, too. You keep track of nodes you've visited and don't visit the same node twice. – Tubing

You should really specify what you mean by "number of cycles". If you mean all cycles that don't repeat a vertex, then Johnson's algorithm is the way. youtube.com/watch?v=johyrWospv0 Note that the number of these can be very, very large, so any answers that rely on num_cycles++ can be very very slow. – Tubing

Answer 1

This algorithm based on DFS seems to work, but I don't have a proof.

This algorithm is modified from the dfs for topological sorting (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;
  }
};

Impolicy

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

Boggart

This doesn't work. Not even close. – Gawk

Thank you for contributing to the Stack Overflow community. This may be a correct answer, but it’d be really useful to provide additional explanation of your code so developers can understand your reasoning. This is especially useful for new developers who aren’t as familiar with the syntax or struggling to understand the concepts. Would you kindly edit your answer to include additional details for the benefit of the community? – Cirrate

Answer 3

Let us consider that , we are coloring the nodes with three types of color . If the node is yet to be discovered then its color is white . If the node is discovered but any of its descendants is/are yet to be discovered then its color is grey. Otherwise its color is black . Now, while doing DFS if we face a situation when, there is an edge between two grey nodes then the graph has cycle. The total number of cycles will be total number of times we face the situation mentioned above i.e. we find an edge between two grey nodes .

Embus

In a depth first search each directed edge is considered only once, so this algorithm gives a number of cycles less than the number of edges. Unfortunately, there can be many more cycles than edges. Consider the complete graph on n vertices. Every subset of two or more vertices describes at least one cycle [(n-1)! of them in fact], but has only n*(n-1) edges, so the number of cycles grows faster than 2^n but the number of edges does not. So the above algorithm can not work. – Kristlekristo

the above also doesn't work if we have connected cycles, i.e. a common edge between 2 cycles – Sphygmograph