Skip to content

Graphs

We progress through the four most important types of graph models: undirected graphs (with simple connections), digraphs graphs (where the direction of each connection is significant), edge-weighted graphs (where each connection has an software associated weight), and edge-weighted digraphs (where each connection has both a direction and a weight).

  • 4.1 Undirected Graphs introduces the graph data type, including depth-first search and breadth-first search.
  • 4.2 Directed Graphs introduces the digraph data type, including topological sort and strong components.
  • 4.3 Minimum Spanning Trees describes the minimum spanning tree problem and two classic algorithms for solving it: Prim and Kruskal.
  • 4.4 Shortest Paths introduces the shortest path problem and two classic algorithms for solving it: Dijkstra's algorithm and Bellman-Ford.