topological-sort

Topological Sort

Takes a Directed Acyclic Graph* and returns an array of the nodes where each node appears before all the nodes it points to.

• Directed Acyclic Graph →* directed graph with no cycles

  

  Untitled

Untitled

Have all nodes in straight line pointing right

• Topological sort is not unique ( can have more one topological ordering )

---

Kahn’s Algorithm

Used to perform a topological sort on a directed acyclic graph

---

Indegree vs Outdegree

Untitled

• vertex 4 has 3 incoming edges and 3 outgoing edges , so indegree is 3 and outdegree is 3.

• vertex 7 has 2 indegree and 1 outdegree :)

---

What is topological sort?