Graph

The Graph data structure is a collection of nodes.

But unlike with trees, there are no rules about how nodes should be connected.

There are no root, parent, or child nodes.

Also, nodes are called vertices and they are connected by edges.

Usually, graphs have more edges than vertices.

Graphs with more edges than vertices are called dense graphs.

If there are fewer edges than vertices, then it’s a sparse graph.

In some graphs, the edges are directional.

These are known as directed graphs or digraphs.

Graphs are considered to be connected if there is a path from each vertex to another.

Graphs whose edges are all bidirectional are called undirected graphs, unordered graphs, or just graphs.

These types of graphs have no implied direction on edges between the nodes.

Edge can be traversed in either direction.

By default, graphs are assumed to be unordered.

In some graphs, edges can have a weight.

These are called weighted graphs.

So, when I say edges have a weight, what I mean to say is that they have some numbers which typically shows the cost of traversing in a graph.

When we are concerned with the minimum cost of traversing the graph then what we do is we find the path that has the least sum of those weights.

Cyclic graphs are a sort of graph in which the starting vertex also serves as the final vertex.

Trees are a special type of graph that includes a path from the starting vertex (the root) to some other vertex.

Therefore, trees are Acyclic Graphs.

Representing Graphs

A graph can be represented using 3 data structures- adjacency matrix, adjacency list and Edge List.

An adjacency matrix can be thought of as a table with rows and columns.

The row labels and column labels represent the nodes of a graph.

An adjacency matrix is a square matrix where the number of rows, columns and nodes are the same.

Each cell of the matrix represents an edge or the relationship between two given nodes.

In adjacency list representation of a graph, every vertex is represented as a node object.

The node may either contain data or a reference to a linked list.

This linked list provides a list of all nodes that are adjacent to the current node

The Edge List is another way to represent adjacent vertices.

It is much more efficient when trying to figure out the adjacent nodes in a graph.

The edge list contains a list of edges in alphanumerical order.

Graphs Good at 😀:

• Relationships

Graphs Bad at 😒:

• Scaling is hard

class Graph {
  constructor() {
    this.vertices = {}; // Adjacency list representation
  }

  // Add a vertex to the graph
  addVertex(vertex) {
    if (!this.vertices[vertex]) {
      this.vertices[vertex] = [];
    }
  }

  // Add an undirected edge between two vertices
  addEdge(vertex1, vertex2) {
    if (!this.vertices[vertex1] || !this.vertices[vertex2]) {
      console.log("One or both vertices do not exist.");
      return;
    }

    if (!this.vertices[vertex1].includes(vertex2)) {
      this.vertices[vertex1].push(vertex2);
    }

    if (!this.vertices[vertex2].includes(vertex1)) {
      this.vertices[vertex2].push(vertex1);
    }
  }

  // Remove an undirected edge between two vertices
  removeEdge(vertex1, vertex2) {
    if (!this.vertices[vertex1] || !this.vertices[vertex2]) {
      console.log("One or both vertices do not exist.");
      return;
    }

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

  // Remove a vertex from the graph along with its incident edges
  removeVertex(vertex) {
    if (!this.vertices[vertex]) {
      console.log("Vertex does not exist.");
      return;
    }

    for (const neighbor of this.vertices[vertex]) {
      this.vertices[neighbor] = this.vertices[neighbor].filter(v => v !== vertex);
    }

    delete this.vertices[vertex];
  }

  // Print the adjacency list representation of the graph
  printGraph() {
    for (const vertex in this.vertices) {
      console.log(vertex + " -> " + this.vertices[vertex].join(", "));
    }
  }
}

// Example usage:
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B");
graph.addEdge("B", "C");
graph.addEdge("C", "A");

console.log("Graph:");
graph.printGraph();

graph.removeEdge("B", "C");
console.log("\nGraph after removing edge between B and C:");
graph.printGraph();

graph.removeVertex("A");
console.log("\nGraph after removing vertex A:");
graph.printGraph();