13. Week 12: Graph Algorithms

• 13.1. Representing Graphs
  • 13.1.1. Graphs as Adjacency Lists
  • 13.1.2. Reading and Printing Graphs
  • 13.1.3. Rendering Graphs via GraphViz
  • 13.1.4. Shortcomings of Adjacency-List graph representation
• 13.2. Graphs as Linked Data Structures
  • 13.2.1. Switching between graph representations
  • 13.2.2. Testing graph operations
• 13.3. Reachability and Graph Traversals
  • 13.3.1. Checking Reachability in a Graph
  • 13.3.2. Testing Reachability
  • 13.3.3. Rendering Paths in a Graph
  • 13.3.4. Depth-First Traversal
  • 13.3.5. DFS and Reachability
  • 13.3.6. DFS and Cycle Detection
  • 13.3.7. Topological Sort
  • 13.3.8. Testing Topological Sort
• 13.4. Single-Source Shortest Paths
  • 13.4.1. Weighted Graphs
  • 13.4.2. Some Properties of Paths
  • 13.4.3. Representing Shortest Paths
  • 13.4.4. Representing Distance
  • 13.4.5. Initialisation and Relaxation
  • 13.4.6. Bellman-Ford Algorithm
  • 13.4.7. Rendering Minimal Paths
  • 13.4.8. Dijkstra’s Algorithm
  • 13.4.9. Testing Shortest-Path Algorithms
• 13.5. Minimal Spanning Trees
  • 13.5.1. Representing Undirected Graphs
  • 13.5.2. Trees in Undirected Connected Graphs
  • 13.5.3. Minimal Spanning Trees
  • 13.5.4. Kruskal’s Algorithm
  • 13.5.5. Testing MST Construction
  • 13.5.6. Other MST Algorithms
• 13.6. Exercises
  • 13.6.1. Exercise 1
  • 13.6.2. Exercise 2