CODEWITHSUNDEEP
algorithmgraphgraph-theorydirected-acyclic-graphs
Emma
Emma

Reputation: 314

Check if new edge will make DAG cyclic

Given some directed graph there are a lot of algorithms for checking weather or not it contains cycles. i.e. algorithms with signatures like this:

function isCyclic(g: DirectedGraph): bool

But I have a problem which is a little different: Given a directed graph that I already know is acyclic I want to check if adding a given edge will create a cycle. i.e. something like this:

function willCreateCycle(g: AcyclicDirectedGraph, newEdge: Edge): bool

My solution this far:

In the graph we have some nodes, two of which are F (from) and T (to) We want to check if adding a new edge E = F->T will create a cycle

=>

Traverse the graph starting from node T. If we at any point end up at node F we have a cycle.

Do you think this is correct?

Upvotes: 1

Views: 871

Answers (1)

Henry
Henry

Reputation: 43728

Yes this is correct. Adding an edge F->T will result in a cycle if and only if there exists already a path from T to F.

Upvotes: 1

Related Questions