Introduction
A graph is the most powerful data structure in computer science for modelling relationships: cities joined by roads, computers linked by cables, web pages connected by hyperlinks, or people in a social network. Almost every real-world "network" problem — routing, scheduling, connectivity, cheapest wiring — reduces to a graph problem.
For BCS, Bank IT, and IT-officer written and viva exams, graph algorithms are among the highest-yield topics in Algorithms. Examiners love them because a single small diagram can test data structures, complexity analysis, and step-by-step tracing at once. This lesson teaches four pillars you must master:
- BFS (Breadth-First Search) — explore level by level.
- DFS (Depth-First Search) — explore as deep as possible first.
- Shortest Path — Dijkstra and Bellman-Ford (and BFS for unweighted graphs).
- MST (Minimum Spanning Tree) — Prim's and Kruskal's algorithms.
Study this fully and you will be able to trace any traversal, compute any shortest path or MST by hand, and answer every complexity and "which algorithm" MCQ.
Learning objectives
By the end of this lesson you will be able to:
- Define a graph and all its core terms (vertex, edge, degree, weighted, directed, cyclic).
- Represent a graph with an adjacency matrix and an adjacency list, and compare their costs.
- Trace BFS and DFS step by step and state their time and space complexity.
- Compute shortest paths using BFS (unweighted), Dijkstra (non-negative weights), and Bellman-Ford (handles negative edges, detects negative cycles).
- Build a Minimum Spanning Tree using Prim's and Kruskal's algorithms.
- Choose the correct algorithm for a given exam scenario and avoid the classic traps.