Phantola

Posted on

# DFS/BFS with JS

## Greeting

Hello! I'm junior programmer who restart a career of dev.
Before tech interview, I think I have to remind a basic algorithms
When I was in univ, I'm very weak about algorithms, specifically Graph.
So I re-learned that, and I wanna share this with beginner or very junior programmer.

## What is in this content

• What is Graph (simple definition)
• What is DFS / How to implement it
• What is BFS / How to implement it

## What is Graph?

Data-structure is a structures for save data efficiently like array, linked-list, stack, queue, deck etc.

Graph is one of data-structure consiste of vertex(node, data...) and edge(pointer, line, link..).

It seems like down below (Vertex is circle, Edge is green-line).

So, Graph is good data-structure to represent a relation between objects.

## What is DFS / How to implement it

DFS (Depth First Search) is a algorithm for graph searching.
DFS is visit a nodes as deep as possible.

if a node has not edge to another node, go back to previous node and do the same thing (visit a nodes as deep as possible)

For example, graph like upper image and search start with 'A' and

step 1 : visit A, and A has edges to 'F', 'B'
step 2 : visit F, and F has not edge.
step 3 : visit B, and B has edges to 'D' , 'C'
step 4 : visit D, and D has edge to 'E'
step 5 : visit E, and E has not edge.
step 6 : visit C, C has not edge. And it's done.

DFS works like this.

### How to implement DFS with JS?

According to explained above, DFS basically need a visited/need-to-visit list to store a node.

At first we need a graph, so we will make a object as a graph down below.

``````const graph = {
'A' : ['F', 'B'], // 'A' has edges to F, B
'B' : ['D', 'C'], // 'A' has edges to D, C
'D' : ['E'] // 'D' has edge to 'E'
}
``````

Okey then, we start to implement.

``````
const dfs = (graph, start) => {
let visited = []; // save a visited nodes
let needVisit = [];  // save a need-to-visit nodes

needVisit.push(start);  // start search with start node

// looping for need-to-visit list
while(needVisit.length !== 0) {
let node = needVisit.shift(); // take a nodes which in first position in array
if(!visited.includes(node)){ // if this node is not visited,
visited.push(node); // add to visited list (now visit)

const tmp = (!graph[node] ? [] : graph[node])
needVisit = [...tmp , ...needVisit]
// dfs is depth first, So, nodes connected to this node has more high priority than original nodes in need-to-visit list
}
}
return visited.join(' ');
}

``````

## What is BFS / How to implement it

BFS (Breadth First Search) searches nodes in nearest order.

step 1 : visit A, and A has edges to 'F', 'B'
step 2 : visit F, and F has not edge. return to 'A'
step 3 : visit B, and B has edges to 'D' , 'C'
step 4 : visit D, and D has edge to 'E'
step 5 : visit C, and C has not edge.
step 6 : visit E, E has not edge. And it's done.

BFS works like this.

### How to implement BFS with JS?

BFS also need a visited/need-to-visit list to store a node like DFS.

Graph object is same as DFS example and code with explanation is down below.

``````
const bfs = (graph, start) => {
let visited = []; // save a visited nodes
let needVisit = [];  // save a need-to-visit nodes

needVisit.push(start);  // start search with start node

// looping for need-to-visit list
while(needVisit.length !== 0) {
let node = needVisit.shift(); // take a nodes which in first position in array
if(!visited.includes(node)){ // if this node is not visited,
visited.push(node); // add to visited list (now visit)

const tmp = (!graph[node] ? [] : graph[node])
needVisit = [...needVisit, ...tmp]
// bfs is breadth first, So, nodes(child nodes) connected to this node has lower priority than original nodes in need-to-visit list
}
}
return visited.join(' ');
}

``````

## Finish

Actually D/BFS can be implemente a recursive way.
If you have a time, recommend to try.