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;
}