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?

You know about Data-structure?
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.

start with 'A' like DFS did,

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.

Thanks for reading, and sorry for my bad english.
If you have a question then please comment, I'll answer as far as I know.