FilesExpand file tree

 master

/

BreadthFirstSearch.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

37 lines (31 loc) · 1.16 KB

 master

/

BreadthFirstSearch.js

Copy path

Top

File metadata and controls

• Code
• Blame

37 lines (31 loc) · 1.16 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

import Queue from '../Data-Structures/Queue/Queue'

/**

* Breadth-first search is an algorithm for traversing a graph.

*

* It discovers all nodes reachable from the starting position by exploring all of the neighbor nodes at the present

* depth prior to moving on to the nodes at the next depth level.

*

* (description adapted from https://en.wikipedia.org/wiki/Breadth-first_search)

* @see https://www.koderdojo.com/blog/breadth-first-search-and-shortest-path-in-csharp-and-net-core

*/

export function breadthFirstSearch (graph, startingNode) {

// visited keeps track of all nodes visited

const visited = new Set()

// queue contains the nodes to be explored in the future

const queue = new Queue()

queue.enqueue(startingNode)

while (!queue.isEmpty()) {

// start with the queue's first node

const node = queue.dequeue()

if (!visited.has(node)) {

// mark the node as visited

visited.add(node)

const neighbors = graph[node]

// put all its neighbors into the queue

for (let i = 0; i < neighbors.length; i++) {

queue.enqueue(neighbors[i])

}

}

}

return visited

}