Ford-Fulkerson algoritması

Bu eğitimde, Ford-Fulkerson algoritmasının ne olduğunu öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da bir akış ağında maksimum akışı bulmanın çalışma örneklerini bulacaksınız.

Ford-Fulkerson algoritması, bir ağ veya grafikte mümkün olan maksimum akışı hesaplamak için açgözlü bir yaklaşımdır.

Akış ağı terimi, bir kaynak (S) ve bir havuz (T) ile bir köşe ve kenar ağını tanımlamak için kullanılır. S ve T dışındaki her köşe, içinden eşit miktarda malzeme alıp gönderebilir. S yalnızca gönderebilir ve T yalnızca bir şeyler alabilir.

Algoritmanın anlaşılmasını, farklı kapasitelerde bir boru ağı içindeki bir sıvı akışını kullanarak görselleştirebiliriz. Her borunun bir anda aktarabileceği belirli bir sıvı kapasitesi vardır. Bu algoritma için, ağı kullanan bir örnekte kaynaktan havuza ne kadar sıvı akabileceğini bulacağız.

Akış ağı grafiği

Kullanılan Terminolojiler

Yol Artırma

Bir akış ağında mevcut olan yoldur.

Artık Grafik

Ek olası akışa sahip akış ağını temsil eder.

Kalan Kapasite

Maksimum kapasiteden akış çıkarıldıktan sonra kenarın kapasitesidir.

Ford-Fulkerson Algoritması nasıl çalışır?

Algoritma şu şekildedir:

Tüm kenarlardaki akışı 0 olarak başlatın.
Kaynak ve havuz arasında bir artırma yolu varken, bu yolu akışa ekleyin.
Kalan grafiği güncelleyin.

Gerektiğinde ters yolu da düşünebiliriz çünkü onları dikkate almazsak, asla maksimum bir akış bulamayabiliriz.

Yukarıdaki kavramlar aşağıdaki örnekle anlaşılabilir.

Ford-Fulkerson Örneği

Başlangıçta tüm kenarların akışı 0'dır.

Akış ağı grafiği örneği

S'den T'ye rastgele herhangi bir yol seçin. Bu adımda, SABT yolunu seçtik. Bir yol bulun
Üç kenar arasındaki minimum kapasite 2'dir (BT). Buna dayanarak, her yol için akışı / kapasiteyi güncelleyin. Kapasiteleri güncelleyin
Başka bir yol SDCT seçin. Bu kenarlar arasındaki minimum kapasite 3'tür (SD). Sonraki yolu bul
Kapasiteleri buna göre güncelleyin. Kapasiteleri güncelleyin
Şimdi ters yol BD'yi de ele alalım. SABDCT yolunu seçme. Kenarlar arasındaki minimum artık kapasite 1'dir (DC). Sonraki yolu bul
Kapasitelerin güncellenmesi. Kapasiteleri güncelleme
İleri ve geri yollar için kapasite ayrı ayrı ele alınır.
Tüm akışların toplanması = 2 + 3 + 1 = 6, bu akış ağında mümkün olan maksimum akıştır.

Herhangi bir kenar kapasitesi doluysa, o yolun kullanılamayacağını unutmayın.

Python, Java ve C / C ++ Örnekleri

