GATE CS - ALGORITHMS:Graph Algorithms for GATE CS
Mastering graph algorithms for gate cs concepts and implementation.
Graph Algorithms for GATE CS
Expect BFS/DFS properties, Dijkstra vs Bellman-Ford, and MST (Kruskal/Prim) behaviour. Complexity in terms of (V,E).
BFS / DFS
| BFS | DFS | |
|---|---|---|
| Structure | Queue | Stack / recursion |
| Unweighted shortest path | Yes | No |
| Edge types (directed) | Cross etc. | Tree/back/forward/cross via timestamps |
DFS discovery/finish times → topological sort on DAGs (decreasing finish).
Shortest paths
| Algo | Weights | Notes |
|---|---|---|
| BFS | Uniform (0/1 hops) | Hop count |
| Dijkstra | Non-negative | Binary heap (O((V+E)log V)) typical |
| Bellman-Ford | Negative OK | (O(VE)); detects neg cycles |
| Floyd-Warshall | All pairs | (O(V^3)) |
Trap: Dijkstra with a negative edge "because it usually works."
MST
Kruskal (sort edges + Union-Find) or Prim (grow tree). Cut property: lightest edge across a cut is safe. Adding a constant to every edge weight preserves MSTs; it need not preserve shortest paths.
Topo / connectivity drills also appear under PDS Graphs. Hub: GATE.
Progress