Graph

Today, we'll talk about graphs, not the kind you see in charts, but the kind used extensively in programming. Graphs are fundamental structures with many uses cases including social networks, search engines, and routing algorithms without us noticing.

Theory

Vocabulary Specific to Graphs

• Vertex: Also known as a Node.
• Edge: A connection between nodes.

Graphs are similar to binary trees but with key differences:

• Relationships: Unlike trees, graphs do not have a hierarchical structure. Each node can have a unique relationship with others, which can be directed or undirected.
• Order: There is no inherent order in graphs. The order is determined by values if relations are weighted; otherwise, it's determined solely by relationships.

Types of Graphs

• Undirected Graphs: Edges connect vertices bidirectionally. For example, Facebook friendships where if you are friends with someone, they are also friends with you.
• Directed Graphs: Edges specify a direction. For example, following someone on Instagram does not necessarily mean they follow you back.
• Unweighted Graphs: All edges have the same weight or priority.
• Weighted Graphs: Each edge has its own weight, indicating different priorities or strengths in relationships.

Implementing Graphs

There are multiple ways to implement a graph, but we'll focus on two:

• Adjacency List: An object where each key is a vertex, and the value is an array of connected edges.
• Adjacency Matrix: A two-dimensional array storing connections between nodes.

For simplicity and suitability for smaller projects, we'll focus on the adjacency list.

Adjacency List implementation

Graph Class

Our adjacency list relies on an object:

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

Add Vertex

Adding vertices to the adjacency list:

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

Explanation: Explanation: We set the key-value pair to be the provided vertex as the key and an empty array as the value only if it doesn't already exist.

addVertex("London"); // { "London": [] }
addVertex("Paris"); // { "London": [], "Paris": [] }

Add Edge

Adding an edge between two vertices:

function addEdge(vertex1, vertex2) {
  if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1);
  }
}

addEdge("London", "Paris");
// { "London": ["Paris"], "Paris": ["London"] }

Explanation: We check if both vertices exist and then link them by adding each to the other's adjacency list

addEdge("London", "Paris");
// { "London": ["Paris"], "Paris": ["London"] }

Remove Edge

Removing an edge between two vertices:

function removeEdge(vertex1, vertex2) {
  this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
    (v) => v !== vertex2
  );

  this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
    (v) => v !== vertex1
  );
}

Explanation: We remove each vertex from the other's adjacency list.

Remove Vertex

Removing a vertex from the graph:

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

Explanation: We remove all edges connected to the vertex and then delete the vertex itself.

Graph traversal

Graph traversal involves visiting all the vertices in a graph. We'll discuss two common strategies: Depth-First Search (DFS) and Breadth-First Traversal (BFS).

Depth First

DFS explores as deep as possible along each branch before backtracking.

Recursive Approach

function depthFirstRecursive(start) {
  const visited = {};
  const ordered = [];
  const adjacencyList = this.adjacencyList;

  (function traverse(vertex) {
    if (!vertex) return null;

    visited[vertex] = true;
    ordered.push(vertex);
    for (let neighbor of adjacencyList[vertex]) {
      if (visited[neighbor]) continue;
      traverse(neighbor);
    }
  })(start);

  return ordered;
}

Explanation: We start by defining two variables, first the visited object which will hold vertices as keys and a boolean as value, then we have the ordered array which we'll return as result. Then we define a helper function traverse that takes a vertex as an argument marks it as visited, adds it to the result list, and then recursively visits all its unvisited neighbors.

Iterative Approach

function depthFirstIterative(start) {
  const stack = [start];
  const visited = {};
  const ordered = [];
  visited[start] = true;

  while (stack.length) {
    const vertex = stack.pop();
    ordered.push(vertex);
    for (let neighbor of this.adjacencyList[vertex]) {
      if (visited[neighbor]) continue;
      visited[neighbor] = true;
      stack.push(neighbor);
    }
  }

  return ordered;
}

