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

Graph Traversals

Explore graph traversal methods such as breadth-first search (BFS) and depth-first search (DFS) using JavaScript. Learn how BFS explores nodes level by level while DFS explores deeply along paths. Understand their implementations, time and space complexities, and practical applications like shortest path 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 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 ...