Graphs

Terminology

node	A point or vertice on the graph. (Also stated as V)
edge	The connection between two nodes. (Also stated as E)
connected	When every node has a path to another node.
cycle	When you start at $Node_X$, follow the links, and end back at $Node_X$. (Can't be only 2 nodes)
acyclic	A graph that contains no cycles.
directed	When there is a direction to the connections. (This helps making asymetric connections, Ex.: $A \rightarrow_{10} B$ but $B \rightarrow_{20} A$)
undirected	Not directed. (The default) (Ex.: $A \rightarrow B$ has the same weight as $B \rightarrow A)$
weighted	The edges have a weight associated with them.
dag	Directed, acyclic graph.

Representing Graphs

Adjacent List

A list, where each main index of the list points to a node of the graph, describing its connections to the other nodes.

This representation is more commonly used.

// Default one as Above
type WeightedAdjList = {
    to: number;
    weight: number;
}[][]

// An adaptation to include `seen`
interface WeightedAdjNode {
    seen?: boolean;
    edges: {
        to: number;
        weight: number;
    }[]
}
type WeightedAdjListWithSeen = WeightedAdjNode[];

Traversing/Searching with BFS

function bfs(graph: WeightedAdjListWithSeen, source: number, needle: number): boolean {
    const queue: number[] = [source];
    
    while (queue.length) {
        const currNode = queue.shift();
        if (currNode === needle) return true;
        graph[currNode].seen = true;
        for (let neighbor of graph[currNode].edges) {
            if (!graph[neighbor.to]?.seen) queue.push(neighbor.to);
        }
    }
    return false;
}

Traversing/Searching with DFS

Easier to preserve the path.

Runs on $O(V+E)$.

function dfs(graph: WeightedAdjListWithSeen, source: number, needle: number): boolean {
    const stack: number[] = [source];
    
    while (stack.length) {
        const currNode = stack.pop();
        if (currNode === needle) return true;
        graph[currNode].seen = true;
        for (let neighbor of graph[currNode].edges) {
            if (!graph[neighbor.to]?.seen) stack.push(neighbor.to);
        }
    }
    return false;
}

Adjacent Matrix

A matrix, where each main index of the first array points to a node of the graph, describing in a second array the weights to the other nodes or zero if there is no connection.

Uses more memory, since it represents non-existent connections with zero.

Traversing/Searching with BFS

type WeightedAdjMatrix = number[][];

function bfs(graph: WeightedAdjMatrix, source: number, needle: number): boolean {
    const queue: number[] = [source];
    const seen: boolean[] = new Array(graph.length).fill(false);
    
    while (queue.length) {
        const currNode = queue.shift();
        if (currNode === needle) return true;
        seen[currNode] = true;
        for (let neighbor=0; neighbor < graph[currNode].length; neighbor++) {
            if (graph[currNode][neighbor] !== 0 && !seen[neighbor]) queue.push(neighbor);
        }
    }
    return false;
}

Dijkstra's Shortest Path

An algorithm to find shortest path, meaning find the edge connections with smallest weight.

Don't use negative weight.

Array Solution

This algorithm will run on $O(V² + E)$ because of the way it uses to get the next lowest unseen node.

seen array has size V, and the while loop will run for each node on the graph in worst case, making it $V*V$.

A way to make it run on $O(logV)$ would be to use a minHeap to hold the weights.

Getting the next lowest unseen would be $O(1)$, and there would be no reason for the seen array since the seen nodes would be removed from the heap.

function hasUnvisited(seen: boolean[], weights: number[]): boolean {
    return seen.some((v, nodeI) => !v && weights[nodeI] < Infinity);
}

function getLowestUnvisited(seen: boolean[], weights: number[]): number {
    let idx = -1;
    let lowestDistance = Infinity;

    for (let i = 0; i < seen.length; i++) {
        if (seen[i]) continue;
        if (lowestDistance > weights[i]) {
            lowestDistance = weights[i];
            idx = i;
        }
    }
    return idx;
}

function dijkstra(graph: WeightedAdjList, source: number, target: number): number[] {
    const seen = new Array(graph.length).fill(false);
    const weights = new Array(graph.length).fill(Infinity);
    const path = new Array(graph.length).fill(-1);

    weights[source] = 0;
    while (hasUnvisited(seen, weights)) {
        const curr = getLowestUnvisited(seen, weights);
        seen[curr] = true;

        for (let edge of graph[curr]) {
            if (seen[edge.to]) continue;
            const carriedWeight = weights[curr] + edge.weight;
            if (carriedWeight < weights[edge.to]) {
                weights[edge.to] = carriedWeight;
                path[edge.to] = curr;
            }
        }
    }

    const bestPath: number[] = [];
    let bestCurr = target;
    while (path[bestCurr] !== -1) {
        bestPath.push(bestCurr);
        bestCurr = path[bestCurr];
    }
    bestPath.push(source);
    return bestPath.reverse();
}

The way this specific algorithm works is

1. Will start from the source node (Ex.: Node 0), and check how much it costs to go to each of the unseen neighbors (Node 1 and Node 2).

   1. After this check it will save:

      1. In weights how much it costs to get to Node 1 = 1 and Node 2 = 5.

      2. In path it will have that the best way yet to get to Node 1 and Node 2 is from Node 0.

2. Then it will check the next unseen node that has the lowest weight in weights. (So it will try to stay on the best path). In this example it will check now Node 1, and its unseen neighbors.

   1. After the check:

      1. In weights it will have that to get to Node 2 = 7 and Node 3 = 1. But we already know that there is a better path for Node 2 which is from Node 0, so reaching Node 2 from Node 1 is ignored.

      2. In path we have now that reaching Node 1 & 2 should be from Node 0 and reaching Node 3 should be from Node 1.

3. Step 2 is repeated until there are no more unseen nodes. The algorithm will prioritize paths with lowest weight and will override them if a better one is found.

4. At the end it just reconstruct the path to return it.

Heap Solution