Cycles on graphs

Question:

I'm creating an algorithm that identifies if a graph contains cycles excluded sources recursively, returning the graph for later verification of the edge quantity, for that, create the following code for adjacency matrices:

Graph GRAPHisCycle( Graph F, vertex v) {
    while( v < F->V) {
        vertex w = 0;       
        while (w < F->V) {
            if( F->adj[v][w] == 1 && GRAPHoutdeg( F, v) > 0 && GRAPHindeg( F, v) == 0) {        
                GRAPHremoveA( F, v, w);
                GRAPHisCycle( F, v); 
             }
        ++w;
        }
    ++v;
    }
    return F;
}

GRAPHoutdeg and GRAPHindeg represent the degree of output and input. I found this code to be very time consuming. I don't want to check it by topological numbering, applying a DFS, I wanted to run it using DFS in another way, without this check, how?

Answer:

For depth search you can use parethetic notation, to help visualize the logic of the algorithm, when we visit a node u, we open a parenthesis (u and when recursion returns to u, we close the parenthesis u) so, suppose our graph visit nodes u->w->v , our notation would be (u (w (vv) w) u) indicating the order in which each node was opened (first visited) and closed (when recursion returns to it ), it is easy to visualize a cycle with this notation, suppose that the cycle occurs with vertices w->v->w->v->... our notation will be (w (v (w (v... , or) that is, one of the nodes in our loop was visited again before it was closed, in the BFS algorithm this translates to visiting a gray node (open, but not yet closed) so we have an algorithm

  1. Mark all nodes with white color
  2. Choose a node to start the search, mark it with gray
  3. Make the recursive call to one of the nodes neighboring the current one
  4. When recursion returns from a given node, that is, when DFS on a node ends and that node is closed, mark it black
  5. If you visit a gray node, you found a cycle, stop the algorithm

It is possible to prove that, if you visit a node that is gray, you have found a cycle, yet nodes that are white or black cannot be part of a cycle (they were not visited before or during the cycle in the case of whites and in this case of blacks, the search ended without finding a cycle), so only nodes that are gray can be part of the cycle (although not necessarily will). During the deep search you can also store the order in which the nodes were visited to reconstruct the cycle, eliminating gray nodes that are not part of it.

Scroll to Top