Main learning outcomes for this class
- Graph Traversal:
- I know what a depth-first search (DFS) and how to implement it
- I know some simple and almost direct applications for DFS such as finding the number of connected components, doing a flood fill or discovering cycles.
- I understand the concept of a DFS tree, edge types on a DFS search and I know more indirect applications of DFS such as computing strongly connected components or articulation points
- I know what a breadth-first search (DFS) and how to implement it
- I know how to use BFS to compute shortest distances in unweighted graphs
- I understand that graph search is a good paradigm for many situations, even where there is no explicit graph.
Study Material
Main References
- Graph Intro+Traversal
- Slides used in class: Graphs Intro, DFS & BFS
- Original Slide Source:
(in portuguese, more complete, used in DAA, a 2nd year course given by me):
- Videos (in portuguese, accompanying the slides)
- Chapters 11, 12, 16, 17 and section 19.1 of Competitive Programmer's Handbook book
- Section 4.1 and 4.2 of the Competitive Programming book
- Visualization: Graph Traversal (VisuAlgo), DFS / BFS (Data Structure Visualizations)
- GeekforGeeks: DFS, applications of DFS, BFS, applications of BFS, Tarjan Algorithm for SCC, articulation points
- Eulerian Path: Wikipedia
- CP-Algorithms (implementation): DFS, BFS, Connected Components, Articulation Points, Bridges, Strongly Connected Components, Cycles, Eulerian Path
Pedro Ribeiro - DCC/FCUP | Last update:
