TIL 41 | Graph

What is Graph

A graph is an abstract notation used to represent the connection between pairs of objects.

Make a graph

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }
}

Adding and edge

This function should accept two vertices, we can call them vertex1 and vertex 2

The function should find in the adjacency list the key of vertex1 and push vertex 2 to the array

The function should find in the adjacency list the key of vertex2 and push vertex1 to the array

addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

Removing an edge

This function should accept two vertices, we'll call them vertex1 and vertex2

The function should reassign the key of vertex1 to be an array that does not contain vertex2

The function should reassign the key of vertex2 to be an array that does not contain vertex1

Don't worry about handling errors/invalid vertices

removeEdge(v1, v2) {
    this.adjacencyList[v1] = this.adjacencyList[v1].filter((v) => v !== v2);
    this.adjacencyList[v2] = this.adjacencyList[v2].filter((v) => v !== v1);
  }

Removing a vertex

This function should accept a vertex to remove

The function should loop as long as there are any other vertices in the adjacency list for that vertex

Inside of the loop, call our removeEdge function with the vertex we are removing and any values in the adjacency list for that vertex

Delete the key in the adjacency list for that vertex

removeVertex(vertex) {
    while (this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];
  }

DFS - recursive

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 adjacencyLst 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

DFSRecursive(start) {
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList;

    (function dfs(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          return dfs(neighbor);
        }
      });
    })(start);
    return result;
  }

DFS - iterative

The function should accept a starting node

Create a stack to help use keep track of vertices

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 itL

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

Pusth all of its neighbors in the stack

return the result array

DFSIterative(start) {
    const stack = [start];
    const result = [];
    const visited = {};
    let cur;

    visited[start] = true;
    while (stack.length) {
      cur = stack.pop();
      result.push(cur);
      this.adjacencyList(cur).forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      });
    }
    return result;
  }

BFS

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

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 adjancency 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

BFS(start) {
    const queue = [start];
    const result = [];
    const visited = {};
    visited[start] = true;
    let cur;

    while (queue.length) {
      cur = queue.shift();
      result.push(cur);

      this.adjacencyList[cur].forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      });
    }
    return result;
  }
}