Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in C++

Graph Traversals

Explore how to systematically visit all nodes in a graph using breadth-first search and depth-first search in C++. Learn their algorithms, implementations, time and space complexities, and practical applications like shortest path finding and cycle detection.

We'll cover the following...

Graph traversal is the process of visiting all vertices (nodes) in a graph systematically. It is a fundamental concept because many graph algorithms rely on efficient graph exploration.

The two most common graph traversal techniques are:

  • Breadth-first search (BFS)

  • Depth-first search (DFS)

Breadth-first search (BFS)

Breadth-First Search explores a graph level by level. Starting from a chosen node, it first visits all immediate neighbors before moving to nodes at the next level.

Key idea

BFS uses a queue (FIFO: first in, first out).

How BFS works

  1. Start from a chosen node.

  2. Mark it as visited.

  3. Add it to a queue.

  4. While the queue is not empty:

    1. Dequeue a node.

    2. Visit all its unvisited neighbors.

    3. Mark them as visited and add them to the queue.

Below is the C++ implementation of BFS:

C++ 17
#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
class Graph {
public:
    unordered_map<string, vector<string>> graph; // Adjacency list
    void addEdge(string u, string v) {
        // Initialize nodes if not present
        if (graph.find(u) == graph.end()) {
            graph[u] = {};
        }
        if (graph.find(v) == graph.end()) {
            graph[v] = {};
        }
        graph[u].push_back(v);
        graph[v].push_back(u); // Remove for directed graph
    }
    void bfs(string start) {
        unordered_set<string> visited;
        queue<string> q;
        q.push(start);
        visited.insert(start); // Mark start node as visited
        while (!q.empty()) {
            string vertex = q.front();
            q.pop();
            // Get next node
            cout << vertex << " ";
            for (string neighbor : graph[vertex]) {
                if (visited.find(neighbor) == visited.end()) {
                    visited.insert(neighbor); // Mark neighbor visited
                    q.push(neighbor);         // Add neighbor to queue
                }
            }
        }
    }
};
int main() {
    Graph g;
    // Build graph
    g.addEdge("A", "B");
    g.addEdge("A", "C");
    g.addEdge("B", "D");
    g.addEdge("B", "E");
    g.addEdge("C", "F");
    // Run BFS
    g.bfs("A");
    return 0;
}
Graph BFS

Time complexity:
The time complexity of BFS is ...