TypeScriptgraph.ts
Copy
1
type Graph = Map<number, number[]>;
2
 
3
function buildGraph(edges: [number, number][], directed = false): Graph {
4
  const g: Graph = new Map();
5
  for (const [u, v] of edges) {
6
    if (!g.has(u)) g.set(u, []);
7
    if (!g.has(v)) g.set(v, []);
8
    g.get(u)!.push(v);
9
    if (!directed) g.get(v)!.push(u);
10
  }
11
  return g;
12
}
13
 
14
// BFS — shortest path (unweighted)
15
function bfs(graph: Graph, start: number, end: number): number[] | null {
16
  const queue: number[][] = [[start]];
17
  const visited = new Set([start]);
18
  while (queue.length) {
19
    const path = queue.shift()!;
20
    const node = path[path.length - 1];
21
    if (node === end) return path;
22
    for (const neighbor of graph.get(node) ?? []) {
23
      if (!visited.has(neighbor)) {
24
        visited.add(neighbor);
25
        queue.push([...path, neighbor]);
26
      }
27
    }
28
  }
29
  return null;
30
}
31
 
32
// DFS — connectivity
33
function dfs(graph: Graph, start: number, visited = new Set<number>()): void {
34
  visited.add(start);
35
  for (const neighbor of graph.get(start) ?? []) {
36
    if (!visited.has(neighbor)) dfs(graph, neighbor, visited);
37
  }
38
}
39
 
40
const g = buildGraph([[1,2],[1,3],[2,4],[3,4],[4,5]]);
41
console.log(bfs(g, 1, 5));  // [1, 2, 4, 5] or [1, 3, 4, 5]