Graphs · BFS and DFS

G = (V, E)

• a set of vertices (or nodes)
• a set of edges connecting pairs of vertices

Notation: G = (V, E), where V is the set of vertices and E the set of edges.

Example:

Vertices: {A, B, C, D}
Edges: {(A,B), (B,C), (C,D), (A,D)}

Visual representation:
    A --- B
    |     |
    D --- C

Why use graphs?

• Social networks: people are vertices, friendships are edges
• Maps and navigation: cities are vertices, roads are edges
• Computer networks: computers are vertices, connections are edges
• Web pages: pages are vertices, hyperlinks are edges
• Dependencies: tasks are vertices, dependencies are edges

1 · Directed graph (digraph)

Edges have a direction — from one vertex to another.

    A --> B
    ↑     ↓
    D <-- C

Edges: (A,B), (B,C), (C,D), (D,A)

Applications: web page links (one-way), task dependencies, state transitions.

2 · Undirected graph

Edges have no direction — the connection goes both ways.

    A --- B
    |     |
    D --- C

Edges: (A,B), (B,C), (C,D), (A,D)

Applications: social networks (friendship is mutual), road networks (two-way roads).

3 · Weighted graph

Edges have weights — costs, distances, capacities.

    A --5-- B
    |       |
    3       7
    |       |
    D --2-- C

Edges: (A,B,5), (A,D,3), (B,C,7), (C,D,2)

Applications: road networks (distances), network routing (latency), flight routes (costs).

4 · Unweighted graph

All edges have equal weight (or weight = 1).

    A --- B
    |     |
    D --- C

5 · Cyclic graph

Contains at least one cycle — a path from a vertex back to itself.

    A --- B
    |     |
    D --- C

Cycle: A → B → C → D → A

6 · Acyclic graph

Contains no cycles.

    A --- B --- C
          |
          D

DAG (Directed Acyclic Graph) — a directed graph with no cycles:

• used in task scheduling
• dependency resolution
• topological sorting

7 · Connected graph

There is a path between every pair of vertices.

    A --- B
    |     |
    D --- C

8 · Disconnected graph

Some vertices are not reachable from others.

    A --- B     E --- F
    |     |
    D --- C

9 · Complete graph

Every pair of vertices is directly connected.

    A --- B
    |\   /|
    | \ / |
    |  X  |
    | / \ |
    |/   \|
    D --- C

Edges: (A,B), (A,C), (A,D), (B,C), (B,D), (C,D)

10 · Tree

A connected acyclic graph.

        A
       / \
      B   C
     / \
    D   E

Properties:

• N vertices have exactly N − 1 edges
• exactly one path between any two vertices
• removing any edge disconnects the graph

11 · Bipartite graph

Vertices can be divided into two sets such that edges only connect vertices from different sets. No edges exist within the same set.

Set 1          Set 2

  0 ----------- 1
   \           /
    \         /
     \       /
      \     /
       \   /
        \ /
         X
        / \
       /   \
      /     \
     /       \
    /         \
   /           \
  2 ----------- 3

Set 1: {0, 2}
Set 2: {1, 3}

Edges: (0,1), (0,3), (2,1), (2,3)

Verification:
- 0 connects to 1: Set 1 → Set 2 ✓
- 0 connects to 3: Set 1 → Set 2 ✓
- 2 connects to 1: Set 1 → Set 2 ✓
- 2 connects to 3: Set 1 → Set 2 ✓
- No edges within Set 1 (0 and 2 NOT connected) ✓
- No edges within Set 2 (1 and 3 NOT connected) ✓

This IS a bipartite graph!

Not bipartite — the triangle

    0
   / \
  1---2

This is NOT bipartite because:
- If we put 0 in Set 1, then 1 and 2 must be in Set 2
- But 1 and 2 are connected to each other
- This violates the bipartite rule!

Applications of bipartite graphs: matching problems (students to projects), job assignments (workers to tasks), task scheduling.

The words we will use

• Vertex (node): a point in the graph
• Edge: a connection between two vertices
• Adjacent vertices: two vertices connected by an edge
• Degree: the number of edges at a vertex — in-degree (incoming) and out-degree (outgoing) in a directed graph
• Path: a sequence of vertices connected by edges
• Cycle: a path that starts and ends at the same vertex
• Connected: a path exists between every pair of vertices
• Component: a maximal connected subgraph

1 · Adjacency matrix

A 2D array where matrix[i][j] tells whether there is an edge from vertex i to vertex j.

• Unweighted: matrix[i][j] = 1 if the edge exists, 0 if not
• Weighted: matrix[i][j] = weight if the edge exists, ∞ or 0 if not

Example. Graph:

    0 --- 1
    |     |
    3 --- 2

Adjacency matrix (undirected):

     0  1  2  3
  0 [0, 1, 0, 1]
  1 [1, 0, 1, 0]
  2 [0, 1, 0, 1]
  3 [1, 0, 1, 0]

Adjacency matrix · implementation

#include <iostream>
using namespace std;

const int MAXN = 100;  // Maximum number of vertices
int adj[MAXN][MAXN];   // Adjacency matrix
int n;                 // Number of vertices

// Add edge (undirected)
void addEdge(int u, int v) {
    adj[u][v] = 1;
    adj[v][u] = 1;
}

// Add directed edge
void addDirectedEdge(int u, int v) {
    adj[u][v] = 1;
}

// Add weighted edge
void addWeightedEdge(int u, int v, int weight) {
    adj[u][v] = weight;
    adj[v][u] = weight;
}

// Check if edge exists
bool hasEdge(int u, int v) {
    return adj[u][v] != 0;
}

// Print adjacency matrix
void printMatrix() {
    cout << "Adjacency Matrix:" << endl;
    cout << "   ";
    for (int i = 0; i < n; i++)
        cout << i << " ";
    cout << endl;

    for (int i = 0; i < n; i++) {
        cout << i << " [";
        for (int j = 0; j < n; j++) {
            cout << adj[i][j];
            if (j < n - 1) cout << " ";
        }
        cout << "]" << endl;
    }
}

int main() {
    n = 4;  // Number of vertices

    // Initialize matrix with zeros
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            adj[i][j] = 0;

    // Add edges
    addEdge(0, 1);
    addEdge(0, 3);
    addEdge(1, 2);
    addEdge(2, 3);

    printMatrix();

    // Print neighbors of vertex 0
    cout << "\nNeighbors of vertex 0: ";
    for (int i = 0; i < n; i++) {
        if (adj[0][i] != 0) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

Adjacency Matrix:
   0 1 2 3 
0 [0 1 0 1]
1 [1 0 1 0]
2 [0 1 0 1]
3 [1 0 1 0]

Neighbors of vertex 0: 1 3

Adjacency matrix · cost

Advantages: fast edge lookup — O(1); simple to implement; good for dense graphs.

Disadvantages: wastes space for sparse graphs — O(V²) even with few edges; iterating all edges takes O(V²).

Another version · the matrix read from input

Vertices numbered from 1 in the input: read m edges into the matrix, then print the neighbours of vertex k by scanning its row.

#include <iostream>

using namespace std;
int g[100][100];
int n, m, x, y, k;

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        x--;
        y--;
        g[x][y] = 1;
        g[y][x] = 1;
    } 

    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++)
    //         cout << g[i][j] << " ";
    //     cout << endl;
    // }
    cin >> k; k--;
    for (int i = 0; i < n; i++)
        if (g[k][i] == 1)
            cout << i + 1 << " ";
    return 0;
}

