We will be creating three modules:

1. A Graph Generator module that helps us generate a graph data structure.
2. A Graph is a data structure that contains nodes
3. Nodes are connected to each other via edges
4. A Depth-first Search (DFS) module that takes a graph and traverses it depth-first.
5. 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:

1. Define a Node class that has a name {{string}}, value{{}}, and neighbors{{array}}
2. Node.addNeighbors([x {{node}}, y {{node}}, z {{node}} ...]): adds an array of nodes x, y, z to node.
3. Node.neighbors(x {{node}}): lists all vertices such that there is an edge from the vertices x to y.
4. [Optional] Node.removeNode(x {{node}}): removes the vertex x, if it is there.

Using these example methods, you should be able to make the graph above like the following:

A = new Node("A")
B = new Node("B")
C = new Node("C")
D = new Node("D")
E = new Node("E")
F = new Node("F")
A.addNeighbors = [B, C]
B.addNeighbors = [D, E]
C.addNeighbors = [F]
D.addNeighbors = []
E.addNeighbors = []
F.addNeighbors = []

The basic operations provided by a Depth-first Search usually include:

1. DFS(start, searchFor): Starting at the node start traverse the graph depth-first and return the value at the node whos key matches searchFor. If there are no matches, return false.

1. BFS(start, searchFor): Starting at the node start traverse the graph breadth-first and return an array of the shortest path between start and the node searchFor. If there are no matches, return false.

1. Write a blog post ELI5 the differences between depth and breadth-first Search.
2. Write Pseudocode for each implementation
3. Explain the Big O notation for each method
4. Provide examples of when you would favor one graph traversal algorithm over the other.
5. Write Tests using Mocha and Chai.
6. Implement a Queue Module for Breadth-first search.
7. Implement a Stack Module for Depth-first search.
8. Write a recursive and non-recursive implementation of BFS and DFS.
9. Visualize each method in the DOM.p

• 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