JavaScript Coding Test Course, DFS and BFS Program

Problem Description

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.

Problem

Input:
- n: number of vertices (1 ≤ n ≤ 10^4)
- edges: list of edges (undirected)
- start: starting vertex
- end: ending vertex

Output:
- List of edges that form the shortest path from start to end
            

Example

Input: n = 5, edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]], start = 1, end = 5

Output: [1, 2, 4, 5] or [1, 3, 4, 5]

Theory

DFS (Depth-First Search)

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.

BFS (Breadth-First Search)

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.

Solution

Step 1: Build the Graph

First, let’s build the graph using an adjacency list.

function buildGraph(n, edges) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u); // Since it's an undirected graph, add both ways
    }
    return graph;
}

const n = 5;
const edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]];
const graph = buildGraph(n, edges);
console.log(graph);
            

Step 2: Implement BFS

Now, let’s find the shortest path from the starting vertex to the ending vertex using BFS.

function bfs(graph, start, end) {
    const queue = [[start]];
    const visited = new Set([start]);

    while (queue.length > 0) {
        const path = queue.shift();
        const node = path[path.length - 1];

        if (node === end) {
            return path; // Return the shortest path found
        }

        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push([...path, neighbor]); // Add neighboring node to current path
            }
        }
    }
    return []; // Return empty array if no path found
}

const start = 1,
      end = 5;

const result = bfs(graph, start, end);
console.log(result);
            

Step 3: Implement DFS

Now, let’s use DFS to check the existence of a path and how to find that path.

function dfs(graph, start, end, visited = new Set(), path = []) {
    visited.add(start);
    path.push(start);
    
    if (start === end) {
        return path; // Return when the path is found
    }

    for (const neighbor of graph[start]) {
        if (!visited.has(neighbor)) {
            const resultPath = dfs(graph, neighbor, end, visited, [...path]);
            if (resultPath.length > 0) {
                return resultPath; // Return when a path is discovered
            }
        }
    }
    return []; // Return empty array if no path found
}

const dfsResult = dfs(graph, start, end);
console.log(dfsResult);