Graf Boyama (Graph Coloring & Backtracking) Algoritması

1function isSafe(
2  node: number,
3  graph: number[][],
4  colors: number[],
5  color: number
6): boolean {
7  for (let i = 0; i < graph.length; i++) {
8    // Komşu düğüm aynı renge sahipse güvensizdir
9    if (graph[node][i] === 1 && colors[i] === color) {
10      return false;
11    }
12  }
13  return true;
14}
15
16function colorGraphRec(
17  node: number,
18  graph: number[][],
19  m: number,
20  colors: number[],
21  trace: string[]
22): boolean {
23  if (node === graph.length) return true; // Tüm düğümler boyandı
24
25  for (let c = 1; c <= m; c++) {
26    trace.push(`Düğüm ${node} için Renk ${c} deneniyor...`);
27    if (isSafe(node, graph, colors, c)) {
28      colors[node] = c;
29      trace.push(`  [Renk Atandı] Düğüm ${node} -> Renk ${c}`);
30      
31      if (colorGraphRec(node + 1, graph, m, colors, trace)) return true;
32      
33      trace.push(`  [Geri İzleme - Backtrack] Düğüm ${node} rengi sıfırlanıyor (${c})`);
34      colors[node] = 0; // Backtrack
35    } else {
36      trace.push(`  [Çakışma] Renk ${c} komşularla çakışıyor.`);
37    }
38  }
39  return false;
40}
41
42function solveMColoring(graph: number[][], m: number, trace: string[]): number[] | null {
43  const colors = Array(graph.length).fill(0);
44  if (colorGraphRec(0, graph, m, colors, trace)) {
45    return colors;
46  }
47  return null;
48}