Topological Sort

两种做法：

1. DFS, output the reverse of finishing time of vertices
2. BFS,
   1. calculate in-degree of each node in a HashMap,
   2. output nodes of in-degree 0
   3. for those that are outputted already,
      1. decrement their neighbors' in-degrees (because outputted means finished, and no dependency for later neighbors anymore)
      2. output, new in-degree == 0 nodes

DFS

试用 题目类型：

寻找所有方案

BFS

适用题目类型：

求最短距离 (code below)，Graph Traversal

pseudo algorithm for finding nth level or n-distance vertices:

also good for shortest path problems

def BFS(s, Adj):
    level = {s: 0}
    parent = {s: None}
    i = 1
    frontier = [s]
    while frontier:
        next = []
        for u in frontier:
            for v in Adj[u]:
                if v not in level:
                    level[v] = i
                    parent[v] = u
                    next.append(v)
        frontier = next
        i += 1

Shortest Path: O(V + E)

• v <-- parent[v]

  <-- parent\[parent\[v\]\]
  
        <-- .....
  
        <--  s
  

is a shortest path solution from s to v of length level[v]