Graphs for Coding Interviews: Complete Beginner-to-Advanced Guide

May 31, 2026

Graphs for Coding Interviews: Complete Beginner-to-Advanced Guide

1. What is a Graph?

A graph is a collection of:

Vertices (Nodes) → Objects
Edges → Connections between objects

Example:

1 ----- 2
|       |
|       |
3 ----- 4

Nodes = {1,2,3,4}

Edges = {(1,2),(1,3),(2,4),(3,4)}

Types of Graphs

Undirected Graph

1 ----- 2

1 connected to 2 and 2 connected to 1.

Directed Graph

1 -----> 2

Only 1 can reach 2.

Weighted Graph

1 --5--> 2

Edge weight = 5

2. Matrix Implementation (Adjacency Matrix)

This is the easiest way to store a graph.

Suppose:

1 ----- 2
|       |
|       |
3 ----- 4

We create an n × n matrix.

vector<vector<int>> graph(5, vector<int>(5,0));

For edge (u,v):

graph[u][v] = 1;
graph[v][u] = 1;

Matrix becomes:

    1 2 3 4

1   0 1 1 0
2   1 0 0 1
3   1 0 0 1
4   0 1 1 0

How to Build Matrix

int n,m;
cin>>n>>m;

vector<vector<int>> adj(n+1, vector<int>(n+1,0));

for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;

    adj[u][v]=1;
    adj[v][u]=1;
}

Advantages

Easy to understand.

Checking edge existence:

adj[u][v]

Time:

O(1)

Disadvantages

For n=10000

Need:

10000 × 10000

memory.

Space:

O(V²)

Huge waste.

3. Adjacency List Implementation

Most interview problems use this.

Instead of storing all possibilities, store only neighbors.

Graph:

1 ----- 2
|       |
|       |
3 ----- 4

Representation:

1 -> 2,3
2 -> 1,4
3 -> 1,4
4 -> 2,3

Code

int n,m;
cin>>n>>m;

vector<vector<int>> adj(n+1);

for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;

    adj[u].push_back(v);
    adj[v].push_back(u);
}

Visualization

adj[1] = {2,3}
adj[2] = {1,4}
adj[3] = {1,4}
adj[4] = {2,3}

Advantages

Space:

O(V + E)

Much better than matrix.

Most graph interview problems use adjacency lists.

Matrix vs Adjacency List

Feature	Matrix	Adj List
Space	O(V²)	O(V+E)
Edge Check	O(1)	O(degree)
Traversal	O(V²)	O(V+E)
Interview Usage	Rare	Very Common

4. Breadth First Search (BFS)

BFS explores level by level.

Uses:

Queue

Example:

Traversal:

1
2 3
4 5

Result:

1 2 3 4 5

BFS Using Adjacency List

vector<int> bfs(int V, vector<vector<int>>& adj){

    vector<int> ans;
    vector<int> vis(V,0);

    queue<int> q;

    q.push(0);
    vis[0]=1;

    while(!q.empty()){

        int node=q.front();
        q.pop();

        ans.push_back(node);

        for(auto neigh:adj[node]){

            if(!vis[neigh]){
                vis[neigh]=1;
                q.push(neigh);
            }
        }
    }

    return ans;
}

Time:

O(V+E)

BFS Using Matrix

void bfsMatrix(vector<vector<int>>& graph){

    int n=graph.size();

    vector<int> vis(n,0);

    queue<int> q;

    q.push(0);
    vis[0]=1;

    while(!q.empty()){

        int node=q.front();
        q.pop();

        cout<<node<<" ";

        for(int neigh=0;neigh<n;neigh++){

            if(graph[node][neigh]==1 &&
               !vis[neigh]){

                vis[neigh]=1;
                q.push(neigh);
            }
        }
    }
}

Time:

O(V²)

5. Depth First Search (DFS)

DFS explores one path completely.

Uses:

Recursion
or
Stack

Example:

1
|
2
|
4
|
5

Go deep first.

Result:

1 2 4 5 ...

Recursive DFS

void dfs(int node,
         vector<vector<int>>& adj,
         vector<int>& vis){

    vis[node]=1;

    cout<<node<<" ";

    for(auto neigh:adj[node]){

        if(!vis[neigh]){
            dfs(neigh,adj,vis);
        }
    }
}

DFS Using Matrix

void dfsMatrix(int node,
               vector<vector<int>>& graph,
               vector<int>& vis){

    vis[node]=1;

    cout<<node<<" ";

    int n=graph.size();

    for(int neigh=0;neigh<n;neigh++){

        if(graph[node][neigh]==1 &&
           !vis[neigh]){

            dfsMatrix(neigh,graph,vis);
        }
    }
}

