A graph is a non-linear data structure consisting of vertices (nodes) connected by edges (arcs). Unlike trees, graphs may have cycles and multiple paths between nodes, with no single root.
Graphs model relationships in many real-world domains: road networks, social networks, the internet, dependency chains, and more.
| Term | Definition |
|---|---|
| Vertex (node) | A fundamental unit/entity in the graph |
| Edge (arc) | A connection between two vertices |
| Weighted edge | An edge with a numeric value (e.g. distance, cost) |
| Degree | Number of edges connected to a vertex |
| Path | A sequence of vertices connected by edges |
| Cycle | A path that starts and ends at the same vertex |
| Connected graph | There is a path between every pair of vertices |
| Feature | Undirected | Directed (Digraph) |
|---|---|---|
| Edges | Bidirectional — travel in either direction | One-way — indicated by arrows |
| Example | Facebook friendships (mutual) | Twitter follows (one-way) |
| Adjacency matrix | Symmetric (a[i][j] = a[j][i]) | Not necessarily symmetric |
| In-degree / Out-degree | Only degree | In-degree: edges arriving; out-degree: edges leaving |
In a weighted graph, each edge carries a numeric weight (cost, distance, time). In an unweighted graph, edges simply indicate connection with no associated value. Algorithms such as Dijkstra's shortest path require weighted graphs.
A 2D array where matrix[i][j] = weight if there is an edge from vertex i to vertex j, or 0 (or ∞) otherwise. For unweighted graphs, use 1 and 0.
Pros: O(1) edge lookup; simple; works for dense graphs.
Cons: O(V²) space — wasteful for sparse graphs where most cells are 0.
Each vertex stores a list of its neighbours (and weights). More space-efficient for sparse graphs.
Pros: O(V + E) space — much better for sparse graphs; easy to iterate over neighbours.
Cons: O(V) edge lookup in worst case; more complex to implement.
| Criterion | Use Adjacency Matrix | Use Adjacency List |
|---|---|---|
| Graph density | Dense (many edges, E ≈ V²) | Sparse (few edges, E << V²) |
| Edge lookup speed | O(1) | O(V) worst case |
| Space | O(V²) | O(V + E) |
| Iterate neighbours | O(V) per vertex | O(degree) per vertex |
Graph traversal visits every vertex exactly once. Two main approaches:
| Type | Description | Example |
|---|---|---|
| Tree | Connected, acyclic graph | File system directory |
| DAG (Directed Acyclic Graph) | Directed, no cycles | Task dependency/build system |
| Complete graph | Every vertex connected to every other | Round-robin tournament |
| Bipartite graph | Vertices split into 2 groups; edges only between groups | Job-applicant matching |
8 questions · 20 marks · instantly marked
| Term | Definition |
|---|