common-algorithms-js/algorithms/es/breadthFirstSearch.js at master · sumtype/common-algorithms-js

This repository was archived by the owner on Dec 3, 2023. It is now read-only.

28 lines (25 loc) · 948 Bytes

  A JavaScript module which performs a breadth first search on a graph using the graph's adjacency matrix as input to determine whether or not the graph is connected.  If a connected graph's adjacency matrix is input, true is returned.  If a disconnected graph's adjacency matrix is input, false is returned.
'use strict'
const breadthFirstSearch = (input = null) => {
  if (input === null) return null
  const queue = []
  const visited = []
  let connected = true
  const search = (value, input, f, r) => {
    for (let i = 0; i < input.length; i++) if (input[value][i] && !visited[i]) queue[++r] = i
    if (f <= r) {
      visited[queue[f]] = 1
      search(queue[f++], input, f, r)
  for (let i = 0; i < input.length; i++) {
    queue[i] = 0
    visited[i] = 0
  search(0, input, 0, -1)
  for (let i = 0; i < visited.length; i++) if (!visited[i]) connected = false
  return connected
export default breadthFirstSearch

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

breadthFirstSearch.js

Latest commit

History

breadthFirstSearch.js

File metadata and controls