Directed Acyclic Graphs

/Directed Acyclic Graphs

A directed acyclic graph(or DAG for short) is a directed graph that contains no cycles. In a DAG, a source is a vertex without incoming edges; a sink is a vertex without outgoing edges. Each DAG contains at least one source and one sink.

Important points :-

  • After removing a source or a sink from a DAG, the resulting graph is still a DAG.
  • If a vertex is the only source/sink removing it creates a new source/sink.
  • Each DAG has a topological order.
  • Back edges are the edges (u,v) where v is an ancestor of u in the tree.
  • Depth-First-Search tree (DFS Tree) is a rooted tree whose nodes are nodes of the graph. New nodes are attached to the tree, as they get visited during the DFS run.
July 7th, 2019|Categories: Data Structure|
avatar
  Subscribe  
Notify of