Graphs/Cycles

Notes

Detecting Cycles

Cycles can exist and be detected on either directed or undirected graphs.

For both types of graphs, a cycle exists if and only if there is a back edge on the graph. To detect a cycle, then, requires a depth-first search (see Graphs/DFS) and marking any back edges. If there are any back edges, the cycle exists.

Algorithm

To algorithmically find a back edge, we should consider undirected and directed graphs separately.

Detecting Cycles on Undirected Graphs

This is the easier case - each edge can be classified as either an edge that is part of the DFS tree, or a back edge. (There are no cross-edges in an undirected graph.)

To classify each edge, when visiting a vertex u, iterate through each edge that is incident to the vertex. If the opposite vertex has already been visited, the edge is a back edge. Otherwise, the edge is a DFS tree edge.

// "visited" is a list of visited vertices
def is_node_in_cycle(s, visited):
    if s not in visited:
        mark current node as visited
        // recur for all vertices:
        for each neighbor v of s:
            if v in visited:
                return true
    return false


def is_graph_cyclic(g):
    initialize visited as empty list
    initialize path_stack as empty
    for each vertex v in g:
        if is_node_in_cycle(v, visited, path_stack):
            return true
    return false

Detecting Cycles on Directed Graphs

For directed graphs, when visiting a vertex u, iterate through each outgoing edge that is incident to the vertex. If the opposite vertex has already been visited, we must determine if it is an ancestor of the current vertex (making it a back edge, and forming a cycle), or whether it is a cross edge (which connects to a vertex that is neither an ancestor nor a descendant, and not forming a cycle).

To do this, additional bookkeeping is needed for the DFS. The DFS must keep track of the vertices that are actively a part of the current recursive DFS call.

// "visited" is a list of visited vertices
// alternatively: can be a map from vertices to booleans (has this vertex been visited)
// "path_stack" is a stack of vertices that are part of this recursive stack
def is_node_in_cycle(s, visited, path_stack):
    if s in visited:
        mark current node as visited
        add s to path_stack
        // recur for all vertices:
        for each neighbor v of s:
            if v not in visited and is_node_in_cycle(v, visited, path_stack):
                return true
            else if v in current_stack:
                return true
    current_stack[v] = false
    return false

def is_graph_cyclic(g):
    initialize visited as empty list
    initialize path_stack as empty
    for each vertex v in g:
        if is_node_in_cycle(v, visited, path_stack):
            return true
    return false