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)
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).