Graphs
A Graph is a non-linear data structure used to represent relationships or connections between objects.
If a tree represents a hierarchy:
A / \ B C
a graph can represent much more general relationships:
A -------- B | \ | | \ | C -------- D \ / \-------E
There is no requirement that there be a single root, and cycles are allowed.
Graph = Vertices (nodes) + Edges (connections)
1. What Is a Graph?
A graph is mathematically represented as:
G = (V, E)
where:
V= set of verticesE= set of edges
For example:
Vertices: A, B, C, D Edges: A-B A-C B-D C-D
Graph:
A / \ B C \ / D
Here:
V = {A, B, C, D} E = {(A,B), (A,C), (B,D), (C,D)}
2. Real-Life Examples
Graphs are everywhere.
Social Network
Alice ---- Bob | | | | Charlie --- David
- Person = vertex
- Friendship = edge
Google Maps
City A ---- City B | | City C ---- City D
- City = vertex
- Road = edge
Computer Network
PC1 ---- Router ---- PC2 | PC3
- Device = vertex
- Connection = edge
Website Links
Page A → Page B ↓ ↓ Page C → Page D
- Web page = vertex
- Link = edge
3. Graph Terminology ⭐
Before algorithms, you need to understand the vocabulary.
Vertex / Node
A point in the graph.
A
Here A is a vertex.
Edge
A connection between two vertices.
A ----- B
A-B is an edge.
Adjacent Vertices
Two vertices connected directly by an edge.
A ----- B
A and B are adjacent.
Degree
The number of edges connected to a vertex.
Example:
B | A ---- C ---- D | E
Degree of C:
degree(C) = 4
because it connects to:
A, B, D, E
4. Directed Graph
In a directed graph, edges have a direction.
A → B
means:
A can go to B
but not necessarily:
B → A
Example:
A → B → C ↓ ↓ D ←-----E
This is called a:
Directed Graph / Digraph
5. Undirected Graph
In an undirected graph, connections have no direction.
A ----- B
means:
A is connected to B B is connected to A
Example:
A / \ B---C
6. Directed vs Undirected
| Feature | Undirected | Directed |
|---|---|---|
| Direction | No | Yes |
| Edge | A-B | A → B |
| Relationship | Usually mutual | Can be one-way |
| Example | Friendship | Instagram follow |
For example:
Friendship
Alice ----- Bob
Usually mutual.
Following
Alice → Bob
Alice follows Bob, but Bob doesn't necessarily follow Alice.
7. Weighted Graph ⭐
An edge can have a weight.
Example:
A ----5---- B \ / 2 3 \ / C
Weights could represent:
- Distance
- Cost
- Time
- Network latency
- Price
For example:
Kathmandu ----200km---- Pokhara
The 200 is the edge weight.
8. Unweighted Graph
If edges don't have weights:
A ----- B | | C
we simply care about whether a connection exists.
9. Weighted vs Unweighted
Unweighted
A ----- B
Question:
Are A and B connected?
Weighted
A ---10--- B
Question:
What is the cost/distance between A and B?
10. Graph With Self-Loop
An edge can sometimes connect a vertex to itself.
↺ A
This is called a:
Self-loop
11. Parallel Edges
Sometimes two vertices can have multiple edges between them.
===== A -------- B =====
This is called:
Parallel edges / Multiple edges
Whether these are allowed depends on the graph type/model.
12. Simple Graph
A simple graph generally has:
- No self-loops
- No parallel/multiple edges
Example:
A ----- B | | | | C ----- D
13. Path ⭐
A path is a sequence of vertices connected by edges.
Example:
A ----- B ----- C ----- D
Path from A to D:
A → B → C → D
The path contains:
4 vertices 3 edges
14. Path Length
The number of edges in a path.
A → B → C → D
Number of edges:
3
Therefore:
Path length = 3
15. Cycle ⭐
A cycle is a path that starts and ends at the same vertex.
Example:
A / \ B---C
Cycle:
A → B → C → A
Graphs can contain cycles.
Trees cannot contain cycles.
16. Connected Graph
An undirected graph is connected if every vertex can be reached from every other vertex.
Example:
A ----- B | | C ----- D
Every vertex is reachable.
So it is connected.
17. Disconnected Graph
Example:
A ----- B C ----- D
There is no path between:
A/B
and:
C/D
Therefore, the graph is disconnected.
18. Connected Components
Each separate connected part is called a connected component.
Example:
Component 1: A ----- B | | C ----- D Component 2: E ----- F
There are:
2 connected components
19. Tree vs Graph
You already learned trees, so this distinction is important.
Tree
A tree is a special type of graph.
For n vertices, a tree has:
n - 1 edges
and is:
Connected + Acyclic
Example:
A / \ B C / D
No cycle.
Graph
A general graph can have:
- Cycles
- Multiple components
- Different numbers of edges
- Directed edges
- Weighted edges
Example:
A ----- B | \ | | \ | C ----- D
20. Important Relationship
Remember:
Every tree is a graph, but every graph is NOT a tree.
Think:
Graph ┌──────┴──────┐ │ │ Trees Other graphs
21. Graph Representations
This is one of the most important parts.
There are three common ways to represent graphs:
- Adjacency Matrix
- Adjacency List
- Edge List
22. Adjacency Matrix
Suppose:
A ----- B | | | | C ----- D
Vertices:
A B C D
We can create a matrix.
For an unweighted graph:
A B C D A 0 1 1 0 B 1 0 0 1 C 1 0 0 1 D 0 1 1 0
1 means:
Edge exists
0 means:
No edge
23. Matrix Example
If:
A ----- B
then:
matrix[A][B] = 1 matrix[B][A] = 1
because it is undirected.
For directed:
A → B
we have:
matrix[A][B] = 1 matrix[B][A] = 0
24. C++ Adjacency Matrix
int graph[4][4] = { {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 1}, {0, 1, 1, 0} };
For:
A = 0 B = 1 C = 2 D = 3
25. Weighted Adjacency Matrix
Suppose:
A --5-- B A --2-- C
Matrix could be:
A B C A 0 5 2 B 5 0 ∞ C 2 ∞ 0
∞ means no direct edge.
26. Adjacency Matrix Complexity
For V vertices:
Space = O(V²)
Checking whether an edge exists:
O(1)
Adding/removing an edge:
O(1)
But traversing all neighbors can take:
O(V)
27. Adjacency List
An adjacency list stores the neighbors of each vertex.
For:
A ----- B | | C ----- D
we can write:
A → B, C B → A, D C → A, D D → B, C
This is much more memory-efficient for sparse graphs.
28. C++ Adjacency List
The most common representation:
vector<vector<int>> graph;
Example:
int V = 4; vector<vector<int>> graph(V); graph[0].push_back(1); graph[0].push_back(2); graph[1].push_back(0); graph[1].push_back(3); graph[2].push_back(0); graph[2].push_back(3); graph[3].push_back(1); graph[3].push_back(2);
29. Building an Undirected Graph
Instead of manually writing both directions:
void addEdge(vector<vector<int>>& graph, int u, int v) { graph[u].push_back(v); graph[v].push_back(u); }
Then:
addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 3); addEdge(graph, 2, 3);
Graph:
0 ----- 1 | | | | 2 ----- 3
30. Building a Directed Graph
For:
0 → 1
we only add:
graph[0].push_back(1);
We do not add:
graph[1].push_back(0);
unless the reverse edge actually exists.
31. Edge List
An edge list simply stores all edges.
Example:
A-B A-C B-D C-D
C++:
vector<pair<int, int>> edges;
Then:
edges.push_back({0, 1}); edges.push_back({0, 2}); edges.push_back({1, 3}); edges.push_back({2, 3});
For weighted graphs:
vector<tuple<int, int, int>> edges;
where:
(u, v, weight)
Example:
edges.push_back({0, 1, 5});
means:
0 --5-- 1
32. Matrix vs List vs Edge List
| Representation | Space | Edge Check | Best For |
|---|---|---|---|
| Matrix | O(V²) | O(1) | Dense graphs |
| List | O(V+E) | O(degree) | Sparse graphs |
| Edge List | O(E) | O(E) | Edge-based algorithms |
For most graph traversal problems in C++, you'll frequently use:
vector<vector<int>>
33. Sparse vs Dense Graph
This is important.
Sparse Graph
Few edges:
V = 1000 E = 1500
Adjacency list is usually better.
Space:
O(V + E)
Dense Graph
Many edges:
V = 1000 E ≈ V²
Adjacency matrix may be useful.
Space:
O(V²)
34. Directed Graph Degree
For directed graphs, we have two types of degree.
Indegree
Number of edges coming into a vertex.
A → B C → B
For B:
indegree(B) = 2
Outdegree
Number of edges going out of a vertex.
B → D B → E
For B:
outdegree(B) = 2
35. Example of Directed Degree
A → B → C ↓ D
For B:
Indegree = 1 Outdegree = 2
Because:
A → B B → C B → D
36. Handshaking Theorem
For an undirected graph:
Sum of degrees = 2E
where:
E = number of edges
Example:
A ----- B | | C ----- D
Each vertex has degree 2.
So:
2 + 2 + 2 + 2 = 8
There are:
E = 4
Therefore:
2E = 2 × 4 = 8
37. Important Graph Types
You should recognize these:
Undirected
A ----- B
Directed
A → B
Weighted
A --5-- B
Unweighted
A ----- B
Connected
Every vertex reachable.
Disconnected
Multiple components.
Cyclic
Contains a cycle.
Acyclic
Contains no cycle.
Complete Graph
Every pair of distinct vertices has an edge.
For 4 vertices:
A / | \ B--|--C \ | / D
Number of edges in an undirected complete graph:
E = V(V - 1) / 2
38. Complete Graph Example
For:
V = 4
maximum number of undirected edges:
4(4-1)/2 = 4×3/2 = 6
So:
E = 6
39. Bipartite Graph
A graph is bipartite if its vertices can be divided into two groups such that no edge connects vertices within the same group.
Example:
Group A Group B A ------------- 1 | | B ------------- 2 | | C ------------- 3
There are no edges:
A-B B-C
inside Group A.
And no edges between:
1-2 2-3
inside Group B.
40. Real-Life Bipartite Example
Students and courses:
Students Courses Uday ---------- C++ | | | | └------------ Web Ram ---------- C++ | └------------ Networks
One group:
Students
Other group:
Courses
Edges represent enrollment.
41. DAG — Directed Acyclic Graph
A DAG is:
Directed + Acyclic
Example:
A → B → D ↓ C → D
There is direction, but no cycle.
DAGs are extremely important in:
- Task scheduling
- Course prerequisites
- Build systems
- Dependency resolution
- Topological sorting
42. Example: Course Prerequisites
Suppose:
Programming Basics ↓ DSA ↓ Algorithms
You must learn:
Programming Basics
before:
DSA
and DSA before Algorithms.
This can be represented as a DAG.
43. Graph Traversal
Once we have a graph, we usually want to visit its vertices.
Two fundamental traversal algorithms are:
BFS DFS
You have already seen these ideas with trees.
44. BFS — Breadth First Search
BFS explores level by level.
It uses a:
Queue
Example:
0 / \ 1 2 / \ 3 4
Starting from 0:
0 ↓ 1 2 ↓ 3 4
Traversal:
0 1 2 3 4
45. BFS C++
void bfs(int start, vector<vector<int>>& graph) { int n = graph.size(); vector<bool> visited(n, false); queue<int> q; visited[start] = true; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } }
46. Why visited[] Is Necessary
Consider:
A ----- B \ / \ / C
If we don't track visited nodes, we could repeatedly travel:
A → B → C → A → B → C ...
So we maintain:
vector<bool> visited(n, false);
When we visit a node:
visited[node] = true;
47. DFS — Depth First Search
DFS explores as deeply as possible before coming back.
It can use:
- Recursion
- Explicit stack
Example:
0 / \ 1 2 / \ 3 4
DFS could produce:
0 → 1 → 3 → 4 → 2
depending on adjacency order.
48. DFS C++ Recursive
void dfs( int node, vector<vector<int>>& graph, vector<bool>& visited ) { visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs(neighbor, graph, visited); } } }
Call:
vector<bool> visited(n, false); dfs(0, graph, visited);
49. DFS Using Stack
DFS can also be implemented iteratively:
void dfs(int start, vector<vector<int>>& graph) { int n = graph.size(); vector<bool> visited(n, false); stack<int> st; st.push(start); while (!st.empty()) { int node = st.top(); st.pop(); if (visited[node]) { continue; } visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { st.push(neighbor); } } } }
Remember:
DFS → Stack BFS → Queue
50. BFS vs DFS
| Feature | BFS | DFS |
|---|---|---|
| Full name | Breadth First Search | Depth First Search |
| Main structure | Queue | Stack/Recursion |
| Exploration | Level by level | Deep first |
| Shortest path in unweighted graph | Yes | Not generally |
| Cycle detection | Yes | Yes |
| Connected components | Yes | Yes |
| Topological sort | Possible | Common |
| Maze/path exploration | Yes | Yes |
51. Graph Traversal Complexity
With an adjacency list:
O(V + E)
Why?
Each vertex is processed approximately once:
O(V)
and each edge is examined:
O(E)
Therefore:
Total = O(V + E)
Space:
O(V)
for:
visited[] + queue/stack/recursion
52. BFS Shortest Path
One major application of BFS:
Shortest path in an unweighted graph.
Example:
A ----- B ----- C | | D ------------- E
Suppose we want shortest path:
A → C
Possible paths:
A → B → C = 2 edges A → D → E → C = 3 edges
BFS finds:
A → B → C
because BFS explores by distance:
Distance 0 → Distance 1 → Distance 2 → ...
53. Graph Cycle
A graph contains a cycle if we can start at a vertex and return to it following edges.
Example:
A ----- B | | | | D ----- C
Cycle:
A → B → C → D → A
Cycle detection is a very common graph problem.
54. Cycle Detection in Undirected Graph
With DFS, we can keep track of the parent.
bool hasCycle( int node, int parent, vector<vector<int>>& graph, vector<bool>& visited ) { visited[node] = true; for (int neighbor : graph[node]) { if (!visited[neighbor]) { if (hasCycle( neighbor, node, graph, visited )) { return true; } } else if (neighbor != parent) { return true; } } return false; }
The important idea:
If we reach an already visited node that isn't our parent, we found a cycle.
55. Connected Components
Suppose:
A ----- B C ----- D ----- E F
There are:
3 components
We can run DFS/BFS from every unvisited vertex.
int components = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { components++; dfs(i, graph, visited); } }
This pattern is extremely important.
56. Graph Algorithms You Will Learn Later
Graphs are a huge DSA topic.
After basic graphs and traversal, you'll encounter:
Traversal
BFS DFS
Shortest Path
BFS Dijkstra Bellman-Ford Floyd-Warshall
Minimum Spanning Tree
Prim's Algorithm Kruskal's Algorithm
Directed Graph
Topological Sort Cycle Detection
Advanced
Disjoint Set Union Strongly Connected Components Bridges Articulation Points
57. Dijkstra's Algorithm
Used for shortest paths when edge weights are non-negative.
Example:
A --4-- B | | 2 1 | | C --3-- D
Find shortest distance from:
A
to:
D
Possible paths:
A → B → D = 4 + 1 = 5 A → C → D = 2 + 3 = 5
Dijkstra finds the minimum distance.
A Min Priority Queue is commonly used.
This connects directly to the topic you just learned:
Priority Queue ↓ Dijkstra ↓ Graphs
58. Topological Sort
Used for a DAG.
Example:
A → B A → C B → D C → D
A valid ordering:
A → B → C → D
Another valid ordering may be:
A → C → B → D
provided all dependencies are respected.
Applications:
- Course scheduling
- Build dependencies
- Package dependencies
- Task scheduling
59. Minimum Spanning Tree
Given a connected weighted undirected graph:
A --4-- B | \ | 2 5 3 | \ | C --1-- D
A Minimum Spanning Tree (MST) connects all vertices with minimum total edge weight and no cycles.
Main algorithms:
Prim's Kruskal's
60. Graph Learning Roadmap
Your DSA roadmap now reaches the graph section:
Graphs | ┌──────────────┴──────────────┐ ↓ ↓ Representation Traversal | | Matrix / List BFS / DFS | | └──────────────┬──────────────┘ ↓ Graph Problems | ┌───────────────┼────────────────┐ ↓ ↓ ↓ Shortest Path MST Topological Sort | | | Dijkstra/BF/FW Prim/Kruskal DAG
61. Graph vs Tree vs BST vs Heap vs Trie
Now you have covered many tree-based structures.
| Structure | Main Idea |
|---|---|
| Tree | Hierarchical structure |
| Binary Tree | ≤ 2 children |
| BST | Ordered binary tree |
| Heap | Priority-based complete tree |
| Trie | Prefix/character tree |
| Graph | General connections |
The biggest difference is:
Tree ↓ Hierarchical BST ↓ Ordered Heap ↓ Priority Trie ↓ Prefix Graph ↓ Relationships / Connections
62. A Complete C++ Graph Example
Let's put the important basics together.
#include <iostream> #include <vector> #include <queue> using namespace std; void addEdge( vector<vector<int>>& graph, int u, int v ) { graph[u].push_back(v); graph[v].push_back(u); } void bfs( int start, vector<vector<int>>& graph ) { int n = graph.size(); vector<bool> visited(n, false); queue<int> q; visited[start] = true; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } } void dfs( int node, vector<vector<int>>& graph, vector<bool>& visited ) { visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs( neighbor, graph, visited ); } } } int main() { int V = 5; vector<vector<int>> graph(V); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 3); addEdge(graph, 1, 4); addEdge(graph, 2, 4); cout << "BFS: "; bfs(0, graph); cout << "\nDFS: "; vector<bool> visited(V, false); dfs(0, graph, visited); return 0; }
Possible output:
BFS: 0 1 2 3 4 DFS: 0 1 3 4 2
The exact DFS order can change depending on the order neighbors are stored.
🧠 Final Summary
You should now have this mental model:
GRAPH │ ├── Vertices │ └── Nodes │ ├── Edges │ └── Connections │ ├── Types │ ├── Directed │ ├── Undirected │ ├── Weighted │ ├── Unweighted │ ├── Connected │ ├── Disconnected │ ├── Cyclic │ ├── Acyclic │ ├── Bipartite │ └── DAG │ ├── Representations │ ├── Adjacency Matrix │ ├── Adjacency List ⭐ │ └── Edge List │ └── Traversal ├── BFS → Queue └── DFS → Stack / Recursion
The most important things to remember:
1. Graph = Vertices + Edges 2. Undirected: A ----- B 3. Directed: A → B 4. Weighted: A --5-- B 5. Adjacency Matrix: Space = O(V²) 6. Adjacency List: Space = O(V + E) 7. BFS: Queue O(V + E) 8. DFS: Stack/Recursion O(V + E) 9. BFS can find shortest paths in unweighted graphs. 10. Graphs can contain cycles, unlike trees.
And your roadmap is now:
Graphs ↓ Graph Traversal ↓ Sorting ↓ Searching ↓ Greedy Algorithms ↓ Divide and Conquer ↓ Dynamic Programming ↓ Bit Manipulation ↓ Advanced Data Structures ↓ Problem Solving