Graf Dolaşma ve Arama (Graph Traversals & Searching) Algoritması

1function hasCycleDFS(adjList: Map, node: number, visited: Set, recStack: Set, parent: number | null = null): boolean {
2  visited.add(node);
3  recStack.add(node);
4
5  const neighbors = adjList.get(node) ?? [];
6  for (const neighbor of neighbors) {
7    if (!visited.has(neighbor)) {
8      if (hasCycleDFS(adjList, neighbor, visited, recStack, node)) return true;
9    } else if (recStack.has(neighbor) && neighbor !== parent) {
10      return true; // Back edge bulduk, çevrim var
11    }
12  }
13
14  recStack.delete(node);
15  return false;
16}
17
18function detectCycle(n: number, edges: [number, number][]): boolean {
19  const adjList = new Map();
20  for (const [u, v] of edges) {
21    if (!adjList.has(u)) adjList.set(u, []);
22    if (!adjList.has(v)) adjList.set(v, []);
23    adjList.get(u)!.push(v);
24    adjList.get(v)!.push(u); // Un-directed graf varsayımı
25  }
26
27  const visited = new Set();
28  const recStack = new Set();
29
30  for (let i = 0; i < n; i++) {
31    if (!visited.has(i)) {
32      if (hasCycleDFS(adjList, i, visited, recStack)) return true;
33    }
34  }
35  return false;
36}