Part 6 | Graphs: paths, spanning trees, and shortest paths#
- Objectives
- To read
- Exercises A
- Graph Representations and Elementary Complexities
- Bipartite Graph Detection with DFS
- Non-Disconnecting Vertex Removal
- Maze Shortest Path
- Cycle Detection in Course Prerequisites
- Kahn’s Algorithm for Topological Sorting
- Reconstructing an MST After Removing k Edges
- Forcing an Edge into an MST
- Dijkstra’s Algorithm with java.util.PriorityQueue
- Why Dijkstra Fails on Negative Edge Weights
- Shifting Negative Edge Weights in Dijkstra
- Longest Path and Bellman-Ford with Negated Weights
- Digraph Data Structure
- Depth-First Paths
- Connected Components
- Covid Bubbles
- Multi-Source Shortest Paths
- Global Warming Shortest Path
- Global Warming Islands with DFS
- Exercises B