DSA Graph Traversal

DSA Graph Traversal – Complete Beginner Guide

(BFS • DFS • Algorithms • Examples • Code • Complexity)

Graph Traversal means visiting all vertices (nodes) of a graph systematically.
It is a foundation topic for almost every graph algorithm.

1️⃣ What is Graph Traversal?

Graph traversal is the process of:

Visiting each vertex exactly once
Avoiding infinite loops using a visited array

Required because graphs may contain cycles.

2️⃣ Types of Graph Traversal

There are two main traversal algorithms:

Breadth First Search (BFS)
Depth First Search (DFS)

Both are very important for exams & interviews.

3️⃣ Breadth First Search (BFS)

Concept

Visits nodes level by level
Uses a Queue
Explores all neighbors first

Best for shortest path in unweighted graphs.

BFS Algorithm (Steps)

Start from a source node
Mark it as visited
Push it into a queue
While queue is not empty:
- Dequeue node
- Visit all unvisited neighbors
- Mark them visited and enqueue

BFS Example

Graph:

Start from 0

BFS Order

BFS Code (C++)

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

void BFS(int start, vector<int> adj[], int V) {
    vector<bool> visited(V, false);
    queue<int> q;

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

    while(!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

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

#include <queue>

#include <vector>

#include <iostream>

using namespace std;

void BFS(int start, vector<int> adj[], int V) {

vector<bool> visited(V, false);

queue<int> q;

visited[start] = true;

q.push(start);

while(!q.empty()) {

int node = q.front();

q.pop();

cout << node << " ";

for(int x : adj[node]) {

if(!visited[x]) {

visited[x] = true;

q.push(x);

}

4️⃣ Depth First Search (DFS)

Concept

Goes as deep as possible before backtracking
Uses Recursion or Stack

Useful for cycle detection, topological sort.

DFS Algorithm (Steps)

Start from a node
Mark it visited
Visit an unvisited neighbor
Repeat recursively
Backtrack when no unvisited neighbors

DFS Example

Graph:

Start from 0

DFS Order

(order may vary)

DFS Code (C++ – Recursive)

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

void DFS(int node, vector<int> adj[], vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";

    for(int x : adj[node]) {
        if(!visited[x])
            DFS(x, adj, visited);
    }
}

#include <vector>

#include <iostream>

using namespace std;

void DFS(int node, vector<int> adj[], vector<bool>& visited) {

visited[node] = true;

cout << node << " ";

for(int x : adj[node]) {

if(!visited[x])

DFS(x, adj, visited);

}

DFS Code (Iterative – Stack)

#include <stack>

void DFS_Iterative(int start, vector<int> adj[], int V) {
    vector<bool> visited(V, false);
    stack<int> st;

    st.push(start);

    while(!st.empty()) {
        int node = st.top();
        st.pop();

        if(!visited[node]) {
            cout << node << " ";
            visited[node] = true;
        }

        for(int x : adj[node]) {
            if(!visited[x])
                st.push(x);
        }
    }
}

#include <stack>

void DFS_Iterative(int start, vector<int> adj[], int V) {

vector<bool> visited(V, false);

stack<int> st;

st.push(start);

while(!st.empty()) {

int node = st.top();

st.pop();

if(!visited[node]) {

cout << node << " ";

visited[node] = true;

}

for(int x : adj[node]) {

if(!visited[x])

st.push(x);

}

5️⃣ BFS vs DFS

Feature	BFS	DFS
Data Structure	Queue	Stack / Recursion
Traversal	Level-wise	Depth-wise
Shortest Path	✅ Yes	❌ No
Memory	More	Less
Use Case	Unweighted shortest path	Cycle detection

6️⃣ Traversal of Disconnected Graph

If graph is disconnected, start traversal from each unvisited vertex:

Very common interview question.

7️⃣ Time & Space Complexity

Time Complexity

Space Complexity

BFS → O(V)
DFS → O(V)

8️⃣ Real-Life Applications

✔ Google Maps (path finding)
✔ Social networks
✔ Web crawling
✔ Network broadcasting
✔ AI & game maps

Interview Questions (Graph Traversal)

Q1. Which traversal uses queue?
👉 BFS

Q2. Which traversal uses recursion?
👉 DFS

Q3. BFS or DFS for shortest path?
👉 BFS

Q4. Why visited array is needed?
👉 To avoid infinite loops

Final Summary

✔ Graph traversal visits all vertices
✔ Two main methods: BFS & DFS
✔ BFS → Queue, DFS → Stack
✔ Both run in O(V + E)
✔ Foundation for all graph algorithms

DSA Graph Traversal