Published on

Authors
•  Name
Curtis Warcup
• Visiting/Updating/Checking each vertex in a graph.
• Since we do not have a dedicated starting point, we need to define one.

### Graph Traversal Uses

• Peer to peer networking
• Web crawlers
• Finding "closest" matches/recommendations
• Shortest path problems
• Solving mazes
• AI (shortest path to win the game)

## Depth First Search Traversal

• explore as far as possible down one brach before "backtracking".
• general idea is we prioritizing children of a given node before we visit siblings.
• in graphs we have NO ROOT NODE.
• follow a graph down, and visit neighbors before you backtrack.

### Depth First Search Recursive

`````` DFS(vertex):
if vertex is empty // base case
return (this is base case)
add vertex to results list // build an array and add results
mark vertex as visited // can do this by setting it to true in the results list
for each neighbor in vertex's neighbors:
if neighbor is not visited:
recursively call DFS on neighbor
``````

Here is what we have:

``````class Graph {
constructor() {
}
}
}
removeEdge(vertex1, vertex2) {
}
removeVertex(vertex) {
}
}
depthFirstRecursive(start) {}
}

let g = new Graph();

console.log(g);
{ A: [ 'B', 'C' ],
B: [ 'A', 'D' ],
C: [ 'A', 'E' ],
D: [ 'B', 'E', 'F' ],
E: [ 'C', 'D', 'F' ],
F: [ 'D', 'E' ] } }

//          A
//        /   \
//       B     C
//       |     |
//       D --- E
//        \   /
//          F
``````
• The function should accept a starting node
• Create a list to store the end result, to be returned at - the very end
• Create an object to store visited vertices
• Create a helper function which accepts a vertex
• The helper function should return early if the vertex is empty
• The helper function should place the vertex it accepts into the visited object and push that vertex into the - result array.
• Loop over all of the values in the adjacencyList for that vertex
• If any of those values have not been visited, recursively invoke the helper function with that vertex
• Invoke the helper function with the starting vertex
• Return the result array
``````// start...
depthFirstRecursive(start) {
const results = [];
const visited = {};
function dfs(vertex) {
if (!vertex) return null;
visited[vertex] = true;
results.push(vertex);
console.log(adjList[vertex]); // [ 'B', 'C' ]
}
dfs(start);
}

// final

depthFirstRecursive(start) {
const results = [];
const visited = {};
function dfs(vertex) {
if (!vertex) return null;
visited[vertex] = true;
results.push(vertex);
if (!visited[neighbor]) {
return dfs(neighbor);
}
});
}
dfs(start);
return results;
}

console.log(g.depthFirstRecursive('A'));

//
[ 'A', 'B', 'D', 'E', 'C', 'F' ]
``````

## DFS Iteratively

``````DFS-iterative(start):
let S be a stack
S.push(start)
while S is not empty
vertex = S.pop()
if vertex is not labeled as discovered:
visit vertex (add to result list)
label vertex as discovered
for each of vertex's neighbors, N do
S.push(N)
``````
• The function should accept a starting node
• Create a stack to help use keep track of vertices (use a list/array) Create a list to store the end result, to be returned at the very end
• Create an object to store visited vertices
• Add the starting vertex to the stack, and mark it visited
• While the stack has something in it:
• Pop the next vertex from the stack
• If that vertex hasn't been visited yet:
• ​Mark it as visited
• Add it to the result list
• Push all of its neighbors into the stack
`````` depthFirstIterative(start) {
const stack = [start];
const results = [];
const visited = {};
let currentVertex;

visited[start] = true;
while (stack.length) {
console.log(stack);
currentVertex = stack.pop();
results.push(currentVertex);
// now need to access the neighbors of currentVertex
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
});
}
return results;
}

let g = new Graph();

console.log(g);

//          A
//        /   \
//       B     C
//       |     |
//       D --- E
//        \   /
//          F

console.log(g.depthFirstIterative('A'));

//
[ 'A', 'C', 'E', 'F', 'D', 'B' ]

``````

Visit neighbors at current depth first!

• This function should accept a starting vertex
• Create a queue (you can use an array) and place the starting vertex in it
• Create an array to store the nodes visited
• Create an object to store nodes visited
• Mark the starting vertex as visited
• Loop as long as there is anything in the queue
• Remove the first vertex from the queue and push it into the array that stores nodes visited
• Loop over each vertex in the adjacency list for the vertex you are visiting.
• If it is not inside the object that stores nodes visited, mark it as visited and enqueue that vertex
• Once you have finished looping, return the array of visited nodes
``````  breadthFirst(start) {
const queue = [start];
const results = [];
const visited = {};
let currentVertex;
visited[start] = true;

while (queue.length) {
currentVertex = queue.shift();
results.push(currentVertex);

if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
});
}
return results;
}

let g = new Graph();

console.log(g);

//          A
//        /   \
//       B     C
//       |     |
//       D --- E
//        \   /
//          F

// [ 'A', 'B', 'C', 'D', 'E', 'F' ]
``````

Full code

``````class Graph {
constructor() {
}
}
}
removeEdge(vertex1, vertex2) {
}
removeVertex(vertex) {
}
}
depthFirstRecursive(start) {
const results = []
const visited = {}
function dfs(vertex) {
if (!vertex) return null
visited[vertex] = true
results.push(vertex)
if (!visited[neighbor]) {
return dfs(neighbor)
}
})
}
dfs(start)
return results
}
depthFirstIterative(start) {
const stack = [start]
const results = []
const visited = {}
let currentVertex

visited[start] = true
while (stack.length) {
console.log(stack)
currentVertex = stack.pop()
results.push(currentVertex)
// now need to access the neighbors of currentVertex
if (!visited[neighbor]) {
visited[neighbor] = true
stack.push(neighbor)
}
})
}
return results
}
const queue = [start]
const results = []
const visited = {}
let currentVertex
visited[start] = true

while (queue.length) {
currentVertex = queue.shift()
results.push(currentVertex)

if (!visited[neighbor]) {
visited[neighbor] = true
queue.push(neighbor)
}
})
}
return results
}
}

let g = new Graph()