Docs
Breadth First Search

Breadth First Search

A hook for implementing breadth first search.

About

The useBreadthFirstSearch hook is a custom React hook that provides a Breadth-First Search (BFS) algorithm implementation. It traverses the graph layer by layer, exploring all nodes at the present depth level before moving on to nodes at the next depth level. The hook is flexible, supporting various use cases like finding the shortest path in an unweighted graph or exploring all reachable nodes.

Parameters

NameTypeDescription
graphRecord<string, string[]>The adjacency The adjacency list representation of the graph, where keys are node IDs and values are their neighbors.
startstringThe starting node from which the traversal begins.
targetstringOptional. The target node to which the shortest path should be calculated.
onComplete`(path: string[] or null) => voidOptional. Callback function that gets called after calculation completes.

Return Values

NameTypeDescription
exploredNodesstring[]The nodes that have been explored in the BFS traversal.
pathstring[] or null
isProcessingbooleanA boolean indicating if the algorithm is currently running.
startBFS(graph: Record<string, string[]>, start: string, target?: string, onComplete?: (path: string[] or null) => void) => void
reset() => voidFunction to reset the hook’s state, clearing the traversal results and processing status.

Installation

Run the following command:

npx scriptkavi-hooks@latest add breadth-first-search

Usage

import { useBreadthFirstSearch } from "@/hooks/breadth-first-search"

BFS Traversal of a Graph

import React from "react"
 
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
}
 
function BFSComponent() {
  const { exploredNodes, path, isProcessing, startBFS, reset } =
    useBreadthFirstSearch()
 
  return (
    <div>
      <h3>Graph: {JSON.stringify(graph)}</h3>
      <h3>Explored Nodes: {exploredNodes.join(" -> ")}</h3>
      <h3>
        Shortest Path (A to F): {path ? path.join(" -> ") : "No Path Found"}
      </h3>
 
      <button onClick={() => startBFS(graph, "A", "F")} disabled={isProcessing}>
        {isProcessing ? "Processing..." : "Start BFS from A to F"}
      </button>
 
      <button onClick={reset} disabled={isProcessing}>
        Reset
      </button>
    </div>
  )
}
 
export default BFSComponent

Completion Callback

You can pass a completion callback to the startBFS function that will be triggered when the BFS traversal completes. This is useful if you want to trigger additional actions based on the traversal result.

import React from "react"
 
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
}
 
const BFSCallbackComponent = () => {
  const { startBFS, exploredNodes, path, isProcessing } =
    useBreadthFirstSearch()
 
  return (
    <div>
      <h3>Explored Nodes: {exploredNodes.join(" -> ")}</h3>
      <h3>Path from A to F: {path ? path.join(" -> ") : "No Path"}</h3>
 
      <button
        onClick={() =>
          startBFS(graph, "A", "F", (resultPath) => {
            console.log("Traversal Complete. Path:", resultPath)
          })
        }
        disabled={isProcessing}
      >
        {isProcessing ? "Processing..." : "Start BFS with Callback"}
      </button>
    </div>
  )
}
 
export default BFSCallbackComponent

Considerations

  • Disconnected Nodes: If the graph contains nodes that are disconnected from the rest of the graph, the BFS traversal will only explore the connected components starting from the given start node.

  • Unweighted Graphs: BFS is generally used in unweighted graphs, as it explores nodes in layers. If you're working with weighted graphs, consider using Dijkstra’s algorithm instead.

Window SizeBinary Search