Run results for: graph test

Test name	Executions per second
✓ array	1,285 Ops/sec
map	857 Ops/sec

Tests:

array
const graph = Array.from({ length: 101 }, () => []); for (let i = 0; i < 100; i++) { const a=Math.floor(Math.random() * 100) + 1 graph[i].push(a); graph[a].push(i) } for (let i = 0; i < 100; i++) { const a=Math.floor(Math.random() * 100) + 1 const b=Math.floor(Math.random() * 100) + 1 graph[a].push(b) graph[b].push(a) } function dfs(i) { const stack = [i]; const visited = Array.from({ length: 101 }, () => 0); visited[i] = 1; while (stack.length) { const target = stack.pop(); for (let i = 0; i < graph[target].length; i++) { if (!visited[graph[target][i]]) { stack.push(graph[target][i]); visited[graph[target][i]] = 1; } } } } for (let i = 0; i <100; i++) { dfs(i); }
map
class Graph { constructor() { this.list = new Map(); } add(v1, v2) { if (!this.list.has(v1)) this.list.set(v1, []); if (!this.list.has(v2)) this.list.set(v2, []); this.list.get(v2).push(v1); this.list.get(v1).push(v2); } dfs(start) { const stack = [start]; const visited = new Map(); visited.set(start, true); while (stack.length) { const target = this.list.get(stack.pop()); for (let i = 0; i < target.length; i++) { if (!visited.has(target[i])) { stack.push(target[i]); visited.set(target[i], true); } } } return } } const graph = new Graph(); for (let i = 0; i < 100; i++) { graph.add(i, Math.floor(Math.random() * 100) + 1); } for (let i = 0; i < 100; i++) { graph.add(Math.floor(Math.random() * 100) + 1, Math.floor(Math.random() * 100) + 1); } for (const [num, _] of graph.list) { graph.dfs(num); }