Checking if a graph is a DAG

Last updated Jan 24, 2022 Edit Source

• Cs algorithms

Checking whether a graph is a Directed Acyclic Graphs is a trivial problem. First off, we need to know that for a graph to be a DAG, there must exit at least one vertice with $0$ incoming edges, otherwise, it cannot be a DAG(go figure out why yourself, you nitwit). After accepting the proposition, it is easy to find the topological ordering of the graph using the following algorithm:

1
2
3
4
5
6

pick a vertice with 0 incoming edges
if none exists:
	not a DAG
append the vertice to the topological order of the graph
remove the vertice from the graph
repeat until graph is empty