Graph Traversal - An Intro to Depth and Breadth First Search

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.

Graph data structure example

    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: []
        }
      ]
    }
  ]
}

Graph Methods

The basic operations provided by a graph data structure 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. Return an array with all of the nodes neighbors.
3. Node.getNeighbors(): 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:

let A = new Node("A", "foo1");
let B = new Node("B", "foo2");
let C = new Node("C", "foo3");
let D = new Node("D", "foo4");
let E = new Node("E", "foo5");
let F = new Node("F", "foo6");
A.addNeighbors([B, C]);
B.addNeighbors([D, E]);
C.addNeighbors([F]);

Depth-first Search Methods

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

Breadth-first Search Methods

BFS(start): Starting at the node start traverse the graph breadth-first and return an array of Strings that represent the path that is traversed. For example, in the graph above, BFS(A) should return ["A", "B", "C", "D", "E", "F"].

Getting Started

1. Fork this repository and clone it from your personal GitHub Account
2. In the Terminal, navigate to the newly created folder for this repository.
3. Install dependencies by running the command: npm install
4. Run tests by running the command: npm test
5. Your work will be done in the files named:

• graphGenerator.js
• depthFirstSearch.js
• breadthFirstSearch.js

1. Pay attention to the tests for hints.
2. Make your tests pass!

Stretch Goals

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 time and space complexities for each graph traversing method
4. Provide examples of when you would favor one graph traversal algorithm over the other.
5. Implement a Queue Module for Breadth-first search.
6. Implement a Stack Module for Depth-first search.
7. Implement a Remove Node method for Graph Generator module.
8. Write a recursive and non-recursive implementation of BFS and DFS.
9. Visualize each method in the DOM.

Additional Resources

Graph

• Link: Graph (Abstract Data Type)
• Concepts: Graph Node, Graph theory, search and depth first search

Depth First Search

• Link: Depth First Search
• Concepts: Graph Node, Graph theory, search and depth first search

Breadth First Search

• Link: Breadth First Search
• Concepts: Graph Node, Graph theory, search and breadth first search