Shortest pass BFS graph

Question

I can't write the steps of bfs algorithm, please helps advice. I have tried everything for two days.

The function takes as an argument an object representing a non-binary tree (a node can have more than two children) and returns an array of nodes corresponding to a breadth-first traversal. Bypass is carried out from left to right (ascending index in the array).

Example graph:
           A 
         /   \ 
        B     C 
       /  \   / \ 
      D    E F   G

The same in the object:
const graph = {
    A: ['B', 'C'],
    B: ['D', 'E'],
    C: ['F', 'G'],
    D: [],
    E: [],
    F: [],
    G: [],
};

Test cases: bfs(graph) // ['A', 'B', 'С', 'D', 'E', 'F', 'G']

I use this:

const bfs = (graph, start, end) => {
  // create a queue
  let queue = [];
  start = Object.keys(graph)[0]
  const visited = [start];
  // add a starting vertex to it
  queue.push(start)
  // loops as long as there is at least 1 element in the queue
  while (queue.length > 0) {
    // get the current vertex from the queue
    const node = queue.shift()
    // check this vertex on the way further
    if (!graph[node]) {
      graph[node] = []
    }
    // if the array contains an endpoint in the graph at the current vertex - return
    if (graph[node].includes(end)) {
      return visited;
    } else {
      queue = [...queue, ...graph[node]]
    }
  }
}

]

But the problem is that in the found algorithm, I always need to immediately indicate the endpoint, how to find the shortest path and return to write down the steps, I cannot decide on my own.

user_5459839 · Answer

You can just remove from that code anything that relates to end, and add the logic to collect nodes in an array and return that array.

I would also take the opportunity to also improve a few things in that bfs function:

It never adds anything to visited apart from the initial start.
It doesn't use visited to prevent the code from revisiting the same node a second time (in case the graph has cycles)
visited should better be a Set than an array, to avoid bad time complexity (has is more efficient than includes)
There is no need to create a new queue array in each iteration. You can use push to extend the existing array.
When a certain node does not have a key in the graph object, there is no need to create it. We can just skip that node for further expansion.

Here is the proposed code to get a BFS traversal without the need to provide an end node:

const bfs = (graph) => {
  const result = []; // Here we collect the traversed nodes
  const queue = [];
  const start = Object.keys(graph)[0]; // no longer a parameter
  const visited = new Set([start]); // Better efficiency
  queue.push(start);
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node); // Collect!
    if (!graph[node]) continue; // No need to mutate `graph`
    // Collect the unvisited neighbors
    //   ... and mark them as visited at the same time
    const neighbors = graph[node].filter(neighbor =>
      !visited.has(neighbor) && visited.add(neighbor)
    );
    // Append these neighbors at the end of the queue (mutation)
    queue.push(...neighbors);
  }
  return result;
}

// The example from the question
const graph = {A:['B','C'],B:['D','E'],C:['F','G'],D:[],E:[],F:[],G:[]};

console.log(bfs(graph));

Shortest pass BFS graph

1 Answers