Topological Sort
==============================================

**TC: O(|V|+|E|) , SC: O(|E|)**

Topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

We can use the Course Schedule question as an example. There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]. Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

.. code-block:: none

  Example 1:
  Input: 6, [[1,0],[2,1],[2,0],[3,2],[4,3],[5,3],[5,4]]
  Output: true

  Example 2:
  Input: 2, [[1,0],[0,1]]
  Output: false
  Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

.. only:: html

  - https://leetcode.com/problems/course-schedule/
  - http://www.cnblogs.com/grandyang/p/4484571.html
  - https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm
  - (CLRS p615. 22.4-3)



.. code-block:: none

  0 -----> 2 -----> 3 -----> 4          0 -----> 2 -----> 3 -----> 4
   \      ^          \     /             \      ^          ^     /   
    \    /            \   /               \    /            \   /    
     v  /              v v                 v  /              \ v     
      1                 5                   1                 5     
  topological sortable                  NOT topological sortable(cycle 3->4->5)



Post-order DFS
^^^^^^^^^^^^^^^^^^^^^^

Post-order DFS will be faster than Kan's Algo to find cycle. To find cycle, we track the color state of a node. Initially all the nodes are white color. When we enter the DFS function, we mark it as grey. When we back-track and unwind the stack, we mark it as black.

.. only:: html

  ..  youtube:: n_yl2a6n7nM
      :width: 640
      :height: 380

.. literalinclude:: code/course_schedule_dfs_test.cpp
  :linenos:
  :language: c++

To get a topological sorted path:

.. literalinclude:: code/course_schedule_getorder_test.cpp
  :linenos:
  :lines: 5-26
  :language: c++

Kahn Algo - BFS with Zero-Degree Nodes
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

|:heart:| The advantage of Kahn’ algo is **DAG checking is not needed**.

Topologically sortable == No cycle!


.. literalinclude:: code/course_schedule_bfs_test.cpp
  :linenos:
  :language: c++

To get a topological sorted path:

.. literalinclude:: code/course_schedule_getorder_test.cpp
  :linenos:
  :lines: 28-44
  :language: c++

With BFS, we can get all possible topological paths. First, we get the **Breadth First Tree** (CLRS p600) with a layered BFS. Then we use **DFS and permutation** to get all the possible paths. Please be noted the algorithm here is different from combination algo here: https://leetcode.com/problems/letter-combinations-of-a-phone-number/.

.. literalinclude:: code/course_schedule_getorder_test.cpp
  :linenos:
  :lines: 46-103
  :language: c++

.. figure:: code/topo_simple.png
  :align: center
  :name: A DAG without cycle

  There are four different paths

.. literalinclude:: code/course_schedule_getorder_test.cpp
  :linenos:
  :lines: 106-123
  :language: c++

Shortest Path Search
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

According to CLRS page 655, topological sort can be used to solve single shortest path problem in graph.

More Questions:

- http://sein.wu-99.com/ch16-graph/questions.html#create-recipes
- http://sein.wu-99.com/ch16-graph/questions.html#course-schedule
- http://sein.wu-99.com/ch16-graph/questions.html#course-schedule-ii