5 7
1 2
2 3
3 1
3 4
4 1
4 5
5 1
1

2 3 4 5

And a matrix given directly in the input — n, then n rows:

#include <iostream>

using namespace std;
int n;
int a[100][100];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << a[i][j] << " ";
        cout << endl;
    }
    return 0;
}

4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

2 · Adjacency list

An array of lists where adj[i] contains all neighbours of vertex i.

Example. The same graph:

    0 --- 1
    |     |
    3 --- 2

Adjacency list:

0: [1, 3]
1: [0, 2]
2: [1, 3]
3: [0, 2]

Adjacency list · implementation

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;     // Maximum number of vertices
vector<int> adj[MAXN];    // Adjacency list
int n;                    // Number of vertices

// Add edge (undirected)
void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

// Add directed edge
void addDirectedEdge(int u, int v) {
    adj[u].push_back(v);
}

// Check if edge exists
bool hasEdge(int u, int v) {
    for (int i = 0; i < adj[u].size(); i++) {
        if (adj[u][i] == v)
            return true;
    }
    return false;
}

// Print adjacency list
void printList() {
    cout << "Adjacency List:" << endl;
    for (int i = 0; i < n; i++) {
        cout << i << ": [";
        for (int j = 0; j < adj[i].size(); j++) {
            cout << adj[i][j];
            if (j < adj[i].size() - 1)
                cout << ", ";
        }
        cout << "]" << endl;
    }
}

int main() {
    n = 4;  // Number of vertices

    // Add edges
    addEdge(0, 1);
    addEdge(0, 3);
    addEdge(1, 2);
    addEdge(2, 3);

    printList();

    // Print neighbors of vertex 0
    cout << "\nNeighbors of vertex 0: ";
    for (int i = 0; i < adj[0].size(); i++) {
        cout << adj[0][i] << " ";
    }
    cout << endl;

    return 0;
}

Adjacency List:
0: [1, 3]
1: [0, 2]
2: [1, 3]
3: [0, 2]

Neighbors of vertex 0: 1 3

Adjacency list · weighted graphs

Each entry becomes a pair {neighbour, weight}.

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<pair<int, int>> adj[MAXN];  // {neighbor, weight}
int n;

void addWeightedEdge(int u, int v, int weight) {
    adj[u].push_back({v, weight});
    adj[v].push_back({u, weight});
}

void printWeightedList() {
    cout << "Weighted Adjacency List:" << endl;
    for (int i = 0; i < n; i++) {
        cout << i << ": [";
        for (int j = 0; j < adj[i].size(); j++) {
            cout << "(" << adj[i][j].first << "," << adj[i][j].second << ")";
            if (j < adj[i].size() - 1)
                cout << ", ";
        }
        cout << "]" << endl;
    }
}

int main() {
    n = 4;

    addWeightedEdge(0, 1, 5);
    addWeightedEdge(0, 3, 3);
    addWeightedEdge(1, 2, 7);
    addWeightedEdge(2, 3, 2);

    printWeightedList();

    return 0;
}

Weighted Adjacency List:
0: [(1,5), (3,3)]
1: [(0,5), (2,7)]
2: [(1,7), (3,2)]
3: [(0,3), (2,2)]

Adjacency list · cost

Advantages: space efficient for sparse graphs; fast iteration over neighbours; the most common representation.

Disadvantages: slower edge lookup than the matrix; a little more to implement.

Another version · the list read from input

The same input as the matrix version — the neighbours now come straight from g[k], in the order the edges were read.

#include <iostream>
#include <vector>

using namespace std;
vector<int> g[100];
int n, m, x, y, k;

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        x--;
        y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    // for (int i = 0; i < n; i++) {
    //     cout << i + 1 << " --- ";
    //     for (int j = 0; j < g[i].size(); j++)
    //         cout << g[i][j] + 1 << " ";
    //     cout << endl;
    // }
    cin >> k;
    k--;
    for (int i = 0; i < g[k].size(); i++)
        cout << g[k][i] + 1 << " ";
    return 0;
}

5 7
1 2
2 3
3 1
3 4
4 1
4 5
5 1
1

2 3 4 5

Weighted: n and m, then m triples x y w, then k — print each neighbour of k with the weight of the edge.

#include <iostream>
#include <vector>

using namespace std;
vector<pair<int, int> > g[100];
int n, m, x, y, w, k;

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> w;
        x--;
        y--;
        g[x].push_back(make_pair(y, w));
        g[y].push_back(make_pair(x, w));
    }

    // for (int i = 0; i < n; i++) {
    //     cout << i + 1 << " --- ";
    //     for (int j = 0; j < g[i].size(); j++)
    //         cout << g[i][j] + 1 << " ";
    //     cout << endl;
    // }
    cin >> k;
    k--;
    for (int i = 0; i < g[k].size(); i++)
        cout << g[k][i].first + 1 << " " << g[k][i].second << endl;
    return 0;
}

6 9
1 2 5
1 3 2
2 3 6
2 5 9
3 4 10
3 5 11
4 5 12
4 6 13 
5 6 14
3

1 2
2 6
4 10
5 11

3 · Edge list

A list of edges, each a pair — or a triple for weighted graphs.

Example. The same graph:

    0 --- 1
    |     |
    3 --- 2

Edge list:

[(0, 1), (0, 3), (1, 2), (2, 3)]

Edge list · implementation

#include <iostream>
#include <vector>
using namespace std;

struct Edge {
    int u, v;
    int weight;
};

const int MAXE = 1000;  // Maximum number of edges
Edge edges[MAXE];
int edgeCount = 0;
int n;  // Number of vertices

// Add edge
void addEdge(int u, int v, int weight = 1) {
    edges[edgeCount].u = u;
    edges[edgeCount].v = v;
    edges[edgeCount].weight = weight;
    edgeCount++;
}

// Print edge list
void printEdges() {
    cout << "Edge List:" << endl;
    for (int i = 0; i < edgeCount; i++) {
        cout << "(" << edges[i].u << ", " << edges[i].v;
        if (edges[i].weight != 1)
            cout << ", " << edges[i].weight;
        cout << ")" << endl;
    }
}

int main() {
    n = 4;  // Number of vertices

    // Add edges
    addEdge(0, 1);
    addEdge(0, 3);
    addEdge(1, 2);
    addEdge(2, 3);

    printEdges();

    cout << "\nTotal edges: " << edgeCount << endl;

    return 0;
}

Edge List:
(0, 1)
(0, 3)
(1, 2)
(2, 3)

Total edges: 4

