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

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.

Previous: 3.3 Trees and Heaps · Next: 3.5 Hashing

All lessons in HEC NSCT – National Skill Competency Test: Complete Preparation for Computing Graduates