York University - CSE 3101 - Summer 2006
Phuong Nguyen

Summary of Lecture 10:

1. Test 2 solution.

2. More on Breadth-first search [22.2]
Breadth-first tree.
Application: Computing the distances to s. Bipartiteness checking.
Also: 2-colorability problem.

3. Depth-first search [22.3]
Depth-first forest.
Application: Topological sorting [22.4] (Will continue next week.)

For next class: Topological sorting [22.4]. Network flow [Sections 26.1-3].