{"id":34420,"date":"2024-11-01T09:27:56","date_gmt":"2024-11-01T09:27:56","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34420"},"modified":"2024-11-01T11:41:20","modified_gmt":"2024-11-01T11:41:20","slug":"javascript-coding-test-course-dfs-and-bfs-program","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34420\/","title":{"rendered":"JavaScript Coding Test Course, DFS and BFS Program"},"content":{"rendered":"

<\/p>\n

\n
\n

Welcome to the blog! Today, we will learn both the theory and practical implementation by solving problems using DFS (Depth-First Search) and BFS (Breadth-First Search) algorithms.<\/p>\n<\/header>\n

\n

Problem Description<\/h2>\n

We will tackle the problem of finding the shortest path to a specific node in a given undirected graph. The graph is provided in the form of an adjacency list, and the shortest path can be found using BFS. DFS can be used to verify the existence of a path rather than finding the shortest path.<\/p>\n

Problem<\/h3>\n
\nInput:\n- n: number of vertices (1 \u2264 n \u2264 10^4)\n- edges: list of edges (undirected)\n- start: starting vertex\n- end: ending vertex\n\nOutput:\n- List of edges that form the shortest path from start to end\n            <\/code><\/pre>\n
Example<\/h3>\n
Input:<\/strong> n = 5<\/code>, edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]]<\/code>, start = 1<\/code>, end = 5<\/code><\/p>\n
Output:<\/strong> [1, 2, 4, 5]<\/code> or [1, 3, 4, 5]<\/code><\/p>\n<\/section>\n
\n
Theory<\/h2>\n
DFS (Depth-First Search)<\/h3>\n
\n                DFS is a method that starts from a node in the graph and explores as far as possible along each branch before backtracking. This algorithm can be implemented recursively or using a stack. The advantage of DFS is its low memory usage, making it useful when deep node exploration is needed.\n            <\/p>\n
BFS (Breadth-First Search)<\/h3>\n
\n                BFS explores all neighboring nodes at the present depth prior to moving on to nodes at the next depth level. It is implemented using a queue and is particularly suitable for finding the shortest path. BFS is very useful in finding the shortest path, ensuring that it exists if a shortest path is available.\n            <\/p>\n<\/section>\n
\n
Solution<\/h2>\n
Step 1: Build the Graph<\/h3>\n
First, let’s build the graph using an adjacency list.<\/p>\n
\nfunction buildGraph(n, edges) {\n    const graph = Array.from({ length: n + 1 }, () => []);\n    for (const [u, v] of edges) {\n        graph[u].push(v);\n        graph[v].push(u); \/\/ Since it's an undirected graph, add both ways\n    }\n    return graph;\n}\n\nconst n = 5;\nconst edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]];\nconst graph = buildGraph(n, edges);\nconsole.log(graph);\n            <\/code><\/pre>\n
Step 2: Implement BFS<\/h3>\n
Now, let’s find the shortest path from the starting vertex to the ending vertex using BFS.<\/p>\n
\nfunction bfs(graph, start, end) {\n    const queue = [[start]];\n    const visited = new Set([start]);\n\n    while (queue.length > 0) {\n        const path = queue.shift();\n        const node = path[path.length - 1];\n\n        if (node === end) {\n            return path; \/\/ Return the shortest path found\n        }\n\n        for (const neighbor of graph[node]) {\n            if (!visited.has(neighbor)) {\n                visited.add(neighbor);\n                queue.push([...path, neighbor]); \/\/ Add neighboring node to current path\n            }\n        }\n    }\n    return []; \/\/ Return empty array if no path found\n}\n\nconst start = 1,\n      end = 5;\n\nconst result = bfs(graph, start, end);\nconsole.log(result);\n            <\/code><\/pre>\n
Step 3: Implement DFS<\/h3>\n
Now, let’s use DFS to check the existence of a path and how to find that path.<\/p>\n
\nfunction dfs(graph, start, end, visited = new Set(), path = []) {\n    visited.add(start);\n    path.push(start);\n    \n    if (start === end) {\n        return path; \/\/ Return when the path is found\n    }\n\n    for (const neighbor of graph[start]) {\n        if (!visited.has(neighbor)) {\n            const resultPath = dfs(graph, neighbor, end, visited, [...path]);\n            if (resultPath.length > 0) {\n                return resultPath; \/\/ Return when a path is discovered\n            }\n        }\n    }\n    return []; \/\/ Return empty array if no path found\n}\n\nconst dfsResult = dfs(graph, start, end);\nconsole.log(dfsResult);\n            <\/code><\/pre>\n<\/section>\n