# Ouadie/js-graph-traversal forked from devleague/js-graph-traversal

An exercise in traversing graphs in JavaScript
This branch is 4 commits ahead, 4 commits behind devleague:master. Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information. solution test .gitignore README.md breadthFirstSearch.js depthFirstSearch.js graphGenerator.js package.json

# 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");
``````

## 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.