1. BFS/DFS Foundations

Competitive ProgrammingWeek 05

This lecture is divided into two segments. In the first part, we introduce the notion of graphs and describe two popular ways in which you can represent a graph - the adjacency matrix and adjacency list representations, with a brief discussion of the pros and cons of both options.

In the second part, we explain the BFS and DFS traversals, focusing mostly on the implementations. To try out the traversals yourself, you can try out this module on Visualgo.

Learn more about graph representations and traversals in this book chapter.

Further, you can find the code discussed in the video on the Competitive Programming book repository:

  1. Graph representations: C++PythonJava
  2. BFS: C++PythonJava
  3. DFS: C++PythonJava

You can find out more about applications of BFS and DFS in the following video:

and you can learn about topological sort here: