## 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.

## Top comments (0)