Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Python

Discussion on Graphs

Explore the fundamentals of graph structures and their implementations using adjacency lists. Understand the breadth-first-search and depth-first-search algorithms, including their time complexities and real-world applications such as maze exploration and planarity testing.

We'll cover the following...

Additional notes

The running times of the depth-first-search and breadth-first-search algorithms are somewhat overstated by the following theorems we explained before:

  1. When given as input a Graph, g, that is implemented using the AdjacencyLists data structure, the bfs(g, r) algorithm runs in O(n+m)O(n + m) time.
  2. When given as input a Graph, g, that is implemented using the AdjacencyLists data structure, the dfs(g,r) and dfs2(g,r) algorithms each run in O(n+m)O(n + m)
...