Lec 28 Graph Traversals

CS61B

DepthFirstPaths Implementation

Implementing Paths With Depth First Search

Recursive Implementation

Graph Problems

General Graph Traversals

Graph Traversals

level order traversal quiz

DFS postorder quiz

Traversals and Graph Problems

Topological Sorting

从Indegree = 0的vertices出发（就是没有指向这个Node即箭头的Node),做DFS，记录DFS postorder到一个List里，最后取这个List的reverse:

topological sorting最后的结果，看起来所有的箭头都往右边指：

Topological Sort Implementation

Graph problems runtime

Breadth First Search

Definition of Level Order search

Finding the “Level-Order”

BreadthFirstPaths Implementation

runtime

Think about:

BreadthFirstPaths Demo