Ağ Akışı (Network Flow) Algoritması

1class FordFulkerson {
2  private size: number;
3  private capacities: number[][];
4  private flows: number[][];
5
6  constructor(size: number) {
7    this.size = size;
8    this.capacities = Array.from({ length: size }, () => Array(size).fill(0));
9    this.flows = Array.from({ length: size }, () => Array(size).fill(0));
10  }
11
12  addEdge(u: number, v: number, cap: number) {
13    this.capacities[u][v] = cap;
14  }
15
16  private bfs(s: number, t: number, parent: number[]): boolean {
17    const visited = Array(this.size).fill(false);
18    const queue: number[] = [s];
19    visited[s] = true;
20
21    while (queue.length > 0) {
22      const u = queue.shift()!;
23      for (let v = 0; v < this.size; v++) {
24        const residual = this.capacities[u][v] - this.flows[u][v];
25        if (!visited[v] && residual > 0) {
26          parent[v] = u;
27          visited[v] = true;
28          if (v === t) return true;
29          queue.push(v);
30        }
31      }
32    }
33    return false;
34  }
35
36  getMaxFlow(s: number, t: number, trace?: string[]): number {
37    const parent = Array(this.size).fill(-1);
38    let maxFlow = 0;
39
40    while (this.bfs(s, t, parent)) {
41      let pathFlow = Infinity;
42      // Yol üzerindeki darboğazı bul
43      for (let v = t; v !== s; v = parent[v]) {
44        const u = parent[v];
45        pathFlow = Math.min(pathFlow, this.capacities[u][v] - this.flows[u][v]);
46      }
47
48      if (trace) {
49        const path: number[] = [];
50        for (let v = t; v !== s; v = parent[v]) path.push(v);
51        path.push(s);
52        trace.push(`Yol Bulundu: ${path.reverse().join(' -> ')} (Kapasite: ${pathFlow})`);
53      }
54
55      // Kapasiteleri ve akışları güncelle
56      for (let v = t; v !== s; v = parent[v]) {
57        const u = parent[v];
58        this.flows[u][v] += pathFlow;
59        this.flows[v][u] -= pathFlow;
60      }
61      maxFlow += pathFlow;
62    }
63    return maxFlow;
64  }
65}