Friday, February 28, 2014

if graph is cyclic

For every node in graph, if a cycle exists (starting from node) then break out and return true else return false.
With only one set 'visited', it does not work. Ex: 1<-2<-3
With only one set 'path', nodes are visited multiple times for an acyclic path. Ex: 1->2->3
Two sets work. A set 'path' is used to save the path from current node. Another set 'acyclicNodes' is used to denote acyclic nodes.

Used for deadlock detection. Each process specifies order of locks required - forming a graph (directed).

    list<node> nodes

    list<node> neighbors

bool isCyclic(graph):
    set acyclicNodes = new
    foreach node in graph.nodes:
        set path = new
        if isCyclic(node, path, acyclicNodes):
            return true
    return false

bool isCyclic(node, path, acyclicNodes):
    if acyclicNodes.has(
        return false
    // node present in path so cyclic
    if path.has(
        return true
    foreach neighbor in node.neighbors:
        if isCyclic(neighbor, path, acyclicNodes):
            return true
    // node is acyclic
    return false

Time: O(nodes + edges)
Space: O(nodes)

No comments:

Post a Comment