1. Problem Statement
Breadth-First Search (BFS) is one of the search algorithms commonly used in graphs or tree structures. In this tutorial, we will use BFS to solve the “Shortest Path Finding” problem.
Problem: Find the Shortest Path
Write a function to find the shortest path between two nodes in the given graph. The graph is provided in the form of an adjacency list, and the nodes are represented as strings.
Input Format
graph: {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}
start: "A"
end: "F"
Output Format
["A", "C", "F"]
2. Problem Analysis
The reason we use BFS to find the shortest path is that BFS explores all neighboring nodes at once, guaranteeing the fastest path. Unlike DFS (Depth-First Search), BFS explores all nodes connected to the current node first before moving to the next level. This characteristic makes BFS suitable for shortest path searches.
3. Algorithm Design
Below is the basic flow of the shortest path finding algorithm using BFS:
- Add the starting node to the queue and mark it as visited.
- Remove a node from the queue and check all its neighbor nodes.
- Add any unvisited neighbor nodes to the queue and set the parent of that node to the current node.
- Repeat steps 2-3 until the ending node is found.
- When reaching the end node, backtrack through the parent nodes to construct the shortest path.
4. Code Implementation
Below is the implementation code for the shortest path finding function using BFS:
function findShortestPath(graph, start, end) {
// Object for queue and marking visited nodes
let queue = [start];
let visited = {};
let parent = {};
visited[start] = true;
parent[start] = null;
while (queue.length > 0) {
let currentNode = queue.shift(); // Remove node from queue
// If the end node is reached
if (currentNode === end) {
return reconstructPath(parent, start, end);
}
// Explore the neighbors of the current node
for (let neighbor of graph[currentNode]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
parent[neighbor] = currentNode; // Set the current node as the parent of the neighbor
queue.push(neighbor); // Add the neighbor to the queue
}
}
}
return []; // Return empty array if there is no path
}
function reconstructPath(parent, start, end) {
let path = [];
let current = end;
while (current !== null) {
path.push(current);
current = parent[current];
}
return path.reverse(); // Return path in reverse order
}
5. Algorithm Analysis
The code above uses BFS to find the shortest path. The time complexity is O(V + E), where V is the number of nodes and E is the number of edges. This algorithm is memory efficient because it utilizes an adjacency list.
6. Time Complexity and Space Complexity Analysis
The time complexity is O(V + E), as all nodes and edges are explored once. The space complexity is also O(V) because arrays for the queue, visited markers, and parent storage are proportional to the number of nodes.
7. Test Cases
Let’s create a few test cases to check the above code.
const graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
};
console.log(findShortestPath(graph, "A", "F")); // Output: ["A", "C", "F"]
console.log(findShortestPath(graph, "B", "F")); // Output: ["B", "E", "F"]
console.log(findShortestPath(graph, "D", "A")); // Output: ["D", "B", "A"]
console.log(findShortestPath(graph, "A", "A")); // Output: ["A"]
8. Conclusion
In this tutorial, we solved the shortest path problem using Breadth-First Search (BFS) with JavaScript. BFS is a useful method for traversing graphs using structures like adjacency lists and can be applied to various problems. Continue practicing algorithms and solving more problems.
9. Additional Resources
If you want to learn more algorithm problems and solutions, try using online coding test platforms. You can enhance your skills through various problems and hints available.