Explanation: We first define three variables, a stack to keep track of vertices to visit, a visited object which will hold vertices as keys and a boolean as value, then we have the ordered array which we'll return as result. Then we continue by pushing the initial vertex onto the stack and marking it as visited. We then processes each vertex by popping it from the stack, adding it to the result list, and pushing its unvisited neighbors onto the stack.

Breadth-First Traversal (BFS)

BFS is another algorithm for traversing or searching through a tree or graph data structures. It starts at a given node and explores all neighboring nodes at the present depth before moving on to nodes at the next depth level.

function breathFirstTraversal(start) {
  const queue = [start];
  const visited = {};
  const ordered = [];
  visited[start] = true;

  while (queue.length) {
    const vertex = queue.shift();
    ordered.push(vertex);
    for (let neighbor of this.adjacencyList[vertex]) {
      if (visited[neighbor]) continue;
      visited[neighbor] = true;
      queue.push(neighbor);
    }
  }

  return ordered;
}

Explanation: BFS uses a queue to keep track of vertices to visit. It starts by enqueuing the initial vertex and marking it as visited. It then processes each vertex by dequeuing it, adding it to the result list, and enqueuing its unvisited neighbors.

Adjacency Matrix Implementation

Let's expand our post to include an implementation using an adjacency matrix, this will give you an alternative method to represent and manipulate graphs.

Graph Class

class Graph {
  constructor(size) {
    this.vertices = [];
    this.adjacencyMatrix = [];
  }
}

Explanation: Our graph holds two variables one storing vertices, could be string, numbers or even objects.

Add Vertex

This function adds a new vertex to the graph.

function addVertex(vertex) {
  if (!this.vertices.includes(vertex)) {
    this.vertices.push(vertex);
    this.adjacencyMatrix.forEach((row) => row.push(0));
    this.adjacencyMatrix.push(new Array(this.vertices.length).fill(0));
  }
}

Explanation:

• It first checks if the vertex is not already present in the list of vertices.
• If the vertex is new, it is added to the vertices array.
• The adjacency matrix is then updated to include a new row and column, initialized to 0, representing no edges initially.

addVertex("London"); // vertices = ["London"]; adjacencyMatrix = [[0]]
addVertex("Paris"); // vertices = ["Paris"]; adjacencyMatrix = [[0, 0] [0, 0]]

Add Edge

This function adds an edge between two vertices.

function addEdge(vertex1, vertex2) {
  const index1 = this.vertices.indexOf(vertex1);
  const index2 = this.vertices.indexOf(vertex2);

  if (index1 !== -1 && index2 !== -1) {
    this.adjacencyMatrix[index1][index2] = 1;
    this.adjacencyMatrix[index2][index1] = 1;
  }
}

Explanation:

• It finds the indices of the vertices in the vertices array.
• If both vertices exist, it sets the corresponding elements in the adjacency matrix to 1, indicating an edge between them.

addEdge("Paris", "London"); // adjacencyMatrix = [[0, 1] [1, 0]]

Remove Edge

This function removes an edge between two vertices.

function removeEdge(vertex1, vertex2) {
  const index1 = this.vertices.indexOf(vertex1);
  const index2 = this.vertices.indexOf(vertex2);

  if (index1 !== -1 && index2 !== -1) {
    this.adjacencyMatrix[index1][index2] = 0;
    this.adjacencyMatrix[index2][index1] = 0;
  }
}

Explanation:

• It finds the indices of the vertices in the vertices array.
• If both vertices exist, it sets the corresponding elements in the adjacency matrix to 0, indicating no edge between them

removeEdge("Paris", "London"); // adjacencyMatrix = [[0, 0] [0, 0]]

Remove Vertex

This function removes a vertex from the graph.

