MV's blog

Graphs

A graph is a set of vertices connected pairwise by edges. We represent the verteces using integers 0..V-1. There are multiple ways to represent the edges - arrays (adjacency matrix), linked lists, adjacency lists, etc.. Using arrays(matrix) is not optimal because most of the time the matrix will be sparse and there will be a lot of unused space. Using only lists makes the search for a vertex's adjacency list in linear time which is again not optimal. Using an adjacency list fixes both of those issues.

Sample typescript implementation.

export class AdjacencyList {
  public value: number | null;
  public adj: AdjacencyList | null;

  constructor() {
    this.value = null;
    this.adj = null;
  }

  public add(value: number): void {
    if (!this.value) {
      this.value = value;
    } else {
      this.adj = this.push(this.adj, value);
    }
  }

  private push(
    node: AdjacencyList | null,
    value: number,
  ): AdjacencyList {
    if (node == null) {
      node = new AdjacencyList();
      node.value = value;

      return node;
    }

    node.adj = this.push(node.adj, value);

    return node;
  }
}

export class Graph {
  private readonly _vertices: Array<AdjacencyList>;
  private readonly _n: number;

  constructor(n: number) {
    this._n = n;
    this._vertices = new Array<AdjacencyList>();

    for (let i = 0; i < this._n; i++) {
      this._vertices[i] = new AdjacencyList();
    }
  }

  public addEdge(v: number, w: number): void {
    this._vertices[v].add(w);
    this._vertices[w].add(v);
  }

  public adj(v: number): number[] {
    if (!this._vertices[v].value) return [];

    let adj = [];
    let neighbour: AdjacencyList | null = this._vertices[v];
    while (neighbour != null) {
      adj.push(neighbour.value as number);
      neighbour = neighbour.adj;
    }

    return adj;
  }

  public degree(v: number): number {
    const neighbours = this.adj(v);
    return neighbours.length;
  }

  public maxDegree(): number {
    let max = -1;
    for (let i = 0; i < this._vertices.length; i++) {
      let degree = this.degree(i);
      if (degree > max) {
        max = degree;
      }
    }

    return max;
  }

  public V(): number {
    return this._n;
  }
}