Introduction
A graph is one of the most powerful and general data structures in computer science. Almost every real-world network — roads between cities, friendships on Facebook, links between web pages, dependencies between tasks, the flow of money between bank accounts — is naturally a graph. Whenever data is about relationships between things rather than a simple list or hierarchy, a graph is the right model.
For Bangladeshi government job exams (BCS, Bank IT/ICT officer, and other IT-officer posts), graphs are a high-frequency, high-value topic. Examiners love to test: the basic terminology (vertex, edge, degree), the difference between adjacency matrix and adjacency list, the space and time complexity of each representation, and small "trace the traversal" problems (BFS/DFS). Master this lesson and you can answer virtually any MCQ or short-answer question on graph representation with confidence.
Learning objectives
By the end of this lesson you will be able to:
- Define a graph formally and use all core terminology (vertex, edge, directed, undirected, weighted, degree, path, cycle, connected) correctly.
- Distinguish directed vs. undirected, weighted vs. unweighted, cyclic vs. acyclic, and dense vs. sparse graphs.
- Represent any graph as an adjacency matrix, an adjacency list, and an edge list, and convert between them.
- Compute and compare the space complexity and operation time complexity of each representation.
- Decide which representation to use for a given problem (dense vs. sparse).
- Trace basic BFS and DFS traversals over a representation.
- Avoid the classic exam traps (undirected symmetry, degree counting, self-loops, the Handshaking Lemma).