We will be creating three modules:
- A Graph Generator module that helps us generate a graph data structure.
- A Graph is a data structure that contains nodes
- Nodes are connected to each other via edges
- A Depth-first Search (DFS) module that takes a graph and traverses it depth-first.
- A Breadth-first Search (BFS) module that takes a graph and traverses it breadth-first.
A
^
B C
^ |
D E F
Is represented in memory as:
{ name: 'A',
value: 'foo1',
neighbors: [
{ name: 'B',
value: 'foo2',
neighbors: [
{ name: 'D',
value: 'foo4',
neighbors: []
},
{ name: 'E',
value: 'foo5',
neighbors: []
}
]
},
{ name: 'C',
value: 'foo3',
neighbors: [
{ name: 'F',
value: 'foo6',
neighbors: []
}
]
}
]
}
The basic operations provided by a graph data structure usually include:
adjacent(G, x, y)
: tests whether there is an edge from the vertices x to y; neighbors(G, x): lists all vertices such that there is an edge from the vertices x to y;add_vertex(G, x)
: adds the vertex x, if it is not there;remove_vertex(G, x)
: removes the vertex x, if it is there;
The basic operations provided by a Depth-first Search usually include:
DFS(start, searchFor)
: Starting at the nodestart
traverse the graph depth-first and return the value at thenode
whos key matchessearchFor
. If there are no matches, returnfalse
.
BFS(start, searchFor)
: Starting at the nodestart
traverse the graph breadth-first and return an array of the shortest path betweenstart
and the nodesearchFor
. If there are no matches, returnfalse
.
- Write a blog post ELI5 the differences between depth and breadth-first Search.
- Write Pseudocode for each implementation
- Explain the Big O notation for each method
- Provide examples of when you would favor one graph traversal algorithm over the other.
- Write Tests using
Mocha
andChai
. - Implement a Queue Module for Breadth-first search.
- Implement a Stack Module for Depth-first search.
- Write a recursive and non-recursive implementation of BFS and DFS.
- Visualize each method in the DOM.
- Link: Graph (Abstract Data Type)
- Concepts: Graph Node, Graph theory, search and depth first search
- Link: Depth First Search
- Concepts: Graph Node, Graph theory, search and depth first search
- Link: Breadth First Search
- Concepts: Graph Node, Graph theory, search and breadth first search
- Link: Graph Traversal Algorithms Implemented in JavaScript
- Concepts: Graph Node, Graph theory, search and breadth first search