12. Chapter 12: Graph Algorithms

• 12.1. Representing Graphs
  • 12.1.1. Graphs as Adjacency Lists
  • 12.1.2. Reading and Printing Graphs
  • 12.1.3. Rendering Graphs via GraphViz
  • 12.1.4. Shortcomings of Adjacency-List graph representation
• 12.2. Graphs as Linked Data Structures
  • 12.2.1. Switching between graph representations
  • 12.2.2. Testing graph operations
• 12.3. Reachability and Graph Traversals
  • 12.3.1. Checking Reachability in a Graph
  • 12.3.2. Testing Reachability
  • 12.3.3. Rendering Paths in a Graph
  • 12.3.4. Depth-First Traversal
  • 12.3.5. DFS and Reachability
  • 12.3.6. DFS and Cycle Detection
  • 12.3.7. Topological Sort
  • 12.3.8. Testing Topological Sort
• 12.4. Single-Source Shortest Paths
  • 12.4.1. Weighted Graphs
  • 12.4.2. Some Properties of Paths
  • 12.4.3. Representing Shortest Paths
  • 12.4.4. Representing Distance
  • 12.4.5. Initialisation and Relaxation
  • 12.4.6. Bellman-Ford Algorithm
  • 12.4.7. Rendering Minimal Paths
  • 12.4.8. Dijkstra’s Algorithm
  • 12.4.9. Testing Shortest-Path Algorithms
• 12.5. Minimal Spanning Trees
  • 12.5.1. Representing Undirected Graphs
  • 12.5.2. Trees in Undirected Connected Graphs
  • 12.5.3. Minimal Spanning Trees
  • 12.5.4. Kruskal’s Algorithm
  • 12.5.5. Testing MST Construction
  • 12.5.6. Other MST Algorithms
• 12.6. Exercises
  • 12.6.1. Exercise 1
  • 12.6.2. Exercise 2