## 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: DFS, BFS, Connected Components, Articulation Points, Bridges, Strongly Connected Components, Cycles, Eulerian Path

Pedro Ribeiro - DCC/FCUP |
**Último update:**