Graph Traversals Study Guide

CS61B

Overview

C LEVEL

3.Problem 2a from Princeton's Fall 2009 final

错了 这个得自己enqueue dequeue一下才知道：

5.Problem 1a and 1b from Princeton's Spring 2008 final.

6.Problem 3a from Princeton's Fall 2010 final.

错，更正：

还是错，再看一遍：

终于对了，说明一点不熟。

B level

1.Problem 2b from Princeton's Fall 2009 final.

这道题对英文的理解有问题，所以我建议继续做GRE阅读题呢。
更正：

2.Problem 1c from Princeton's Spring 2008 final.

3.Problem 3b from Princeton's Fall 2010 final.

要理解这里的 simultaneously on function call stack at some point during DFS 是什么意思，我的理解是能够构成一条return DFS的路，那么这条路上的所有vertices就是同时在stack上。
比如A-B-G,A-C-D-F-E.

讨论:
DFS Graph

LEVEL A
1.Adapted from Algorithms textbook 4.2.10: Given a DAG, does there exist a topological order that cannot result from applying a DFS-based algorithm, no matter in what order the vertices adjacent to each vertex are chosen? Prove your answer.

https://www.youtube.com/watch?v=Q9PIxaNGnig
Topological Sorting

题目搜了一下，答案都是刷题的人总结的，所以现在不做了，刷题时做。