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

Discussion on Graphs

Understand the fundamentals of graphs, including adjacency list representations and traversal methods such as breadth-first search and depth-first search. Learn how these algorithms operate efficiently with complexity analysis and grasp their historical context and applications in software development.

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)
...