Advantages: very simple; space efficient; good for edge-focused algorithms (Kruskal's MST).

Disadvantages: slow neighbour lookup; slow edge-existence check; not good for traversal.

Comparison of representations

When to use:

• Adjacency matrix: dense graphs, frequent edge queries
• Adjacency list: sparse graphs, traversal algorithms (most common)
• Edge list: simple storage, edge-based algorithms

BFS algorithm

1. Start from the source vertex
2. Visit all its neighbours (level 1)
3. Visit all neighbours of neighbours (level 2)
4. Continue until all reachable vertices are visited

Uses a queue (FIFO — First In, First Out).

BFS visualization

Graph:

        0
       / \
      1   2
     / \   \
    3   4   5

BFS starting from vertex 0:

Level 0: [0]
Level 1: [1, 2]
Level 2: [3, 4, 5]

Visit order: 0 → 1 → 2 → 3 → 4 → 5

BFS algorithm steps

1. Create a queue Q
2. Mark source vertex as visited
3. Enqueue source vertex
4. While Q is not empty:
   a. Dequeue vertex v from Q
   b. Process vertex v
   c. For each neighbor u of v:
      - If u is not visited:
        * Mark u as visited
        * Enqueue u

1 · The graph

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>   // added: reverse() lives here
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
int n;

2 · BFS from a source

// BFS from source vertex
void BFS(int source) {
    queue<int> q;

    // Initialize visited array
    for (int i = 0; i < n; i++)
        visited[i] = false;

    // Start from source
    visited[source] = true;
    q.push(source);

    cout << "BFS traversal: ";

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        cout << v << " ";

        // Visit all neighbors
        for (int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i];
            if (!visited[u]) {
                visited[u] = true;
                q.push(u);
            }
        }
    }

    cout << endl;
}

3 · BFS with distances

// BFS with distance tracking
void BFS_with_distance(int source) {
    queue<int> q;
    int distance[MAXN];

    // Initialize
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        distance[i] = -1;
    }

    visited[source] = true;
    distance[source] = 0;
    q.push(source);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i];
            if (!visited[u]) {
                visited[u] = true;
                distance[u] = distance[v] + 1;
                q.push(u);
            }
        }
    }

    cout << "Distances from vertex " << source << ":" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Vertex " << i << ": ";
        if (distance[i] == -1)
            cout << "unreachable" << endl;
        else
            cout << distance[i] << endl;
    }
}

-1 means "not reached yet" — it doubles as the visited mark for distances.

4 · BFS with parents — the shortest path

// BFS with parent tracking (for shortest path)
void BFS_with_path(int source, int target) {
    queue<int> q;
    int parent[MAXN];

    // Initialize
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        parent[i] = -1;
    }

    visited[source] = true;
    q.push(source);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        if (v == target)
            break;

        for (int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i];
            if (!visited[u]) {
                visited[u] = true;
                parent[u] = v;
                q.push(u);
            }
        }
    }

    // Reconstruct path
    if (!visited[target]) {
        cout << "No path exists" << endl;
        return;
    }

    vector<int> path;
    int current = target;
    while (current != -1) {
        path.push_back(current);
        current = parent[current];
    }

    reverse(path.begin(), path.end());

    cout << "Shortest path from " << source << " to " << target << ": ";
    for (int i = 0; i < path.size(); i++) {
        cout << path[i];
        if (i < path.size() - 1)
            cout << " -> ";
    }
    cout << endl;
}

The path is collected from the target backwards, so it has to be reversed before printing.

5 · main — and what it prints

int main() {
    n = 6;  // Number of vertices

    // Add edges
    adj[0].push_back(1);
    adj[1].push_back(0);

    adj[0].push_back(2);
    adj[2].push_back(0);

    adj[1].push_back(3);
    adj[3].push_back(1);

    adj[1].push_back(4);
    adj[4].push_back(1);

    adj[2].push_back(5);
    adj[5].push_back(2);

    cout << "Graph structure:" << endl;
    cout << "    0" << endl;
    cout << "   / \\" << endl;
    cout << "  1   2" << endl;
    cout << " / \\   \\" << endl;
    cout << "3   4   5" << endl;
    cout << endl;

    BFS(0);
    cout << endl;

    BFS_with_distance(0);
    cout << endl;

    BFS_with_path(0, 5);

    return 0;
}

Graph structure:
    0
   / \
  1   2
 / \   \
3   4   5

BFS traversal: 0 1 2 3 4 5

Distances from vertex 0:
Vertex 0: 0
Vertex 1: 1
Vertex 2: 1
Vertex 3: 2
Vertex 4: 2
Vertex 5: 2

Shortest path from 0 to 5: 0 -> 2 -> 5

The whole program

Everything above in one file — open it and press ▶ edit & run.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>   // added: reverse() lives here
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
int n;

// BFS from source vertex
void BFS(int source) {
    queue<int> q;

    // Initialize visited array
    for (int i = 0; i < n; i++)
        visited[i] = false;

    // Start from source
    visited[source] = true;
    q.push(source);

    cout << "BFS traversal: ";

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        cout << v << " ";

        // Visit all neighbors
        for (int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i];
            if (!visited[u]) {
                visited[u] = true;
                q.push(u);
            }
        }
    }

    cout << endl;
}

// BFS with distance tracking
void BFS_with_distance(int source) {
    queue<int> q;
    int distance[MAXN];

    // Initialize
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        distance[i] = -1;
    }

    visited[source] = true;
    distance[source] = 0;
    q.push(source);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i];
            if (!visited[u]) {
                visited[u] = true;
                distance[u] = distance[v] + 1;
                q.push(u);
            }
        }
    }

    cout << "Distances from vertex " << source << ":" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Vertex " << i << ": ";
        if (distance[i] == -1)
            cout << "unreachable" << endl;
        else
            cout << distance[i] << endl;
    }
}

// BFS with parent tracking (for shortest path)
void BFS_with_path(int source, int target) {
    queue<int> q;
    int parent[MAXN];

    // Initialize
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        parent[i] = -1;
    }

    visited[source] = true;
    q.push(source);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        if (v == target)
            break;

        for (int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i];
            if (!visited[u]) {
                visited[u] = true;
                parent[u] = v;
                q.push(u);
            }
        }
    }

    // Reconstruct path
    if (!visited[target]) {
        cout << "No path exists" << endl;
        return;
    }

    vector<int> path;
    int current = target;
    while (current != -1) {
        path.push_back(current);
        current = parent[current];
    }

    reverse(path.begin(), path.end());

    cout << "Shortest path from " << source << " to " << target << ": ";
    for (int i = 0; i < path.size(); i++) {
        cout << path[i];
        if (i < path.size() - 1)
            cout << " -> ";
    }
    cout << endl;
}

int main() {
    n = 6;  // Number of vertices

    // Add edges
    adj[0].push_back(1);
    adj[1].push_back(0);

    adj[0].push_back(2);
    adj[2].push_back(0);

    adj[1].push_back(3);
    adj[3].push_back(1);

    adj[1].push_back(4);
    adj[4].push_back(1);

    adj[2].push_back(5);
    adj[5].push_back(2);

    cout << "Graph structure:" << endl;
    cout << "    0" << endl;
    cout << "   / \\" << endl;
    cout << "  1   2" << endl;
    cout << " / \\   \\" << endl;
    cout << "3   4   5" << endl;
    cout << endl;

    BFS(0);
    cout << endl;

    BFS_with_distance(0);
    cout << endl;

    BFS_with_path(0, 5);

    return 0;
}

BFS from vertex 0

Graph:

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

Initial:
  visited = [false, false, false, false, false]
  queue = []

Step 1: Start from vertex 0
  visited = [true, false, false, false, false]
  queue = [0]

Step 2: Dequeue 0, visit neighbors 1 and 2
  visited = [true, true, true, false, false]
  queue = [1, 2]
  Output: 0

Step 3: Dequeue 1, visit neighbors 3 and 4
  visited = [true, true, true, true, true]
  queue = [2, 3, 4]
  Output: 0 1

