Graph Traversal

 

Graph Traversal Uses

• Peer to peer networking
• Web crawlers
• Finding the closest
• matches/recommendations
• Shortest path problems(GPS, Solving mazes, AI)

 

In a Tree, depth first means moving away from the route.

unlike a tree, we need to specify the starting point.

when it comes to depth first traversal, it is finding one neighbor following one neighbor.

It is really important, we remember where we've been.

 

Depth First Traversal -  Recursive 

 

DFS(vertex) :

  if vertex is empty

     return (this is base case)

  add vertex to results list

  mark vertex as visited

  for each neighbor in vertex's neighbors:

    if neighbor is not visited:

      recursively call DFS on neighbor

 

Depth First Traversal - Iterative

 

• The function should accept a starting node
• Create an object to store visited nodes and an array to store the result
• Create a helper function which accepts a vertex
• The helper function should place the vertex it accepts into the visited object and push that vertex into the results
• Loop over all of the values in the adjacencyList for that vertex
• If any of those values have not been visited, invoke the helper function with that vertex
• return the array of results

 

 

// Adjacency List

class Graph{
    constructor() {
      this.adjacencyList = {};
    }
   addVertex(vertex) {
     if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(v1, v2) {
     this.adjacencyList[v1].push(v2);
     this.adjacencyList[v2].push(v1);
   }
   removeEdge(v1, v2) {
     this.adjacencyList[v1] = this.adjacencyList[v1].filter( v => v !== v2);
     this.adjacencyList[v2] = this.adjacencyList[v2].filter( v => v !== v1);
   }
   removeVertex(v1) {
     while(this.adjacencyList[v1].length) {
       const ajacentVertex = this.adjacencyList[vertex].pop();
       this.removeEdge(v1, adjacentyVertex);
     }
     delete this.adjacencyList[v1];
   }
   
   // DFS Recursive
   depthFirstRecursive(start) {
     const result = [];
     const visited = {};
     const adjacencyList = this.adjacencyList;
     
     (function dfs(vertex){
       if(!vertex) return null;
       visited[vertex] = true;
       result.push(vertex); 
       adjacencyLiat[vertex].forEach(neighbor => {
         if(!visited[neighbor]) {
           return dfs(neighbor);
         }
       });
     })(start);
   }
   
   // DFS Iterative
   depthFirstIterative(start) {
     const result = [];
     const visited = {};
     const stack = [start];
     let currentVertex;
     
     visited[start] = true;
     while(stack.length) {
       currentVertex = stack.pop();
       result.push(currentVertex);
       
       this.adjacencyList[currenVertex].forEach(neighbor => {
         if(!visited[neighbor]) {
           visited[neighbor] = true;
           stack.push(neighbor);
         }
       })
     }
   }
   
}

 

Breadth First Graph Traversal

visit all of it's neighbors in depth order

 

• 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 result = [];
  const visited = {};
  visited[start] = true;
  
  while(queue.length) {
  	currentVertext = queue.shift();
    result.push(currentVertex);
   
    this.adjacencyList[currentVertex].forEach( neighbor => {
     if(!visited[neighbor]) {
       visitied[neighbor = true;
       queue.push(neighbor);
     }
    });
  }
}