CODEWITHSUNDEEP
algorithmgraphlanguage-agnosticgraph-algorithm
fast_cen
fast_cen

Reputation: 1377

How can I convert an undirected graph to directed graph with no cycle (Directed acyclic graph)

I have an undirected graph and I wish to transform it to a directed graph. I will have few constraint, such as already having some directed relations.

Upvotes: 0

Views: 1535

Answers (1)

amit
amit

Reputation: 178471

You are actually trying to build a DAG from your infrastructure graph. Note that a directed graph is a DAG if and only if it can be topologically sorted.

So, let's go from the end to the beginning. First create the topological sort, and then connect nodes in a way that obey the sort.

  • First, remove all "undetermined" edges, and keep only those you already have directions for.
  • Then, do topological sort on the graph and find some topological sort (If there is none, the problem cannot be solved with the given restrictions).
  • Based on it, from first to last set the direction of each edge such that the source node is the one with the lower topological sort.

Time complexity of the algorithm is linear in the number of nodes and edges.

Upvotes: 2

Related Questions