function removeVertex(vertex) {
  const index = this.vertices.indexOf(vertex);

  if (index !== -1) {
    this.vertices.splice(index, 1);
    this.adjacencyMatrix.splice(index, 1);
    this.adjacencyMatrix.forEach((row) => row.splice(index, 1));
  }
}

Explanation:

• It finds the index of the vertex in the vertices array.
• If the vertex exists, it removes the vertex from the vertices array and updates the adjacency matrix to remove the corresponding row and column.

removeEdge("Paris"); // vertices = ["London"] adjacencyMatrix = [[0] [0]]

Graph traversal

Let's talk about traversing an adjacency matrix with our two common approaches Depth-First Search (DFS) and Breadth-First Traversal (BFS).

Depth First Traversal (DFS)

DFS explores from a given vertex as deep as possible along each branch before backtracking.

function depthFirstTraversal(start) {
  const visited = {};
  const result = [];

  const vertices = this.vertices;
  const adjacencyMatrix = this.adjacencyMatrix;
  function traverse(vertexIndex) {
    visited[vertexIndex] = true;
    result.push(vertices[vertexIndex]);

    for (let i = 0; i < adjacencyMatrix[vertexIndex].length; i++) {
      if (adjacencyMatrix[vertexIndex][i] === 1 && !visited[i]) {
        traverse(i);
      }
    }
  }

  const startIndex = this.vertices.indexOf(start);
  if (startIndex !== -1) {
    traverse(startIndex);
  }

  return result;
}

Explanation:

• It uses a helper function traverse to recursively visit each vertex and its unvisited neighbors.
• The result of the traversal is stored in the result array and returned.

Breadth-First Traversal (BFS)

We start from a given node and explores all neighboring nodes at the present depth before moving on to nodes at the next depth level.

function breadthFirstTraversal(start) {
  const visited = {};
  const result = [];
  const queue = [];

  const startIndex = this.vertices.indexOf(start);
  if (startIndex !== -1) {
    queue.push(startIndex);
    visited[startIndex] = true;

    while (queue.length) {
      const vertexIndex = queue.shift();
      result.push(this.vertices[vertexIndex]);

      for (let i = 0; i < this.adjacencyMatrix[vertexIndex].length; i++) {
        if (this.adjacencyMatrix[vertexIndex][i] === 1 && !visited[i]) {
          visited[i] = true;
          queue.push(i);
        }
      }
    }
  }

  return result;
}

Explanation:

• It uses a queue to manage the order of traversal, visiting each vertex and its unvisited neighbors level by level.
• The result of the traversal is stored in the result array and returned.

Practical Use Cases

Graphs are used in various real-world applications:

• Social Networks: Representing friendships and connections.
• Routing Algorithms: Finding the shortest path in navigation systems.
• Recommendation Systems: Suggesting films or products based on connections.

Performance Considerations

Understanding the performance of graph operations is essential for efficient algorithm design. Graphs can be represented using adjacency lists or matrices, each with distinct performance implications.

Time Complexity:

Traversal Operations (DFS and BFS): Both have a time complexity of O(V+E), where V is the number of vertices and E is the number of edges, as each vertex and edge is visited once.

Insertion and Deletion of Vertices:

• Adjacency List: Insertion is O(1), while deletion can be O(V+E).
• Adjacency Matrix: Both insertion and deletion are generally O(n²) due to matrix resizing.

Insertion and Deletion of Edges:

• Adjacency List: Both operations are typically O(1).
• Adjacency Matrix: Both operations are O(1), involving simple matrix updates.

Space Complexity:

• Adjacency List: Space complexity is O(V+E), making it efficient for sparse graphs.
• Adjacency Matrix: Space complexity is O(n²), suitable for dense graphs but less efficient for sparse ones.

Conclusion

Graphs are a powerful data structure used in various applications. Understanding how to implement and traverse graphs is essential for solving complex problems efficiently.

I hope you enjoyed this as much as I enjoyed writing it. If you have any questions or recommendations, please leave them!