- Description
- Recursive depth first search
- Iterative depth first search
- Iterative depth first search with recursive-like order
Given the following graph:
Represented by the following javascript data structure:
const graph = {
a: ["b", "e"],
b: ["c", "d"],
c: [],
d: [],
e: ["f"],
f: [],
};
Three possible way could be used to iterate through its nodes. They are explained below.
In index.js
one can find the function recursiveDFS
.
Given a graph
parameter it will iterate over its nodes by using recursion and returns an array representing the
iteration order.
The function called in the following way:
recursiveDFS(graph);
Will have the following returned value:
['a', 'b', 'c', 'd', 'e', 'f']
In index.js
one can find the function iterativeDFS
.
Given a graph
parameter it will iterate over its nodes by using iteration and returns an array representing the
iteration order.
The function called in the following way:
iterativeDFS(graph);
Will have the following returned value:
['a', 'e', 'f', 'b', 'd', 'c']
In index.js
one can find the function orderedIterativeDFS
.
Given a graph
parameter it will iterate over its nodes by using iteration and returns an array representing the
iteration order.
The difference between iterativeDFS
and orderedIterativeDFS
is that the orderedIterativeDFS
iterate over the
nodes in the same order as recursiveDFS
.
The function called in the following way:
orderedIterativeDFS(graph);
Will have the following returned value:
['a', 'b', 'c', 'd', 'e', 'f']