Cycles in graphs

Asked

Viewed 531 times

3

I am creating an algorithm that identifies whether a graph contains cycles excluded from the sources recursively, returning the graph for later verification of the edge quantity, so 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 that this code is time consuming. I don’t want to check it by topological numbering, applying a DFS, I wanted to run it using the DFS otherwise, without this check, it has like?

c algorithm
  • 2

    Your algorithm implementation doesn’t look efficient. Why perform multiple recursions ? You could store a list with the entry level 0 nos, go removing the ones from that list (and assigning the v) and after removing the edge check if w should enter the list of nos with entry grade 0.

1 answer

1

For the in-depth search you can use the parethetic notation, to help visualize the logic of the algorithm, when we visit a u node, we open a parentheses (u and when the recursion is returned to u, we close the parentheses u) so, suppose our graph visits the nodes u->w->v, our notation would stand (u (w (v v) 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 the cycle occurs with the vertices w->v->w->v->... our notation will be (w (v (w (v..., that is, one of the nodes of our cycle was visited again before being closed, in the BFS algorithm this translates into visiting a gray node (open, but still n 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 neighbors to the current one
  4. When recursion returns from a given node, i.e., when the DFS on a node ends and that node is closed, mark it as 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 encountered a cycle, yet, nodes that are white or black cannot be part of a cycle (were not visited before or during the cycle in the case of whites and in the 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 rebuild the cycle, eliminating the gray nodes that are not part of it.

Browser other questions tagged c algorithm

You are not signed in. Login or sign up in order to post.