Step 4: Dequeue 2, no new neighbors
  queue = [3, 4]
  Output: 0 1 2

Step 5: Dequeue 3, no new neighbors
  queue = [4]
  Output: 0 1 2 3

Step 6: Dequeue 4, no new neighbors
  queue = []
  Output: 0 1 2 3 4

Final output: 0 1 2 3 4

1 · Shortest path in an unweighted graph

BFS finds the shortest path — the minimum number of edges — from the source to every other vertex.

int shortestPath(Graph& g, int source, int target) {
    vector<bool> visited(n, false);
    vector<int> distance(n, -1);
    queue<int> q;

    visited[source] = true;
    distance[source] = 0;
    q.push(source);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        if (v == target)
            return distance[target];

        for (int u : adj[v]) {
            if (!visited[u]) {
                visited[u] = true;
                distance[u] = distance[v] + 1;
                q.push(u);
            }
        }
    }

    return -1;  // No path exists
}

2 · Check if the graph is connected

One BFS from vertex 0 and count how many vertices it reaches.

bool isConnected(Graph& g) {
    vector<bool> visited(n, false);
    queue<int> q;

    visited[0] = true;
    q.push(0);
    int count = 1;

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int u : adj[v]) {
            if (!visited[u]) {
                visited[u] = true;
                q.push(u);
                count++;
            }
        }
    }

    return count == n;
}

3 · Find connected components

int countComponents(Graph& g) {
    vector<bool> visited(n, false);
    int components = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            components++;

            // BFS from vertex i
            queue<int> q;
            visited[i] = true;
            q.push(i);

            while (!q.empty()) {
                int v = q.front();
                q.pop();

                for (int u : adj[v]) {
                    if (!visited[u]) {
                        visited[u] = true;
                        q.push(u);
                    }
                }
            }
        }
    }

    return components;
}

4 · Bipartite graph check

Check whether the graph can be coloured with 2 colours.

bool isBipartite(Graph& g) {
    vector<int> color(n, -1);
    queue<int> q;

    for (int s = 0; s < n; s++) {   // added: start from every vertex, not only 0 —
        if (color[s] != -1)          // otherwise a second component is never checked
            continue;
        color[s] = 0;
        q.push(s);

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            for (int u : adj[v]) {
                if (color[u] == -1) {
                    color[u] = 1 - color[v];
                    q.push(u);
                } else if (color[u] == color[v]) {
                    return false;  // Same color as neighbor
                }
            }
        }
    }

    return true;
}

5 · Level order traversal

Print the vertices level by level — q.size() at the start of a level is exactly that level.

void levelOrder(Graph& g, int source) {
    vector<bool> visited(n, false);
    queue<int> q;

    visited[source] = true;
    q.push(source);

    int level = 0;

    while (!q.empty()) {
        int size = q.size();
        cout << "Level " << level << ": ";

        for (int i = 0; i < size; i++) {
            int v = q.front();
            q.pop();
            cout << v << " ";

            for (int u : adj[v]) {
                if (!visited[u]) {
                    visited[u] = true;
                    q.push(u);
                }
            }
        }

        cout << endl;
        level++;
    }
}

Another version · counting components on a matrix

BFS over an adjacency matrix: the neighbours of x are all y with g[x][y] == 1, so one BFS costs O(V²). The loop in main starts a new BFS from every unvisited vertex and counts them.

void bfs(int x) {
    q.push(x);
    u[x] = 1;
    d[x] = 0;
    while (!q.empty()) {
        x = q.front();
        for (int y = 0; y < n; y++) {
            if (u[y] == 0 && g[x][y] == 1) {
                u[y] = 1;
                d[y] = d[x] + 1;
                q.push(y);
            }
        }
        q.pop();
    }
}

#include <iostream>
#include <queue>

using namespace std;
int g[100][100];
queue<int> q;
int u[100];
int d[100];
int n, m, x, y;

void bfs(int x) {
    q.push(x);
    u[x] = 1;
    d[x] = 0;
    while (!q.empty()) {
        x = q.front();
        for (int y = 0; y < n; y++) {
            if (u[y] == 0 && g[x][y] == 1) {
                u[y] = 1;
                d[y] = d[x] + 1;
                q.push(y);
            }
        }
        q.pop();
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y; 
        x--; y--;
        g[x][y] = 1;
        g[y][x] = 1;
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) // i = 10
        if (u[i] == 0) {
            bfs(i);
            cnt++;
        }
    cout << cnt;
    // for (int i = 0; i < n; i++)
    //     cout << d[i] << " ";

    return 0;
}

5 7
1 2
2 3
3 1
3 4
4 1
4 5
5 1

1

Another version · BFS on a grid

Every cell is a vertex, its four side neighbours are the edges. Free cells are 0, walls are 1; the start gets 2 and every reached cell gets its parent's value + 1 — so a cell holds distance + 2.

int dx[4] = {1, -1, 0,  0};
int dy[4] = {0,  0, 1, -1};

bool ok(int x, int y) {
    return (x >= 0) && (x < n) && (y >= 0) && (y < m);
}

void solve(int x, int y) {
    queue<pair<int, int> > q;
    q.push(make_pair(x, y));
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int x1 = x + dx[i];
            int y1 = y + dy[i];
            if (ok(x1, y1) && a[x1][y1] == 0) {
                a[x1][y1] = a[x][y] + 1;
                q.push(make_pair(x1, y1));
            }
        }
        // if (x + 1 < n && a[x + 1][y] == 0) {
        //     a[x + 1][y] = a[x][y] + 1;
        //     q.push(make_pair(x + 1, y));
        // }
        // if (x - 1 >= 0 && a[x - 1][y] == 0) {
        //     a[x - 1][y] = a[x][y] + 1;
        //     q.push(make_pair(x - 1, y));
        // }

        // if (y + 1 < m && a[x][y + 1] == 0) {
        //     a[x][y + 1] = a[x][y] + 1;
        //     q.push(make_pair(x, y + 1));
        // }
        // if (y - 1 >= 0 && a[x][y - 1] == 0) {
        //     a[x][y - 1] = a[x][y] + 1;
        //     q.push(make_pair(x, y - 1));
        // }
    }
}

#include <iostream>
#include <queue>

using namespace std;

int n, m;
int a[100][100];

int dx[4] = {1, -1, 0,  0};
int dy[4] = {0,  0, 1, -1};

bool ok(int x, int y) {
    return (x >= 0) && (x < n) && (y >= 0) && (y < m);
}

void solve(int x, int y) {
    queue<pair<int, int> > q;
    q.push(make_pair(x, y));
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int x1 = x + dx[i];
            int y1 = y + dy[i];
            if (ok(x1, y1) && a[x1][y1] == 0) {
                a[x1][y1] = a[x][y] + 1;
                q.push(make_pair(x1, y1));
            }
        }
        // if (x + 1 < n && a[x + 1][y] == 0) {
        //     a[x + 1][y] = a[x][y] + 1;
        //     q.push(make_pair(x + 1, y));
        // }
        // if (x - 1 >= 0 && a[x - 1][y] == 0) {
        //     a[x - 1][y] = a[x][y] + 1;
        //     q.push(make_pair(x - 1, y));
        // }

        // if (y + 1 < m && a[x][y + 1] == 0) {
        //     a[x][y + 1] = a[x][y] + 1;
        //     q.push(make_pair(x, y + 1));
        // }
        // if (y - 1 >= 0 && a[x][y - 1] == 0) {
        //     a[x][y - 1] = a[x][y] + 1;
        //     q.push(make_pair(x, y - 1));
        // }
    }
}

