Quick Revision Notes: Graph Data Structure & Graph Theory (DSSSB TGT/PGT CS)
- Representations: Adjacency Matrix uses
O(V²) space (dense graphs); Adjacency List uses O(V + E) space (sparse graphs); Incidence Matrix has size V × E.
- Graph Traversals: BFS uses a Queue (level-order, shortest path in unweighted graphs); DFS uses a Stack (cycle detection, topological sort, articulation points). Time complexity is
O(V + E) using adjacency lists.
- Minimum Spanning Tree (MST): Always has
V - 1 edges. Prim's (O(E log V) with binary heap) grows from a vertex; Kruskal's (O(E log E) with Union-Find) sorts edges greedily.
- Shortest Paths: Dijkstra's (
O((V+E) log V), non-negative weights only); Bellman-Ford (O(VE), detects negative cycles); Floyd-Warshall (O(V³), DP all-pairs shortest path).
- Discrete Graph Formulas: Handshaking Lemma:
Σ deg(v) = 2|E|; Simple undirected max edges: n(n-1)/2; Euler planar formula: V - E + F = 2; Cayley's labeled trees: n^(n-2); Complete graph chromatic number: n.
Set 1 (Q1 – Q20)
Total Score: 0 / 0 Attempted (160 Total)