Cycles in graphs

Question

Cycles in graphs

Navigation

#1 by (0 votes)

1

I am creating an algorithm that identifies if a graph contains cycles deleted the fonts recursively, returning the graph for later verification of the amount of edge, for this 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 time consuming. I do not want to check it by topological numbering, applying a DFS, wanted to run it using DFS in another way, without that check, how?

c algoritmo

asked by anonymous 22.09.2017 / 02:36

1 answer

Error adding attribute name to @WebService How to do a SELECT with CONVERT or CAST in the WHERE clause using sequelize

score 0 · Answer 1

For deep search you can use parethetic notation to help visualize the logic of the algorithm when we visit a node u, open a (u and when recursion returns to u, we close the u) so, suppose that in our graph we visit% nodes%, our notation would be u->w->v indicating the order in which each node was opened (visited for the first time) and closed (when recursion returns to it), it is easy to visualize a cycle with this notation, suppose that the cycle occurs with the vertices (u (w (v v) w) u) 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 algorithm of BFS this translates to visiting a node gray (open, but still n closed) then we have an algorithm

Mark all nodes with white color

Choose a node to start the search, mark it with gray

Make the recursive call to one of the neighboring neighbors to the current

When recursion returns from a particular node, that is, when DFS on a node ends and that node is closed, mark it as black

If you visit a gray node, you have found a loop, stop the algorithm

You can prove that if you visit a node that is gray, you have found a cycle, yet, whites that are white or black can not be part of a cycle (they 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 that only we who are gray can be part of the cycle (although not necessarily). During deep search you can also store the order in which the nodes were visited to reconstruct the cycle, eliminating the gray nodes that are not part of it.