int main() {
    int x, y;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    cin >> x >> y;
    a[x][y] = 2;
    solve(x, y);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) 
            cout << a[i][j] << " ";
        cout << endl;
    }
    return 0;
}

4 5
0 0 0 1 0
0 1 0 1 0
0 1 0 0 0
0 0 0 1 0
0 0

2 3 4 1 10
3 1 5 1 9
4 1 6 7 8
5 6 7 1 9

The same BFS with the four moves written out as four ifs:

#include <iostream>
#include <queue>

using namespace std;
int a[100][100];
int n;

void modify(int x, int y) {
    a[x][y] = 2;
    queue<pair<int, int> > q;
    q.push(make_pair(x, y));
    while (!q.empty()) {
        // x + 1, y
        x = q.front().first;
        y = q.front().second;
        // cout << x << " " << y << endl;
        q.pop();
        if (x + 1 < n && a[x + 1][y] == 0) {
            q.push(make_pair(x + 1, y));
            a[x + 1][y] = a[x][y] + 1;
        }
        if (x - 1 >= 0 && a[x - 1][y] == 0) {
            q.push(make_pair(x - 1, y));
            a[x - 1][y] = a[x][y] + 1;
        }
        if (y - 1 >= 0 && a[x][y - 1] == 0) {
            q.push(make_pair(x, y - 1));
            a[x][y - 1] = a[x][y] + 1;
        }
        if (y + 1 < n && a[x][y + 1] == 0) {
            q.push(make_pair(x, y + 1));
            a[x][y + 1] = a[x][y] + 1;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    int x, y;
    cin >> x >> y;
    modify(x, y);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

Another version · knight moves

A chessboard 8 × 8, the knight's eight moves are the edges. The start gets 1, so the answer for the target cell is its value − 1.

int dx[8] = {-2, -2,  2, 2, -1, -1,  1, 1};
int dy[8] = {-1,  1, -1, 1, -2,  2, -2, 2};

#include <iostream>
#include <queue>

using namespace std;

int n, m;
int a[100][100];


int dx[8] = {-2, -2,  2, 2, -1, -1,  1, 1};
int dy[8] = {-1,  1, -1, 1, -2,  2, -2, 2};

bool ok(int x, int y) {
    return (x >= 0) && (x < n) && (y >= 0) && (y < m);
}

void solve(int x, int y) {
    queue<pair<int, int> > q;
    q.push(make_pair(x, y));
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for (int i = 0; i < 8; i++) {
            int x1 = x + dx[i];
            int y1 = y + dy[i];
            if (ok(x1, y1) && a[x1][y1] == 0) {
                a[x1][y1] = a[x][y] + 1;
                q.push(make_pair(x1, y1));
            }
        }
    }
}

int main() {
    n = 8;
    m = 8;
    int x, y, x1, y1;
    cin >> x >> y >> x1 >> y1;
    a[x][y] = 1;
    solve(x, y);

    for (int i = 0; i < n; i++) {
        for (int j = 0;j < m; j++) 
            cout << a[i][j] << " ";
        cout << endl;
    }
    cout << a[x1][y1] - 1;
    return 0;
}

0 0 7 7

1 4 3 4 3 4 5 6
4 5 2 3 4 5 4 5
3 2 5 4 3 4 5 6
4 3 4 3 4 5 4 5
3 4 3 4 5 4 5 6
4 5 4 5 4 5 6 5
5 4 5 4 5 6 5 6
6 5 6 5 6 5 6 7
6

From one corner to the opposite one takes 6 moves.

Time

Space

• Queue: O(V) in the worst case
• Visited array: O(V)
• Total: O(V)

Side by side

Q1 · When should I use an adjacency list and when a matrix?

• Adjacency list: sparse graphs (few edges), most graph algorithms
• Adjacency matrix: dense graphs, when you need O(1) edge lookup

Q2 · Why does BFS find the shortest path?

BFS explores vertices level by level. It visits all vertices at distance k before any vertex at distance k + 1. Therefore the first time it reaches a vertex is guaranteed to be via a shortest path.

Q3 · Can BFS work on weighted graphs?

BFS finds the shortest path in terms of the number of edges. For weighted graphs use Dijkstra's algorithm or Bellman–Ford instead.

Q4 · What is the difference between BFS and level order traversal?

They are essentially the same. Level order traversal is BFS that explicitly tracks the levels.

Q5 · How do I handle disconnected graphs in BFS?

Run BFS from each unvisited vertex to explore all components.

Graphs and BFS — eight things to remember

1. Graphs represent relationships — vertices and edges
2. Many types of graphs — directed, undirected, weighted, cyclic, etc.
3. Three main representations — adjacency matrix, adjacency list, edge list
4. The adjacency list is the most common — space efficient for sparse graphs
5. BFS uses a queue — explores level by level
6. BFS finds shortest paths — in unweighted graphs
7. BFS complexity is O(V + E) — with an adjacency list
8. BFS has many applications — shortest path, connectivity, bipartite check

Graphs and BFS — try these

1. Implement all three graph representations
2. Find the shortest path using BFS
3. Check if a graph is connected
4. Count connected components
5. Check if a graph is bipartite
6. Find the distance between two vertices
7. Print all vertices at distance k from the source
8. Find if a path exists between two vertices
9. Find the diameter of a graph (the longest shortest path)
10. Clone a graph using BFS

DFS vs BFS

DFS visualization

Graph:

        0
       / \
      1   2
     / \   \
    3   4   5

DFS starting from vertex 0:

Visit order: 0 → 1 → 3 → 4 → 2 → 5

Path taken:
1. Start at 0
2. Go to 1
3. Go to 3
4. Backtrack to 1
5. Go to 4
6. Backtrack to 0
7. Go to 2
8. Go to 5

Recursive implementation

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
int n;

void DFS(int v) {
    // Mark current vertex as visited
    visited[v] = true;
    cout << v << " ";

    // Visit all neighbors
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (!visited[u]) {
            DFS(u);
        }
    }
}

int main() {
    n = 6;

    // Initialize visited array
    for (int i = 0; i < n; i++)
        visited[i] = false;

    // Add edges
    adj[0].push_back(1);
    adj[1].push_back(0);

    adj[0].push_back(2);
    adj[2].push_back(0);

    adj[1].push_back(3);
    adj[3].push_back(1);

    adj[1].push_back(4);
    adj[4].push_back(1);

    adj[2].push_back(5);
    adj[5].push_back(2);

    cout << "DFS traversal: ";
    DFS(0);
    cout << endl;

    return 0;
}

DFS traversal: 0 1 3 4 2 5

Another version · recursive and iterative

The same graph read from input, and the traversal written both ways. The iterative one marks a vertex when it is popped, so a vertex can sit on the stack twice — the if (visited[v]) continue; line handles that.

void DFS_iterative(int start) {
    stack<int> s;

    for (int i = 0; i < n; i++)
        visited[i] = false;

    s.push(start);

    while (!s.empty()) {
        int v = s.top();
        s.pop();

        if (visited[v])
            continue;

        visited[v] = true;
        cout << v + 1 << " ";   // +1: back to the numbering of the input

        for (int i = adj[v].size() - 1; i >= 0; i--) {
            int u = adj[v][i];
            if (!visited[u]) {
                s.push(u);
            }
        }
    }
}

// Basic DFS implementation - recursive and iterative
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
int n, m;

void DFS_recursive(int v) {
    visited[v] = true;
    cout << v + 1 << " ";   // +1: back to the numbering of the input

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (!visited[u]) {
            DFS_recursive(u);
        }
    }
}

