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.