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)