void DFS_iterative(int start) {
    stack<int> s;

    for (int i = 0; i < n; i++)
        visited[i] = false;

    s.push(start);

    while (!s.empty()) {
        int v = s.top();
        s.pop();

        if (visited[v])
            continue;

        visited[v] = true;
        cout << v + 1 << " ";   // +1: back to the numbering of the input

        for (int i = adj[v].size() - 1; i >= 0; i--) {
            int u = adj[v][i];
            if (!visited[u]) {
                s.push(u);
            }
        }
    }
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    // Initialize visited
    for (int i = 0; i < n; i++)
        visited[i] = false;

    cout << "DFS recursive: ";
    DFS_recursive(0);
    cout << endl;

    cout << "DFS iterative: ";
    DFS_iterative(0);
    cout << endl;

    return 0;
}

7 7
1 2
1 3
2 4
2 5
3 6
4 7
5 7

DFS recursive: 1 2 4 7 5 3 6
DFS iterative: 1 2 4 7 5 3 6

DFS from vertex 0

Graph:

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

Initial:
  visited = [false, false, false, false, false]
  stack (call stack) = []

Step 1: Visit 0
  visited = [true, false, false, false, false]
  Output: 0
  Neighbors of 0: [1, 2]
  Call DFS(1)

Step 2: Visit 1
  visited = [true, true, false, false, false]
  Output: 0 1
  Neighbors of 1: [0, 3, 4]
  0 is visited, skip
  Call DFS(3)

Step 3: Visit 3
  visited = [true, true, false, true, false]
  Output: 0 1 3
  Neighbors of 3: [1]
  1 is visited, return

Step 4: Back to 1, next neighbor is 4
  Call DFS(4)

Step 5: Visit 4
  visited = [true, true, false, true, true]
  Output: 0 1 3 4
  Neighbors of 4: [1, 2]
  1 is visited, skip
  Call DFS(2)

Step 6: Visit 2
  visited = [true, true, true, true, true]
  Output: 0 1 3 4 2
  Neighbors of 2: [0, 4]
  all visited, return

Final output: 0 1 3 4 2

Counting components

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
int n;

void DFS(int v) {
    visited[v] = true;
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (!visited[u]) {
            DFS(u);
        }
    }
}

int countComponents() {
    // Initialize visited array
    for (int i = 0; i < n; i++)
        visited[i] = false;

    int components = 0;

    // Try to start DFS from each unvisited vertex
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            DFS(i);
            components++;
        }
    }

    return components;
}

int main() {
    n = 7;

    // Component 1: 0-1-2
    adj[0].push_back(1);
    adj[1].push_back(0);

    adj[1].push_back(2);
    adj[2].push_back(1);

    // Component 2: 3-4
    adj[3].push_back(4);
    adj[4].push_back(3);

    // Component 3: 5-6
    adj[5].push_back(6);
    adj[6].push_back(5);

    cout << "Number of connected components: " << countComponents() << endl;

    return 0;
}

Number of connected components: 3

Example

Graph:
    0 --- 1 --- 2     3 --- 4     5 --- 6

Component 1: {0, 1, 2}
Component 2: {3, 4}
Component 3: {5, 6}

Output: 3 components

Another version · from input

// Count connected components using DFS
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
int n, m;

void DFS(int v) {
    visited[v] = true;

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (!visited[u]) {
            DFS(u);
        }
    }
}

int countComponents() {
    for (int i = 0; i < n; i++)
        visited[i] = false;

    int components = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            DFS(i);
            components++;
        }
    }

    return components;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    cout << countComponents() << endl;

    return 0;
}

7 4
1 2
2 3
4 5
6 7

3

Another version · counting islands on a grid

An island is a group of 1s connected horizontally or vertically — a connected component of the grid. Same loop, the four directions instead of an adjacency list.

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

void DFS(int x, int y) {
    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (isValid(nx, ny) && !visited[nx][ny] && grid[nx][ny] == 1) {
            DFS(nx, ny);
        }
    }
}

// Count number of islands in 2D grid using DFS
// An island is a group of connected 1s (horizontally or vertically)
#include <iostream>

using namespace std;

const int MAXN = 100;
int grid[MAXN][MAXN];
bool visited[MAXN][MAXN];
int n, m;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

void DFS(int x, int y) {
    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (isValid(nx, ny) && !visited[nx][ny] && grid[nx][ny] == 1) {
            DFS(nx, ny);
        }
    }
}

int countIslands() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            visited[i][j] = false;

    int islands = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                DFS(i, j);
                islands++;
            }
        }
    }

    return islands;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    cout << countIslands() << endl;

    return 0;
}

5 5
1 1 0 0 0
1 1 0 0 1
0 0 0 1 1
0 0 0 0 0
1 0 1 0 1

5

Two colours by DFS

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
int color[MAXN];  // 0 = uncolored, 1 = color1, 2 = color2
int n;

bool DFS_bipartite(int v, int c) {
    color[v] = c;

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];

        if (color[u] == 0) {
            // Not colored yet, color with opposite color
            if (!DFS_bipartite(u, 3 - c))  // 3-1=2, 3-2=1
                return false;
        }
        else if (color[u] == c) {
            // Same color as current vertex - not bipartite
            return false;
        }
    }

    return true;
}

bool isBipartite() {
    // Initialize color array
    for (int i = 0; i < n; i++)
        color[i] = 0;

    // Check all components
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            if (!DFS_bipartite(i, 1))
                return false;
        }
    }

    return true;
}

int main() {
    // Example 1: Bipartite graph
    n = 4;
    adj[0].push_back(1);
    adj[1].push_back(0);

    adj[0].push_back(3);
    adj[3].push_back(0);

    adj[2].push_back(1);
    adj[1].push_back(2);

    adj[2].push_back(3);
    adj[3].push_back(2);

    cout << "Graph 1 is ";
    if (isBipartite())
        cout << "bipartite" << endl;
    else
        cout << "NOT bipartite" << endl;

    // Example 2: Not bipartite (triangle)
    for (int i = 0; i < MAXN; i++)
        adj[i].clear();

    n = 3;
    adj[0].push_back(1);
    adj[1].push_back(0);

    adj[1].push_back(2);
    adj[2].push_back(1);

    adj[2].push_back(0);
    adj[0].push_back(2);

    cout << "Graph 2 (triangle) is ";
    if (isBipartite())
        cout << "bipartite" << endl;
    else
        cout << "NOT bipartite" << endl;

    return 0;
}

Graph 1 is bipartite
Graph 2 (triangle) is NOT bipartite

Key idea

• Try to colour the graph with 2 colours using DFS
• If the whole graph can be coloured without conflicts, it is bipartite
• If two adjacent vertices get the same colour, it is NOT bipartite

Another version · from input

// Check if graph is bipartite using DFS
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
int color[MAXN];
int n, m;

