Search⌘ K
Home
Courses
Data Structures with Generic Types in Java

Discussion on Graphs

Explore the fundamental concepts of graph data structures, focusing on adjacency list representations. Understand depth-first-search and breadth-first-search algorithms, their running times, and practical applications in graph traversal. This lesson enhances your ability to implement and analyze graph algorithms efficiently in Java.

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