1
2// BFS: кратчайший путь в невзвешенном графе
3function bfsPath(
4    graph: Record<string, string[]>,
5    start: string,
6    isGoal: (name: string) => boolean
7): string[] | null {
8    const queue: string[] = [start];
9    const visited = new Set<string>();
10    const parent = new Map<string, string>();
11    
12    while (queue.length) {
13        const v = queue.shift()!;
14        if (visited.has(v)) continue;
15        visited.add(v);
16
17    if (isGoal(v)) {
18        const path = [v];
19        let cur = v;
20        while (parent.has(cur)) {
21            cur = parent.get(cur)!;
22            path.unshift(cur);
23        }
24        return path;
25    }
26    
27    for (const n of graph[v] ?? []) {
28        if (!visited.has(n)) {
29            if (!parent.has(n)) parent.set(n, v);
30            queue.push(n);
31            }
32        }
33    }
34    return null;
35}
36
37const graph: Record<string, string[]> = {
38  "you": [
39    "alice",
40    "bob",
41    "claire"
42  ],
43  "alice": [
44    "peggy"
45  ],
46  "bob": [
47    "anuj",
48    "peggy"
49  ],
50  "claire": [
51    "thom",
52    "jonny"
53  ],
54  "anuj": [],
55  "peggy": [],
56  "thom": [],
57  "jonny": []
58};
59
60const isSeller = (name: string) => name.endsWith('m');
61const noSuch = (name: string) => name.startsWith('z');
62
63bfsPath(graph, 'you', isSeller) // -> ["you","claire","thom"]
64bfsPath(graph, 'you', noSuch)   // -> null
65