Skip to content

Instantly share code, notes, and snippets.

@thg303
Created April 28, 2019 08:22
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save thg303/8871044d4fd75de17c1e5c7c518c5859 to your computer and use it in GitHub Desktop.
// graph image https://imagebin.ca/v/4fEWnt6XNraD
// 11. Breadth first search and queue [udemy easy to advanced data structure]
class Node {
constructor (value = null) {
this.value = value;
this.neighbours = []
}
setNeighbours (neighbours) {
this.neighbours = neighbours;
}
setValue (value) {
this.value = value
}
}
let graph = []
for (let i = 0; i < 13; i++) {
graph.push(new Node(i))
}
// building graph schema
graph[0].setNeighbours([graph[1], graph[9]])
graph[1].setNeighbours([graph[0], graph[8]])
graph[9].setNeighbours([graph[0], graph[8]])
graph[8].setNeighbours([graph[1], graph[9], graph[7]])
graph[7].setNeighbours([graph[8], graph[10], graph[11], graph[3], graph[6]])
graph[10].setNeighbours([graph[7]])
graph[11].setNeighbours([graph[7]])
graph[6].setNeighbours([graph[5], graph[7]])
graph[3].setNeighbours([graph[7], graph[2], graph[4]])
graph[2].setNeighbours([graph[3]])
graph[4].setNeighbours([graph[2]])
// using array as queue
// use .push() to enqueue
// use .shift() to dequeue
let startPoint = graph[0];
let q = [startPoint];
let traversedItems = [];
while (q.length > 0) {
let currentItem = q.shift();
if (!traversedItems.includes(currentItem.value)) {
traversedItems.push(currentItem.value);
for (let i = 0; i < currentItem.neighbours.length; i++) {
if (!traversedItems.includes(currentItem.neighbours[i].value)) {
q.push(currentItem.neighbours[i])
}
}
}
}
console.log('traverse path:', traversedItems);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment