13. YSC2229 Lecture Notes, Week 13

• 13.1. Reachability and Graph Traversals
  • 13.1.1. Checking Reachability in a Graph
  • 13.1.2. Testing Reachability
  • 13.1.3. Rendering Paths in a Graph
  • 13.1.4. Depth-First Traversal
  • 13.1.5. DFS and Reachability
  • 13.1.6. DFS and Cycle Detection
  • 13.1.7. Topological Sort
  • 13.1.8. Testing Topological Sort
• 13.2. Single-Source Shortest Paths
  • 13.2.1. Weighted Graphs
  • 13.2.2. Some Properties of Paths
  • 13.2.3. Representing Shortest Paths
  • 13.2.4. Representing Distance
  • 13.2.5. Initialisation and Relaxation
  • 13.2.6. Bellman-Ford Algorithm
  • 13.2.7. Rendering Minimal Paths
  • 13.2.8. Dijkstra’s Algorithm
  • 13.2.9. Testing Shortest-Path Algorithms
• 13.3. Minimal Spanning Trees
  • 13.3.1. Representing Undirected Graphs
  • 13.3.2. Trees in Undirected Connected Graphs
  • 13.3.3. Minimal Spanning Trees
  • 13.3.4. Kruskal’s Algorithm
  • 13.3.5. Testing MST Construction
  • 13.3.6. Other MST Algorithms
• 13.4. Exercises
  • 13.4.1. Mandatory exercises
  • 13.4.2. Recommended exercises
  • 13.4.3. Exercise 1
  • 13.4.4. Exercise 2
  • 13.4.5. Exercise 3
  • 13.4.6. Exercise 4
  • 13.4.7. Exercise 5

Supplementary materials

• Reachability in Directed Graphs
• Single-Source Shortest Paths
• Minimal Spanning Trees
• Automated Tests