Graphs
Schema della sezione
-
Motivations. Definition of (un)directed graph. How to represent a graph. Graph traversal: Breadth-First Search and Depth-First Search. Intuition, examples, pseudo-code, complexity, and properties. Topological Sort: motivations, intuition, pseudo-code, complexity, and sketch of correctness. Transitivity Closure: naive algorithm and complexity, intuition, and complexity.