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

Graph Traversals

Explore how to systematically visit all nodes in a graph using breadth-first search and depth-first search. Learn JavaScript implementations, analyze time and space complexities, and discover when to apply each traversal method in graph-related problems.

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 JavaScript implementation of BFS:

Javascript (babel-node)
// Graph class using adjacency list
class Graph {
    constructor() {
        this.graph = {}; // Adjacency list
    }
    addEdge(u, v) {
        // Initialize nodes if not present
        if (!this.graph[u]) {
            this.graph[u] = [];
        }
        if (!this.graph[v]) {
            this.graph[v] = [];
        }
        this.graph[u].push(v);
        this.graph[v].push(u); // Remove for directed graph
    }
    bfs(start) {
        const visited = new Set();
        const queue = [start];
        visited.add(start); // Mark start node as visited
        while (queue.length > 0) {
            const vertex = queue.shift(); // Get next node
            process.stdout.write(vertex + " ");
            for (const neighbor of this.graph[vertex]) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor); // Mark neighbor visited
                    queue.push(neighbor);  // Add neighbor to queue
                }
            }
        }
    }
}
function main() {
    const g = new Graph();
    // 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");
}
main();
Graph BFS

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