Breadth-First Search (BFS)

Summary §

==BFS is a type of Graph search - a method of traversing (visiting) nodes in a graph particular (efficient) order. Specifically, where we visit all the neighbours of a node before moving to the next level.==

Nodes: Think of nodes as individual items in a data structure. In an array, each element could be considered a node. In an object, each key-value pair could be a node.

Connections: Nodes are often connected to other nodes. In more complex structures like graphs or trees, these connections are explicit. - In an array, elements are connected by their indices (each element is “connected” to the next one). - In an object, you could consider related properties as connected.

In an array, a simple traversal would be a for-loop going through each element.

How it works: We start with a root node (A) and we explore all of its children (E, B, G). Then we move to the first node one layer down (E) and explore all of its children (D, F)

Relating nodes/connections to familiar data structures:

let fileSystem = {
  "Documents": {
    "Work": ["report.doc", "presentation.ppt"],
    "Personal": ["budget.xlsx"]
  },
  "Pictures": {
    "Vacation": ["beach.jpg", "mountain.jpg"],
    "Family": ["birthday.png"]
  }
};

Here, each key in the object is a “node” (representing a folder), and its value (either an object or an array) represents its “children” (subfolders or files).

Traversing this structure using BFS would mean:

1. Start with the root (“Documents” and “Pictures”)
2. Then visit all their immediate children (“Work”, “Personal”, “Vacation”, “Family”)
3. Then visit the next level (all the files)

To implement this, we'd typically use a queue (which could be represented by an object in JavaScript):

Purpose §

Time Complexity: §

Implementation: §

// Define a type for the graph
type Graph<T> = {
  [key: string]: T[]
};
// Example usage
const graph: Graph<string> = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};
 
// Define the Queue interface
interface Queue<T> {
  enqueue: (item: T) => void;
  dequeue: () => T | undefined;
  peek: () => T | undefined;
  isEmpty: () => boolean;
  size: () => number;
}
 
 
const createQueue = () => {
  const queue = [];
  return {
    enqueue: (item: any) => queue.push(item), // add a vertice to the queue
    dequeue: () => {
      const removeFirst = queue.shift()
      console.log('removed', removeFirst, 'from queue, added', removeFirst, 'to current vertex')
      return removeFirst
    }, // remove the first item from the array
    firstInQueue: () => queue[0], // check the first item in the queue
    isEmpty: () => queue.length === 0,
    sizeOfQueue: () => queue.length,
    showQueue: () => console.log('current queue', queue),
    includes: (item: any) => queue.includes(item), // boolean return to check if item is in queue
    getQueue: () => [...queue] // get a copy of the queue
  }
}
 
const bfs = (graph, startingVertex) => {
  // we need to create a queue
  const q = createQueue();
  const visited: string[] = [];
  let currentVertex = startingVertex;
 
  // add the vertices adjacent to the current vertex
  console.log('current vertex:', currentVertex)
  // initialise the queue with adjacent vertices of the root starting vertex
  graph[currentVertex].map((neighbour) => {
    q.enqueue(neighbour)
  });
  q.showQueue();
 
  while(!q.isEmpty()) {
    // access a vertex of the graph and add all of its adjacent vertices to the queue
    graph[currentVertex].map((neighbour) => {
      // add the vertices that are adjacent to the starting vertex to the queue
      if (!visited.includes(neighbour) && !q.includes(neighbour)) {
        q.enqueue(neighbour);
        console.log('adding',neighbour, 'to queue')
      }
    })
    // take the current vertex, and put it in visited
    visited.push(currentVertex);
    // take the first vertex in the queue and make it the current vertex
    currentVertex = q.firstInQueue();
    // remove the first vertex from the queue
    console.log('visited:', visited)
    q.dequeue();
    if (q.isEmpty()) {
      console.log('queue is empty')
      visited.push(currentVertex)
      console.log('current vertex:', currentVertex)
      console.log('visited:', visited)
      console.log('breadth first search finished')
      break
    }
    console.log('current vertex:', currentVertex)
 
    q.showQueue();
    console.log('adding new adjacent nodes to queue...')
  }
  console.log('finished: ', visited)
  return visited
}
 
bfs(graph, "A")

Drawing here14234.excalidraw