CODEWITHSUNDEEP
c++graphadjacency-matrix
Eugenos_Programos
Eugenos_Programos

Reputation: 15

Print all cycles in a directed graph

I have an adjacency matrix for a graph. And I need to output all the cycles in this graph. How can I do this using dfs?

void al_dfs(int tmp_vertex,int** Graph,vector<int>& color,int number,vector<int>& result){
    color[tmp_vertex] = 1;
    for(int i = 0;i<number;i++){
        if((color[i] == 0)){ al_dfs(i,Graph,color,number,result); result.push_back(i); };
        if((color[i] == 1)){
            for(int i = 0;i< result.size();i++) cout << result[i] << " ";
        }
    }
    color[tmp_vertex] = 2;
}

I wrote a small function, but I understand that there is a lot of things that have not been completed yet.

Upvotes: 0

Views: 568

Answers (1)

Kargath
Kargath

Reputation: 528

You can reading <Algorithms FOURTH EDITION by Robert Sedgewick and Kevin Wayne> and search for the section Finding a directed cycle, which gives the full java code and diagrams.

class DirectedCycle
{
  vector<vector<int>> graph;  //index:node i,vec: The next node of this node
  vector<bool> visited;
  vector<int> edgeTo;//edgeTo[v]=w means w->v,Being used for backtracking paths
  vector<int> cycle; //store cycle path
  vector<vector<int>> cycles;
  vector<bool> onStack;//All vertices on the stack during dfs
public:
  DirectedCycle(vector<vector<int>> g, int n)
  {
    graph = g;
    visited.resize(n);
    edgeTo.resize(n);
    onStack.resize(n);
    for (int i = 0; i < n; i++) DFS(i);
  }
  void DFS(int v)
  {
    visited[v] = true;
    onStack[v] = true;//add to stack
    for (auto item : graph[v])
    {
      if (HasCycle()) return;
      if (!visited[item])
      {
        edgeTo[item] = v;
        DFS(item);
      }
      else if (onStack[item])
      {
        cycle = vector<int>();
        for (int x = v; x != item; x = edgeTo[x])
          cycle.push_back(x);
        cycle.push_back(item);
        cycles.push_back(cycle);
        cycle.clear();
      }
    }
    onStack[v] = false;//remove from the stack
  }
  bool HasCycle()
  {
    return !cycle.empty();
  }
  vector<vector<int>> CyclePath()
  {
    return cycles;
  }
};

Upvotes: 0

Related Questions