# Graph

A collection of nodes with some amount of directed or non-directed connections.

cycle: three or more nodes linked together in a loop

connected: every node can reach every other node

directed: one way connections between nodes

weight: the cost of a link between nodes

dag: directed acyclic graph

node === vertex

# Representation

Normally represented with:

# Adjacency List

Stored in a 2d array. An index is a node and the array at that index is a list of edges.

[
  [
    { to: 3, weight: 10 },
    { to: 5, weight: 4 },
  ],
  [{ to: 1, weight: 1 }],
];

# Adjacency Matrix (O(V^2))

Like an adjacency list but each subarray shows the weight of connections to all other nodes. No connection is represented with a 0.

[
  [0, 0, 10, 0, 4],
  [0, 1, 0, 0, 0],
];

# Search

All trees are graphs, so just use DFS or BFS.

BFS on adjacency matrix:

function bfs(
  graph: WeightedAdjacencyMatrix,
  source: number,
  needle: number,
): number[] | undefined {
  const seen = new Array(graph.length).fill(false);
  const prev = new Array(graph.length).fill(-1);
  const queue: number[] = [source];

  seen[source] = true;

  do {
    const curr = queue.shift() as number;
    if (curr === needle) {
      break;
    }

    const adjs = graph[curr];
    for (let i = 0; i < adjs.length; i++) {
      if (adjs[i] === 0) {
        continue;
      }

      if (seen[i]) {
        continue;
      }

      seen[i] = true;
      prev[i] = curr;
      queue.push(i);
    }
  } while (queue.length);

  let curr = needle;
  const out: number[] = [];
  while (prev[curr] !== -1) {
    out.push(curr);
    curr = prev[curr];
  }

  return out.length ? [source].concat(out.reverse()) : undefined;
}

DFS on adjacency list:

function dfs(
  graph: WeightedAdjacencyList,
  source: number,
  needle: number,
): number[] | undefined {
  const seen: boolean[] = new Array(graph.lenght).fill(false);
  const path: number[] = [];

  walk(graph, source, needle, seen, path);

  return path.length ? path : undefined;
}
function walk(
  graph: WeightedAdjacencyList,
  curr: number,
  needle: number,
  seen: boolean[],
  path: number[],
): boolean {
  if (seen[curr]) {
    return false;
  }

  // pre
  seen[curr] = true;
  path.push(curr);
  if (curr === needle) {
    return true;
  }

  const adjs = graph[curr];
  for (let i = 0; i < adjs.length; i++) {
    const edge = adjs[i];

    if (walk(graph, edge.to, needle, seen, path)) {
      return true;
    }
  }

  // post
  path.pop();

  return false;
}

# Dijkstra's shortest path

The most ultimate classic graph problem is finding the shortest path between nodes. Dijkstra got that on lock with a greedy algorithm.

Make sure to use an adjacency list to maintain O(V^2 + E) in naive implementation or O(logv(v+e)) if you use a min heap rather than a seen array to keep track of the smallest unseen next step.

https://github.com/jollyjerr/algorithms-specialization-notebook/blob/main/course2/week2/dijkstra/dijkstra.go