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.

CodePudding user response：

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