If you are unsure of any of the material, watch https://www.youtube.com/watch?v=AfSk24UTFS8

Topological Sort:

In summary, it's just running DFS, and output the reverse of the finishing time of vertices.

Usually the technique is DFS + extra stack.

Time Complexity is O(V + E) where V is number of vertices, E is number of edges

DFS:

The core of DFS and related problems is that,

have dictionary to track visited vertices, and only record into dictionary after coming out from the dfs_visit function

Include other constraints as necessary: eg. ancestors stack, value constraints

parameters to pass:

adjacency list (vertex: [vertices], usually a hashmap)
processing letter
visited set,
ancestors stack,
return result

overview of dfs

def dfs(V, adj):
    parent = {}
    for s in V:
        if s not in parent:
            parent[s] = None
            dfs_visit(adj, s)

DFS - Visit:

parent = {s: None}

# adj is a set 
def dfs_visit(adj, s):
    for v in adj[s]:
        if v not in parent:
            parent[v] = s
            dfs_visit(adj, s)

Edge classification:

Tree edge: bolded edges that visit new node via edges
non-tree edge:
- forward edge: goes to descendent in the tree/forest
- backward edge: goes to ancestor from a node
- cross edge: neither forward or backward

In Undirected, only tree edge and backward edge can exist

Edge classification is key for cycle detection:

in Directed graph G:

G has a cycle <=> G has a backward edge

To summarize, a backward edge is an edge that visits its ancestor where ancestor is a node that comprises of the tree edges that come to backward edge's starting node.

THUS, proving there is no backward edge proves graph to be DAG, directed acyclic graph

Similarly, Topological Sort only applies to DAG, or Topological sort cannot work when there exists backward edge. AKA, topological sort cannot work when there is a cycle