bool DFS_bipartite(int v, int c) {
    color[v] = c;

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];

        if (color[u] == 0) {
            if (!DFS_bipartite(u, 3 - c))
                return false;
        }
        else if (color[u] == c) {
            return false;
        }
    }

    return true;
}

bool isBipartite() {
    for (int i = 0; i < n; i++)
        color[i] = 0;

    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            if (!DFS_bipartite(i, 1))
                return false;
        }
    }

    return true;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    if (isBipartite())
        cout << "YES" << endl;
    else
        cout << "NO" << endl;

    return 0;
}

4 4
1 2
1 4
2 3
3 4

YES

Cycle detection in an undirected graph

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
int n;

bool DFS_cycle(int v, int parent) {
    visited[v] = true;

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];

        if (!visited[u]) {
            if (DFS_cycle(u, v))
                return true;
        }
        else if (u != parent) {
            // Visited vertex that is not parent = cycle found
            return true;
        }
    }

    return false;
}

bool hasCycle() {
    // Initialize visited array
    for (int i = 0; i < n; i++)
        visited[i] = false;

    // Check all components
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (DFS_cycle(i, -1))
                return true;
        }
    }

    return false;
}

int main() {
    // Example 1: Graph with cycle
    n = 4;
    adj[0].push_back(1);
    adj[1].push_back(0);

    adj[1].push_back(2);
    adj[2].push_back(1);

    adj[2].push_back(3);
    adj[3].push_back(2);

    adj[3].push_back(0);
    adj[0].push_back(3);

    cout << "Graph ";
    if (hasCycle())
        cout << "has a cycle" << endl;
    else
        cout << "does NOT have a cycle" << endl;

    return 0;
}

Graph has a cycle

Cycle detection in a directed graph

For directed graphs we track the vertices on the current path:

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
bool recStack[MAXN];  // Vertices in current recursion stack
int n;

bool DFS_cycle_directed(int v) {
    visited[v] = true;
    recStack[v] = true;

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];

        if (!visited[u]) {
            if (DFS_cycle_directed(u))
                return true;
        }
        else if (recStack[u]) {
            // Found back edge to vertex in current path
            return true;
        }
    }

    recStack[v] = false;
    return false;
}

bool hasCycleDirected() {
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        recStack[i] = false;
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (DFS_cycle_directed(i))
                return true;
        }
    }

    return false;
}

int main() {
    n = 4;

    // Directed edges
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[2].push_back(3);
    adj[3].push_back(1);  // Creates cycle: 1 -> 2 -> 3 -> 1

    cout << "Directed graph ";
    if (hasCycleDirected())
        cout << "has a cycle" << endl;
    else
        cout << "does NOT have a cycle" << endl;

    return 0;
}

Directed graph has a cycle

Another version · from input

Undirected:

// Cycle detection in undirected graph using DFS
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
int n, m;

bool DFS_cycle(int v, int parent) {
    visited[v] = true;

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];

        if (!visited[u]) {
            if (DFS_cycle(u, v))
                return true;
        }
        else if (u != parent) {
            return true;
        }
    }

    return false;
}

bool hasCycle() {
    for (int i = 0; i < n; i++)
        visited[i] = false;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (DFS_cycle(i, -1))
                return true;
        }
    }

    return false;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    if (hasCycle())
        cout << "Cycle found" << endl;
    else
        cout << "No cycle" << endl;

    return 0;
}

7 7
1 2
1 3
2 4
2 5
3 6
4 7
5 7

Cycle found

Directed — on a DAG, so the answer is "no cycle":

// Cycle detection in directed graph using DFS
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
bool recStack[MAXN];
int n, m;

bool DFS_cycle_directed(int v) {
    visited[v] = true;
    recStack[v] = true;

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];

        if (!visited[u]) {
            if (DFS_cycle_directed(u))
                return true;
        }
        else if (recStack[u]) {
            return true;
        }
    }

    recStack[v] = false;
    return false;
}

bool hasCycleDirected() {
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        recStack[i] = false;
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (DFS_cycle_directed(i))
                return true;
        }
    }

    return false;
}

int main() {
    cin >> n >> m;

    // Directed edges
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
    }

    if (hasCycleDirected())
        cout << "Cycle found" << endl;
    else
        cout << "No cycle (DAG)" << endl;

    return 0;
}

6 6
6 3
6 1
5 1
5 2
3 4
4 2

No cycle (DAG)

Applications of topological sort

• Task scheduling with dependencies
• Course prerequisites
• Build systems (compile order)
• Package dependency resolution

Example

Task dependencies:
A → B (A must be done before B)
A → C
B → D
C → D

One valid topological order: A, B, C, D
Another valid order: A, C, B, D

DFS-based topological sort

Key idea: use DFS and add a vertex to the result when all its descendants are processed (post-order).

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
stack<int> result;
int n;

void DFS_topo(int v) {
    visited[v] = true;

    // Visit all neighbors first
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (!visited[u]) {
            DFS_topo(u);
        }
    }

    // Add current vertex to stack after visiting all descendants
    result.push(v);
}

void topologicalSort() {
    // Initialize
    for (int i = 0; i < n; i++)
        visited[i] = false;

    // Process all vertices
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            DFS_topo(i);
        }
    }

    // Print result
    cout << "Topological order: ";
    while (!result.empty()) {
        cout << result.top() << " ";
        result.pop();
    }
    cout << endl;
}

int main() {
    n = 6;

    // DAG example
    adj[5].push_back(2);
    adj[5].push_back(0);
    adj[4].push_back(0);
    adj[4].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(1);

    cout << "Graph (directed):" << endl;
    cout << "5 -> 2, 0" << endl;
    cout << "4 -> 0, 1" << endl;
    cout << "2 -> 3" << endl;
    cout << "3 -> 1" << endl;
    cout << endl;

    topologicalSort();

    return 0;
}

Graph (directed):
5 -> 2, 0
4 -> 0, 1
2 -> 3
3 -> 1

Topological order: 5 4 2 3 1 0

Output: 5 4 2 3 1 0 — one possible topological order.

Topological sort algorithm steps

1. Initialize all vertices as unvisited
2. For each unvisited vertex v:
   a. Call DFS(v)
   b. In DFS, visit all descendants first (recursively)
   c. After visiting all descendants, push v to stack
3. The stack contains topological order (top to bottom)

Important notes

• Topological sort only works on Directed Acyclic Graphs (DAG)
• If the graph has a cycle, topological sort is not possible
• There can be multiple valid topological orderings
• Time complexity: O(V + E)

Another version · from input

The same DAG, vertices numbered from 1 — the order is printed with + 1.

// Topological sort using DFS
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
stack<int> result;
int n, m;

void DFS_topo(int v) {
    visited[v] = true;

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (!visited[u]) {
            DFS_topo(u);
        }
    }

    result.push(v);
}

void topologicalSort() {
    for (int i = 0; i < n; i++)
        visited[i] = false;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            DFS_topo(i);
        }
    }

    while (!result.empty()) {
        cout << result.top() + 1 << " ";
        result.pop();
    }
    cout << endl;
}

int main() {
    cin >> n >> m;

    // Directed graph
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
    }

    topologicalSort();

    return 0;
}

6 6
6 3
6 1
5 1
5 2
3 4
4 2

6 5 3 4 2 1

Find if a path exists

bool DFS_path(int v, int target);   // added: declared before hasPath uses it

