Grokking 75: Top Coding Interview Questions

0% completed

​

Graph Traversal - Breadth First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph's vertices (nodes) level by level. It starts from a selected source node and moves outward to visit all the nodes at the same distance from the source before moving on to nodes at the following distance level.

BFS is particularly useful for finding the shortest path in unweighted graphs and for systematically exploring graphs.

Step-by-Step Algorithm for BFS

  1. Graph Initialization:
    • Create a graph with V vertices.

.....

.....

.....

Like the course? Get enrolled and start learning!
J

Jimmy

· 2 years ago

In step 6 of the example, you shouldn't enqueue vertex F since it was enqueued in step 4 and vertex F was already marked as visited.

Show 1 reply
Edwin Torres

Edwin Torres

· 2 years ago

For Javascript it looks like you're calling a process.stdout.write

However, it looks like this is an old syntax used by Nodejs or low level, You could replace this line with a simple console.log

class Graph {
    constructor(vertices) {
        this.V = vertices; // Number of vertices
        this.adjList = new Array(vertices).fill(null).map(() => []);
    }

    addEdge(u, v) {
        this.adjList[u].push(v);
        this.adjList[v].push(u); // For undirected graph
    }

    BFS(startVertex) {
        const visited = new Array(this.V).fill(false); // To keep track of visited vertices
        const queue = [];

        visited[startVertex] = true;
        queue.push(startVertex);

        while (queue.length !== 0) {
            const currentVertex = queue.shif
Saumya Kumar

Saumya Kumar

· a year ago

The Data structure should be queue as mentioned in the algorithm not stack