Python Java C C ++

 # Ford-Fulkerson algorith in Python from collections import defaultdict class Graph: def __init__(self, graph): self.graph = graph self. ROW = len(graph) # Using BFS as a searching algorithm def searching_algo_BFS(self, s, t, parent): visited = (False) * (self.ROW) queue = () queue.append(s) visited(s) = True while queue: u = queue.pop(0) for ind, val in enumerate(self.graph(u)): if visited(ind) == False and val> 0: queue.append(ind) visited(ind) = True parent(ind) = u return True if visited(t) else False # Applying fordfulkerson algorithm def ford_fulkerson(self, source, sink): parent = (-1) * (self.ROW) max_flow = 0 while self.searching_algo_BFS(source, sink, parent): path_flow = float("Inf") s = sink while(s != source): path_flow = min(path_flow, self.graph(parent(s))(s)) s = parent(s) # Adding the path flows max_flow += path_flow # Updating the residual values of edges v = sink while(v != source): u = parent(v) self.graph(u)(v) -= path_flow self.graph(v)(u) += path_flow v = parent(v) return max_flow graph = ((0, 8, 0, 0, 3, 0), (0, 0, 9, 0, 0, 0), (0, 0, 0, 0, 7, 2), (0, 0, 0, 0, 0, 5), (0, 0, 7, 4, 0, 0), (0, 0, 0, 0, 0, 0)) g = Graph(graph) source = 0 sink = 5 print("Max Flow: %d " % g.ford_fulkerson(source, sink))

 // Ford-Fulkerson algorith in Java import java.util.LinkedList; class FordFulkerson ( static final int V = 6; // Using BFS as a searching algorithm boolean bfs(int Graph()(), int s, int t, int p()) ( boolean visited() = new boolean(V); for (int i = 0; i < V; ++i) visited(i) = false; LinkedList queue = new LinkedList(); queue.add(s); visited(s) = true; p(s) = -1; while (queue.size() != 0) ( int u = queue.poll(); for (int v = 0; v 0) ( queue.add(v); p(v) = u; visited(v) = true; ) ) ) return (visited(t) == true); ) // Applying fordfulkerson algorithm int fordFulkerson(int graph()(), int s, int t) ( int u, v; int Graph()() = new int(V)(V); for (u = 0; u < V; u++) for (v = 0; v < V; v++) Graph(u)(v) = graph(u)(v); int p() = new int(V); int max_flow = 0; # Updating the residual calues of edges while (bfs(Graph, s, t, p)) ( int path_flow = Integer.MAX_VALUE; for (v = t; v != s; v = p(v)) ( u = p(v); path_flow = Math.min(path_flow, Graph(u)(v)); ) for (v = t; v != s; v = p(v)) ( u = p(v); Graph(u)(v) -= path_flow; Graph(v)(u) += path_flow; ) // Adding the path flows max_flow += path_flow; ) return max_flow; ) public static void main(String() args) throws java.lang.Exception ( int graph()() = new int()() ( ( 0, 8, 0, 0, 3, 0 ), ( 0, 0, 9, 0, 0, 0 ), ( 0, 0, 0, 0, 7, 2 ), ( 0, 0, 0, 0, 0, 5 ), ( 0, 0, 7, 4, 0, 0 ), ( 0, 0, 0, 0, 0, 0 ) ); FordFulkerson m = new FordFulkerson(); System.out.println("Max Flow: " + m.fordFulkerson(graph, 0, 5)); ) )

 / Ford - Fulkerson algorith in C #include #define A 0 #define B 1 #define C 2 #define MAX_NODES 1000 #define O 1000000000 int n; int e; int capacity(MAX_NODES)(MAX_NODES); int flow(MAX_NODES)(MAX_NODES); int color(MAX_NODES); int pred(MAX_NODES); int min(int x, int y) ( return x < y ? x : y; ) int head, tail; int q(MAX_NODES + 2); void enqueue(int x) ( q(tail) = x; tail++; color(x) = B; ) int dequeue() ( int x = q(head); head++; color(x) = C; return x; ) // Using BFS as a searching algorithm int bfs(int start, int target) ( int u, v; for (u = 0; u < n; u++) ( color(u) = A; ) head = tail = 0; enqueue(start); pred(start) = -1; while (head != tail) ( u = dequeue(); for (v = 0; v 0) ( enqueue(v); pred(v) = u; ) ) ) return color(target) == C; ) // Applying fordfulkerson algorithm int fordFulkerson(int source, int sink) ( int i, j, u; int max_flow = 0; for (i = 0; i < n; i++) ( for (j = 0; j = 0; u = pred(u)) ( increment = min(increment, capacity(pred(u))(u) - flow(pred(u))(u)); ) for (u = n - 1; pred(u)>= 0; u = pred(u)) ( flow(pred(u))(u) += increment; flow(u)(pred(u)) -= increment; ) // Adding the path flows max_flow += increment; ) return max_flow; ) int main() ( for (int i = 0; i < n; i++) ( for (int j = 0; j < n; j++) ( capacity(i)(j) = 0; ) ) n = 6; e = 7; capacity(0)(1) = 8; capacity(0)(4) = 3; capacity(1)(2) = 9; capacity(2)(4) = 7; capacity(2)(5) = 2; capacity(3)(5) = 5; capacity(4)(2) = 7; capacity(4)(3) = 4; int s = 0, t = 5; printf("Max Flow: %d", fordFulkerson(s, t)); )

 // Ford-Fulkerson algorith in C++ #include #include #include #include using namespace std; #define V 6 // Using BFS as a searching algorithm bool bfs(int rGraph(V)(V), int s, int t, int parent()) ( bool visited(V); memset(visited, 0, sizeof(visited)); queue q; q.push(s); visited(s) = true; parent(s) = -1; while (!q.empty()) ( int u = q.front(); q.pop(); for (int v = 0; v 0) ( q.push(v); parent(v) = u; visited(v) = true; ) ) ) return (visited(t) == true); ) // Applying fordfulkerson algorithm int fordFulkerson(int graph(V)(V), int s, int t) ( int u, v; int rGraph(V)(V); for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph(u)(v) = graph(u)(v); int parent(V); int max_flow = 0; // Updating the residual values of edges while (bfs(rGraph, s, t, parent)) ( int path_flow = INT_MAX; for (v = t; v != s; v = parent(v)) ( u = parent(v); path_flow = min(path_flow, rGraph(u)(v)); ) for (v = t; v != s; v = parent(v)) ( u = parent(v); rGraph(u)(v) -= path_flow; rGraph(v)(u) += path_flow; ) // Adding the path flows max_flow += path_flow; ) return max_flow; ) int main() ( int graph(V)(V) = ((0, 8, 0, 0, 3, 0), (0, 0, 9, 0, 0, 0), (0, 0, 0, 0, 7, 2), (0, 0, 0, 0, 0, 5), (0, 0, 7, 4, 0, 0), (0, 0, 0, 0, 0, 0)); cout << "Max Flow: " << fordFulkerson(graph, 0, 5) << endl; )