6. DFS Using Stack

Recursion internally uses stack.

We can do it manually.

vector<int> dfsStack(int V,
                     vector<vector<int>>& adj){

    vector<int> ans;
    vector<int> vis(V,0);

    stack<int> st;

    st.push(0);

    while(!st.empty()){

        int node=st.top();
        st.pop();

        if(vis[node])
            continue;

        vis[node]=1;

        ans.push_back(node);

        for(auto neigh:adj[node]){

            if(!vis[neigh]){
                st.push(neigh);
            }
        }
    }

    return ans;
}

Graph Pattern Recognition

Most interview questions are one of these:

Pattern 1

"Find connected components"

Use:

DFS/BFS

Examples:

Number of Provinces
LINK : [ https://leetcode.com/problems/number-of-provinces/solutions/8304489/most-easy-explanation-on-leetcode-by-vis-6wzn ]
Number of Islands
LINK : https://leetcode.com/problems/number-of-islands/solutions/8304502/most-easy-explanation-on-leetcode-by-vis-hqzm]
Flood Fill
LINK : [https://leetcode.com/problems/flood-fill/solutions/8304506/most-easy-explanation-on-leetcode-by-vis-eth6]
Connected Components
LINK : []

Pattern 2

"Find shortest distance in unweighted graph"

Use:

BFS

Examples:

Word Ladder
01 Matrix
Shortest Path Binary Matrix

Pattern 3

"Spread process level by level"

Use:

Multi Source BFS

Examples:

Rotting Oranges
01 Matrix
Walls and Gates

Pattern 4

"Traverse all cells"

Treat matrix as graph.

Use:

DFS/BFS

Examples:

Flood Fill
Number of Islands
Surrounded Regions

Important Problems

1. Number of Provinces

Idea:

Each city = node

If city not visited:

DFS/BFS
count++

Connected Components problem.

2. Flood Fill

Idea:

Starting pixel.

Visit all connected pixels having same color.

Use:

DFS
or
BFS

Matrix becomes graph.

3. Rotting Oranges

Idea:

All rotten oranges start simultaneously.

Use:

Multi Source BFS

Push all rotten oranges into queue first.

4. 01 Matrix

Idea:

Distance from nearest zero.

Use:

Multi Source BFS

Push every 0 into queue.

5. Word Ladder

Idea:

Each word = node.

One character change = edge.

Need shortest transformation.

Use:

BFS

Because BFS gives shortest path in unweighted graph.

6. Number of Islands

Idea:

Grid graph.

Every land cell = node.

Find connected components.

Use:

DFS/BFS

7. Surrounded Regions

Idea:

Start DFS from boundary O's.

Mark safe cells.

Convert remaining O → X.

8. Course Schedule

Idea:

Directed Graph.

Use:

Topological Sort

9. Clone Graph

Idea:

Graph traversal + mapping.

Use:

DFS/BFS

10. Network Delay Time

Idea:

Weighted Graph.

Use:

Dijkstra

Interview Roadmap

Beginner

✅ Graph Representation

✅ BFS

✅ DFS

✅ Number of Provinces

✅ Number of Islands

✅ Flood Fill

Intermediate

✅ Rotting Oranges

✅ 01 Matrix

✅ Word Ladder

✅ Surrounded Regions

✅ Bipartite Graph

Advanced

✅ Topological Sort

✅ Course Schedule

✅ Dijkstra

✅ Bellman Ford

✅ Floyd Warshall

✅ Disjoint Set Union (DSU)

Final Cheat Sheet

Graph Representation
    |
    +---- Matrix
    |
    +---- Adjacency List

Traversal
    |
    +---- BFS (Queue)
    |
    +---- DFS (Recursion)
    |
    +---- DFS (Stack)

Connected Components
    |
    +---- Number of Provinces
    +---- Number of Islands

Multi Source BFS
    |
    +---- Rotting Oranges
    +---- 01 Matrix

Shortest Path
    |
    +---- BFS (Unweighted)
    +---- Dijkstra (Weighted)

Directed Graph
    |
    +---- Topological Sort
    +---- Course Schedule

If you're preparing for interviews, the strongest order is:

Graph Representation → BFS → DFS → Number of Provinces → Flood Fill → Number of Islands → Rotting Oranges → 01 Matrix → Word Ladder → Topological Sort → Dijkstra.

This sequence covers about 70–80% of graph questions commonly asked in coding interviews.

Comments (0)