logo
logo

Overview

Course Introduction

Strings and Arrays

Reverse Words In A String

Rotate Array

Isomorphic Strings

Kth Largest Element In An Array

Matrix Problems

Set Matrix Zero

Spiral Matrix

Number Of Islands

Linked Lists

Implement A Stack Using An Array

Add Two Numbers As Reversed Linked Lists

Reverse A Linked List

Binary Trees

Inorder Traversal

Preorder Traversal

Postorder Traversal

Graph Problems

Clone a Graph: Build a Graph

Clone a Graph: Build a Queue

Clone a Graph: Breadth First Traversal (BFS)

Clone a Graph: Depth First Search (DFS)

Sorting & Time Complexities

Time Complexities (Bad)

Time Complexities (Good)

Bubble Sort

Selection Sort

Insertion Sort

Quicksort

Merge Sort

Time Complexity Of Different Sorting Algorithms

Dynamic Programming

Coin Change

Edit Distance

Distinct Subsequences

Bit Manipulation

Bitwise And Shift Operators

Single Number

Number Of 1 Bits

Sum of Two Integers

Maximum Sum Subarray

Reverse Bits

Bitwise And Of A Range

Combinations & Permutations

Permutations

Distinct Permutations Of A String

Letter Combinations Of A Phone Number

Factor Combinations

Math Problems

Reverse Integer

Palindrome Number

Excel Sheet Column Number

Clone a Graph: Breadth First Traversal (BFS)

Lesson

Implement a breadth-first traversal function for an undirected graph in JavaScript. Given a graph and a starting node, the function should traverse the graph in a breadth-first manner, copying each visited node along the way. The function should return an array of all the visited nodes.

Example:

1const graph = {
2  vertices: 4,
3  adjacentList: {
4    a: ['b', 'c'],
5    b: ['a', 'd'],
6    c: ['a', 'd'],
7    d: ['b', 'c']
8  }
9};
10
11breadthFirstTraversal(graph, 'a');
12
13// ['a', 'b', 'c', 'd']

Walkthrough

To implement a breadth-first traversal function for an undirected graph, we will use a queue to keep track of the unvisited nodes. We will initialize a visited array, which will store the nodes that we have already visited. We will start at the given starting node and add it to the queue. We will then enter a loop that continues as long as the queue is not empty. During each iteration, we will dequeue the next node from the queue and mark it as visited. We will then add all its unvisited neighbors to the queue, one by one.

Here is the implementation:

1function breadthFirstTraversal(graph, startingNode) {
2  const visitedNodes = [];
3  const queue = [];
4
5  // Mark all nodes as unvisited
6  for (let i = 0; i < graph.vertices; i++) {
7    visitedNodes[i] = false;
8  }
9
10  // Add the starting node to the queue and mark it as visited
11  queue.push(startingNode);
12  visitedNodes[startingNode] = true;
13
14  while (queue.length > 0) {
15    // Dequeue a node from the queue and add it to the visited array
16    const currentNode = queue.shift();
17    visitedNodes.push(currentNode);
18
19    // Get all unvisited neighbors of the current node and add them to the queue
20    const neighbors = graph.adjacentList[currentNode];
21    for (let i = 0; i < neighbors.length; i++) {
22      const neighbor = neighbors[i];
23      if (!visitedNodes[neighbor]) {
24        visitedNodes[neighbor] = true;
25        queue.push(neighbor);
26      }
27    }
28  }
29
30  return visitedNodes;
31}

Big O Complexity Analysis:

The time complexity of the algorithm is O(V+E), which is the same as the time complexity of BFS on a graph. We visit each vertex and each edge exactly once, which takes O(V+E) time.

The space complexity of the algorithm is also O(V+E), since we need to store the visited array and the queue. The visited array takes O(V) space, while the queue takes O(E) space in the worst case, where E is the number of edges in the graph. Therefore, the total space complexity is O(V+E).