Introduction · Representation · Traversal · Minimum Spanning Trees · Shortest Path Algorithms
Many real-world problems cannot be represented using arrays, linked lists, or trees alone. Graphs model arbitrary relationships between entities.
What is a Graph?
A graph is a non-linear data structure consisting of a set of vertices (nodes) and a set of edges connecting pairs of vertices.
V = Set of Vertices · E = Set of Edges
Example
V = {A, B, C, D, E}
E = {(A,B), (A,C), (B,D), (C,D), (D,E)}
Important Properties
Create vertices. Start with isolated nodes — no connections yet.
Connect vertices using edges to form relationships.
Assign weights (optional) — e.g., distance, cost, or capacity.
Assign directions (optional) — edges may be one-way or two-way.
Basic Components of a Graph
A point representing an object or entity in the graph.
A connection or relationship between two vertices.
Two vertices connected directly by a single edge.
An edge connected to a particular vertex.
Degree of a Vertex
Degree of a vertex is the number of edges connected to it.
In-degree of a vertex in a directed graph: number of edges coming into the vertex.
Out-degree of a vertex in a directed graph: number of edges going out of the vertex.
Directed Graph vs Undirected Graph — the fundamental distinction
Edges have no direction. The relationship is bidirectional — if A connects to B, then B connects to A.
Every edge has a direction, represented using arrows. A → B does not imply B → A.
| Feature | Undirected | Directed |
|---|---|---|
| Direction | No direction — edges are symmetric | Directional — edges have arrows |
| Traversal | Bidirectional: A↔B both ways | One-way: A→B only (unless B→A exists) |
| Applications | Social networks, road maps, electrical grids | Web links, task scheduling, compilers |
| Representation | Symmetric adjacency matrix | Asymmetric adjacency matrix |
| Example | Facebook friendship (mutual) | Twitter follow (one-way) |
Adding numerical values to edges — cost, distance, or capacity
Edges contain numerical values. Weights may represent:
Examples: Google Maps, Flight Routes, Computer Networks
Every edge is treated equally. Only the structure (who connects to whom) matters — no cost or distance associated.
Examples: Friendship Graph, Website Links, Hierarchy
| Aspect | Weighted | Unweighted |
|---|---|---|
| Storage | Adjacency matrix stores weight values | Adjacency matrix stores 0/1 only |
| Search | Dijkstra's / Bellman-Ford (weight-based) | BFS — each edge has equal cost |
| Shortest Path | Minimum total weight along path | Fewest number of edges (hops) |
| Applications | GPS navigation, network routing, logistics | Social networks, web crawling, hierarchies |
Does a closed loop exist?
A path that starts and ends at the same vertex.
Example: A → B → C → A
A graph that contains at least one cycle.
May also contain non-cycle parts.
A graph with no cycles at all.
DAGs are directed acyclic graphs — common in task scheduling.
Every tree is acyclic, but not every acyclic graph is a tree (could be a forest).
| Cyclic Graph | Acyclic Graph | |
|---|---|---|
| Definition | Contains at least one cycle | No cycles exist |
| Key Property | Path loops back to start | All paths are finite |
| Example | Friendship circle (mutual friends) | Project task dependencies (DAG) |
Can you reach every vertex?
A graph where every pair of vertices has a path between them.
Removing any single edge does NOT necessarily disconnect it.
Analogy: A road network where every town is reachable from every other town.
A graph where at least one pair of vertices has no path between them.
Contains two or more connected components.
Analogy: An airline network where not all cities have direct or indirect flights to each other.
A maximal connected subgraph — the largest group of vertices that are all reachable from each other.
Every disconnected graph can be decomposed into its connected components.
Use: Social network analysis — friend circles as components.
From drawing to data structure
A V × V 2D array where Matrix[i][j] = 1 if edge (i, j) exists.
Advantage: O(1) edge lookup | Disadvantage: O(V²) space
A V × E matrix where row = vertex, column = edge. Entry is 1 if vertex is an endpoint of that edge.
Advantage: Captures edge identity | Disadvantage: Sparse, O(V × E) space
Each vertex stores a list of its neighbors. Space-efficient for sparse graphs.
Advantage: O(V + E) space | Disadvantage: Edge lookup O(degree)
V × V matrix — constant-time edge lookup
An Adjacency Matrix is a V × V matrix where:
Matrix[i][j] = 1 if edge (i, j) exists
Matrix[i][j] = 0 otherwise
Both rows and columns represent vertices, listed in order A, B, C, D, E.
For undirected graphs, Matrix[i][j] = Matrix[j][i]. The matrix is symmetric about the diagonal.
For directed graphs, Matrix[i][j] ≠ Matrix[j][i] in general — direction matters.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 0 | 1 | 0 |
| C | 1 | 0 | 0 | 1 | 0 |
| D | 0 | 1 | 1 | 0 | 1 |
| E | 0 | 0 | 0 | 1 | 0 |
V × E matrix — one column per edge
An Incidence Matrix is a V × E matrix:
Rows = vertices (A, B, C, D)
Columns = edges (e1, e2, e3, e4)
Each column has exactly two 1's — the endpoints of that edge.
Column for edge (A, B): row A = 1, row B = 1, all others = 0
Each column has one +1 (tail) and one −1 (head).
Edge A→B: row A = +1, row B = −1
| e1 | e2 | e3 | e4 | |
|---|---|---|---|---|
| A | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 1 | 0 |
| C | 0 | 1 | 0 | 1 |
| D | 0 | 0 | 1 | 1 |
Choosing the right representation
| Criteria | ▦ Adjacency Matrix | ⊞ Incidence Matrix |
|---|---|---|
| 📐 Rows | V (vertices) | V (vertices) |
| 📊 Columns | V (vertices) | E (edges) |
| 💾 Memory | O(V²) — wasteful for sparse | O(V × E) — better for sparse |
| 🔍 Edge Search | O(1) | O(E) |
| 🔄 Traversal | O(V²) | O(V × E) |
| ➕ Insert Edge | O(1) | O(V) |
| 🗑️ Delete Edge | O(1) | O(V) |
| 🎯 Best For | Dense graphs, fast lookup | Edge-centric algorithms, circuits |
Array of lists — the most common choice
An Adjacency List stores every vertex together with a list of all its adjacent vertices.
Which one should you choose?
| Criteria | ▦ Adjacency Matrix | ⊞ Incidence Matrix | ≡ Adjacency List |
|---|---|---|---|
| Rows | V | V | V |
| Columns / Structure | V (full matrix) | E (full matrix) | Each row = neighbor list |
| Memory Usage | O(V²) | O(V × E) | O(V + E) |
| Edge Lookup | O(1) | O(E) | O(degree) |
| Traversal | O(V²) | O(V × E) | O(V + E) |
| Insert Edge | O(1) | O(V) | O(1) |
| Delete Edge | O(1) | O(V) | O(degree) |
| Sparse Graphs | Wasteful | OK | Ideal |
| Dense Graphs | Ideal | Verbose | Good |
| Implementation | Simple | Moderate | Simple |
Adding, removing, and searching
Insert a new vertex into the graph.
Delete vertex and all its incident edges.
Connect two existing vertices.
Delete a specific edge between vertices.
Check if a vertex or edge exists.
Pseudocode + live update
Depth-First Search (DFS) and Breadth-First Search (BFS)
Uses Stack — goes as deep as possible before backtracking.
Implemented via Recursion or explicit Stack.
Uses Queue — visits level by level, exploring all neighbors first.
Guarantees shortest path in unweighted graphs.
Explore deep before wide — stack-based traversal
DFS explores one branch completely before backtracking. It visits a vertex, marks it, then recursively visits each unvisited neighbor.
Level-by-level traversal — queue-based
BFS visits vertices level by level. It explores all neighbors at the current depth before moving to the next level.
Uses a Queue (FIFO).
Choosing the right traversal strategy
| Criteria | Depth-First Search (DFS) | Breadth-First Search (BFS) |
|---|---|---|
| Data Structure | Stack (or Recursion) | Queue |
| Traversal Style | Deep — goes as far as possible | Wide — visits all neighbors first |
| Memory | O(V) — path depth | O(V) — level width |
| Shortest Path | No guarantee | Yes (unweighted) |
| Recursion | Natural fit | Not used |
| Applications | Maze, Topo Sort, Cycle Detection | Shortest Path, GPS, Social Networks |
| Traversal Order | A → B → D → E → G → F → C | A → B → C → D → E → F → G |
| Time Complexity | O(V + E) | O(V + E) |