bool hasPath(int start, int end) {
    // Initialize visited array
    for (int i = 0; i < n; i++)
        visited[i] = false;

    return DFS_path(start, end);
}

bool DFS_path(int v, int target) {
    if (v == target)
        return true;

    visited[v] = true;

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (!visited[u]) {
            if (DFS_path(u, target))
                return true;
        }
    }

    return false;
}

Find and print the path

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
vector<int> path;
int n;

bool DFS_printPath(int v, int target) {
    visited[v] = true;
    path.push_back(v);

    if (v == target) {
        return true;
    }

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (!visited[u]) {
            if (DFS_printPath(u, target))
                return true;
        }
    }

    // Backtrack
    path.pop_back();
    return false;
}

void findPath(int start, int end) {
    for (int i = 0; i < n; i++)
        visited[i] = false;

    path.clear();

    if (DFS_printPath(start, end)) {
        cout << "Path from " << start << " to " << end << ": ";
        for (int i = 0; i < path.size(); i++) {
            cout << path[i];
            if (i < path.size() - 1)
                cout << " -> ";
        }
        cout << endl;
    } else {
        cout << "No path exists" << endl;
    }
}

int main() {
    n = 6;

    // Add edges
    adj[0].push_back(1);
    adj[1].push_back(0);
    adj[0].push_back(2);
    adj[2].push_back(0);
    adj[1].push_back(3);
    adj[3].push_back(1);
    adj[1].push_back(4);
    adj[4].push_back(1);
    adj[2].push_back(5);
    adj[5].push_back(2);

    findPath(0, 5);
    findPath(3, 5);

    return 0;
}

Path from 0 to 5: 0 -> 2 -> 5
Path from 3 to 5: 3 -> 1 -> 0 -> 2 -> 5

Another version · from input

The graph from the DFS example, path from 4 to 6.

// Find path between two vertices using DFS
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
vector<int> path;
int n, m;

bool DFS_path(int v, int target) {
    visited[v] = true;
    path.push_back(v);

    if (v == target) {
        return true;
    }

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (!visited[u]) {
            if (DFS_path(u, target))
                return true;
        }
    }

    path.pop_back();
    return false;
}

void findPath(int start, int end) {
    for (int i = 0; i < n; i++)
        visited[i] = false;

    path.clear();

    if (DFS_path(start, end)) {
        cout << "Path: ";
        for (int i = 0; i < path.size(); i++) {
            cout << path[i] + 1;
            if (i < path.size() - 1)
                cout << " -> ";
        }
        cout << endl;
    } else {
        cout << "No path" << endl;
    }
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    int start, end;
    cin >> start >> end;
    start--; end--;

    findPath(start, end);

    return 0;
}

7 7
1 2
1 3
2 4
2 5
3 6
4 7
5 7
4 6

Path: 4 -> 2 -> 1 -> 3 -> 6

Kosaraju's algorithm

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
vector<int> adj_rev[MAXN];  // Reversed graph
bool visited[MAXN];
stack<int> finishOrder;
int n;

void DFS1(int v) {
    visited[v] = true;

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (!visited[u])
            DFS1(u);
    }

    finishOrder.push(v);
}

void DFS2(int v, vector<int>& component) {
    visited[v] = true;
    component.push_back(v);

    for (int i = 0; i < adj_rev[v].size(); i++) {
        int u = adj_rev[v][i];
        if (!visited[u])
            DFS2(u, component);
    }
}

void findSCC() {
    // Step 1: Do DFS and fill finish order
    for (int i = 0; i < n; i++)
        visited[i] = false;

    for (int i = 0; i < n; i++) {
        if (!visited[i])
            DFS1(i);
    }

    // Step 2: Do DFS on reversed graph in order of finish time
    for (int i = 0; i < n; i++)
        visited[i] = false;

    int sccCount = 0;
    while (!finishOrder.empty()) {
        int v = finishOrder.top();
        finishOrder.pop();

        if (!visited[v]) {
            vector<int> component;
            DFS2(v, component);

            sccCount++;
            cout << "SCC " << sccCount << ": ";
            for (int i = 0; i < component.size(); i++) {
                cout << component[i] << " ";
            }
            cout << endl;
        }
    }
}

int main() {
    n = 5;

    // Add directed edges
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[2].push_back(0);
    adj[1].push_back(3);
    adj[3].push_back(4);

    // Create reversed graph
    for (int v = 0; v < n; v++) {
        for (int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i];
            adj_rev[u].push_back(v);
        }
    }

    findSCC();

    return 0;
}

SCC 1: 0 2 1
SCC 2: 3
SCC 3: 4

0 → 1 → 2 → 0 is a cycle, so {0, 1, 2} is one component; 3 and 4 are reachable from it but cannot get back, so each is a component on its own.

Bridge (cut edge)

An edge whose removal increases the number of connected components.

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];
int disc[MAXN];  // Discovery time
int low[MAXN];   // Lowest discovery time reachable
int timer = 0;
int n;

void DFS_bridge(int v, int parent) {
    visited[v] = true;
    disc[v] = low[v] = timer++;

    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];

        if (u == parent)
            continue;

        if (visited[u]) {
            low[v] = min(low[v], disc[u]);
        } else {
            DFS_bridge(u, v);
            low[v] = min(low[v], low[u]);

            // If lowest reachable from u is higher than disc[v],
            // then v-u is a bridge
            if (low[u] > disc[v]) {
                cout << "Bridge: " << v << " - " << u << endl;
            }
        }
    }
}

void findBridges() {
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        disc[i] = -1;
        low[i] = -1;
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i])
            DFS_bridge(i, -1);
    }
}

int main() {
    n = 5;

    adj[0].push_back(1);
    adj[1].push_back(0);

    adj[1].push_back(2);
    adj[2].push_back(1);

    adj[2].push_back(0);
    adj[0].push_back(2);

    adj[1].push_back(3);
    adj[3].push_back(1);

    adj[3].push_back(4);
    adj[4].push_back(3);

    findBridges();

    return 0;
}

Bridge: 3 - 4
Bridge: 1 - 3

The triangle 0 — 1 — 2 has no bridges: removing any one of its edges leaves the other two. The edges 1 — 3 and 3 — 4 are both bridges.

Time

Space

• Recursive: O(V) for the recursion stack + O(V) for the visited array = O(V)
• Iterative: O(V) for the explicit stack + O(V) for the visited array = O(V)

Everything above, one line each

DFS — seven things to remember

1. DFS explores depth-first using a stack or recursion
2. DFS is versatile — many graph problems are solved with it
3. Topological sort is done with DFS on a DAG
4. Cycle detection is different for directed and undirected graphs
5. The bipartite check can be done with DFS or BFS
6. DFS complexity is O(V + E) with an adjacency list
7. DFS is perfect for path finding, cycle detection and topological sorting

DFS — try these

1. Implement DFS recursively and iteratively
2. Count connected components using DFS
3. Check if a graph is bipartite
4. Detect a cycle in an undirected graph
5. Detect a cycle in a directed graph
6. Implement topological sort
7. Find all paths between two vertices
8. Find bridges in a graph
9. Find articulation points
10. Check if a directed graph is a DAG
11. Find strongly connected components (Kosaraju's algorithm)
12. Find the number of islands (2D grid DFS)
13. Solve a maze using DFS
14. Clone a graph
15. Find if there is a path with a given sum in a tree

Problem to topic