jsschools

Graph

A collection of vertices (nodes) and edges (connections), representing pairwise relationships — directed or undirected, weighted or unweighted.

Spec ↗

Syntax

// Represented as adjacency list (Map of arrays) or adjacency matrix
const graph = new Map();
graph.set('A', [['B', 1], ['C', 4]]);  // weighted directed

Parameters

NameTypeRequiredDescription
vertices Iterable<any> No Initial set of vertex labels.
edges Array<[u, v, weight?]> No Initial edge list. Weight defaults to 1 if omitted.

Returns

Graph — A graph representation (adjacency list or matrix).

Examples

// Build an undirected graph as an adjacency list
function buildGraph(edges) {
  const g = new Map();
  for (const [u, v] of edges) {
    (g.get(u) ?? g.set(u, []).get(u)).push(v);
    (g.get(v) ?? g.set(v, []).get(v)).push(u);
  }
  return g;
}
const g = buildGraph([['A','B'],['A','C'],['B','D'],['C','D'],['D','E']]);
console.log([...g.entries()].map(([k,v]) => `${k}: ${v}`).join('\n'));
Output 
A: B,C
B: A,D
C: A,D
D: B,C,E
E: D

// DFS to detect cycle in a directed graph
function hasCycle(graph) {
  const state = new Map(); // 0=unvisited, 1=in-stack, 2=done
  function dfs(v) {
    state.set(v, 1);
    for (const nb of graph.get(v) ?? []) {
      if (state.get(nb) === 1) return true;
      if (!state.get(nb) && dfs(nb)) return true;
    }
    state.set(v, 2);
    return false;
  }
  for (const v of graph.keys()) if (!state.get(v) && dfs(v)) return true;
  return false;
}
const dg = new Map([['A',['B']], ['B',['C']], ['C',['A']]]);
console.log(hasCycle(dg));
Output 
true

Notes

| Algorithm | Time | Space | |----------|---------------|--------| | BFS/DFS | O(V + E) | O(V) | | Dijkstra | O((V+E) log V)| O(V) | | Bellman-Ford | O(V * E) | O(V) | | Floyd-Warshall| O(V³) | O(V²) | | Prim MST | O((V+E) log V)| O(V) | | Kruskal MST | O(E log E) | O(V) | V = vertices, E = edges. For sparse graphs use adjacency lists (O(V+E) space); for dense graphs use adjacency matrix (O(V²) space but O(1) edge lookup).

See also