Courses / HEC NSCT – National Skill Competency Test: Complete Preparation for Computing Graduates
3.4 Graphs
Area 3 – Data Structures & Algorithms (10%) · 45 min read · 9 MCQs to check yourself
A graph G = (V, E) has vertices and edges; edges may be directed/undirected and weighted.
| Representation | Space | Check edge (u, v) | Best for |
|---|---|---|---|
| Adjacency matrix | O(V²) | O(1) | Dense graphs |
| Adjacency list | O(V + E) | O(degree) | Sparse graphs (most real graphs) |
Traversal
- BFS (queue) – visits level by level; finds shortest path in unweighted graphs.
- DFS (stack/recursion) – goes deep first; used for cycle detection, topological sort, connected components. Both run in O(V + E).
Key algorithms
| Problem | Algorithm | Notes |
|---|---|---|
| Shortest path, non-negative weights | Dijkstra | Greedy with priority queue; O((V + E) log V) |
| Shortest path with negative edges | Bellman-Ford | Detects negative cycles; O(VE) |
| All-pairs shortest paths | Floyd-Warshall | Dynamic programming; O(V³) |
| Minimum spanning tree | Kruskal (sort edges + union-find) / Prim (grow from a vertex) | MST of V vertices has V − 1 edges |
| Order tasks with dependencies | Topological sort | Only for DAGs (directed acyclic graphs) |
Sum of degrees in an undirected graph = 2 × number of edges. A complete graph with n vertices has n(n − 1)/2 edges.
Graph traversals – BFS and DFS (Abdul Bari)
This lesson ends with a quiz of 9 MCQs. Open the lesson on PrepOasis to take it and save your progress.