GATE CS - PROGRAMMING & DATA STRUCTURES:Graphs
Mastering graphs concepts and implementation.
Graphs for GATE CS (PDS)
In Programming & Data Structures, GATE focuses on representation, degrees, and BFS/DFS order. Shortest paths and MST live mainly under Algorithms — know the interface here.
Representation trade-off
| Adjacency matrix | Adjacency list | |
|---|---|---|
| Space | \(O(V^2)\) | \(O(V+E)\) |
| Edge query | \(O(1)\) | \(O(\deg)\) |
| Best when | Dense graphs | Sparse graphs |
Handshaking lemma: .
BFS vs DFS
- BFS (queue): layers by hop count; shortest path in unweighted graphs; level-order trees
- DFS (stack/recursion): discovery/finish times; cycle detection; topological order on DAGs (via finish times)
Worked: BFS order
Graph: 0—1—2, 0—3; start at 0, neighbours listed ascending.
Visit order: 0, 1, 3, 2 (1 before 3 if adjacency lists sorted).
Trap: claiming DFS gives shortest paths in unweighted graphs — that is BFS.
Directed graphs
In-degree / out-degree. A DAG has a topological order; a cycle means none. Kahn’s algorithm: repeatedly take in-degree 0 vertices.
Connectivity (undirected)
Connected components via DFS/BFS. Bridge/articulation points appear less often but use DFS tree properties when they do.
For Dijkstra / Kruskal depth, see Algorithms on the GATE hub. Next: Hashing.