Ford-Fulkerson Algoritması: Maksimum Akış Bulma

10 Mart 2024 • ☕️ 4 dk okuma • 🏷 bilgisayar, yazılım, algoritma, graf, network

Yazar tarafından şu dillere çevrildi: English

Ford-Fulkerson algoritması, ağ teorisinde önemli bir yere sahip olan ve bir ağdaki maksimum akışı belirlemeyi amaçlayan bir graf algoritmasıdır. Akış ağlarındaki bir kaynaktan bir hedefe ulaşan en büyük akışı bulmak için kullanılır. Algoritma bu maksimum akışı bulmak için artan yolları keşfeder ve bu yollar boyunca akışı artırır.

Algoritmanın başlangıç noktası, maksimum akışın sıfır olduğu varsayımıdır. Başlangıçta ağdaki hiçbir akış yoktur ve algoritma bu akışı kademeli olarak artırarak maksimum akışı bulmaya çalışır. Her artış adımında, bir artan yol bulunur ve bu yol boyunca akış artırılır. Bu artan yol, kaynaktan hedefe ulaşan bir yol olup, bu yol boyunca akış artırılabilir. Ford-Fulkerson algoritması, genellikle genişletilmiş Derinlik Öncelikli Arama (DFS) algoritması ile uygulanır. Bu algoritma, ağdaki her bir düğümü ziyaret ederek artan yolları bulur ve akışı artırmak için kullanılır. Algoritmanın karmaşıklığı ağ yapısına ve maksimum akışın boyutuna bağlı olarak değişir. Ancak genellikle zaman karmaşıklığı, ağdaki kenar sayısına ve maksimum akışın büyüklüğüne bağlı olarak ifade edilir.

Nasıl Çalışır?

Başlangıçta maksimum akış sıfır olarak varsayılır.
Artan yollar bulunmaya çalışılır. Artan yol kaynaktan hedefe bir yol olup, bu yol boyunca akış artırılabilir.
Bir artan yol bulunduğunda, bu yol boyunca akış artırılır.
Akış artırılamadığı sürece yani artan yol bulunamadığı durumda, algoritma sona erer.

Çalışma Adımları

Başlangıç Durumu ve Başlangıç Noktası Belirleme:
Ford-Fulkerson algoritması, bir ağdaki maksimum akışı bulmayı amaçlar. Bu süreçte ilk adım, ağın başlangıç durumunu ve başlangıç noktasını belirlemektir. Başlangıç noktası, genellikle ağın kaynağıdır ve akışın başladığı yerdir.
Artan Yolların Bulunması:
Algoritmanın ana işleyişini oluşturan adımlardan biri, artan yolların keşfedilmesidir. Bu adımda, başlangıç noktasından hedef noktaya kadar olan potansiyel artan yollar aranır. Genellikle, genişletilmiş Derinlik Öncelikli Arama (DFS) veya Genişlik Öncelikli Arama (BFS) gibi graf gezme algoritmaları kullanılarak bu artan yollar bulunur.
Artan Yolların Belirlenmesi ve Analizi:
Bulunan artan yollar üzerinde analiz yapılır. Her bir artan yolun kapasitesi belirlenir ve bu kapasiteler arasından en düşük olanı seçilir. Bu, akışın artırılacağı miktarı belirlemek için kullanılır.
Akışın Artırılması:
En zayıf bağlantının kapasitesi kadar akış artırılır. Bu, belirlenen artan yol boyunca akışın güncellenmesi anlamına gelir. Akış, başlangıç noktasından hedef noktaya doğru ilerlerken artırılır.
Yeniden Düzenleme ve Yeniden Değerlendirme:
Akışın artırılmasıyla birlikte, ağdaki kapasiteler güncellenir ve artık kullanılamayan yollar işaretlenir. Bu adımda, akışın güncellenmesi sonucunda ağın yeniden düzenlenmesi ve akışın yeniden değerlendirilmesi gerekebilir.
Tekrarlama ve Sonlandırma:
Artan yolların bulunması, akışın artırılması ve ağın güncellenmesi adımları tekrarlanır. Bu işlem, artık artan yol bulunamadığı ve akış artırılamadığı zaman sona erer. Algoritma, maksimum akış bulunduğunda veya akış artırılamadığında sonlanır.

Algoritma Karmaşıklığı

Ford-Fulkerson algoritmasının karmaşıklığı, genellikle ağ yapısına ve maksimum akış boyutuna bağlıdır. En kötü durumda, zaman karmaşıklığı O(Ef) olabilir. Burada E ağdaki kenar sayısını ve f maksimum akışı temsil eder.

Kullanım Alanları

Ağ akışı yönetimi
Taşıma ve lojistik sistemleri
Telekomünikasyon ağları
Veri iletimi ve ağ optimizasyonu

GoLang’de Ford-Fulkerson Algoritması uygulaması:

package main

import "fmt"

// FordFulkerson is the implementation of Ford-Fulkerson algorithm
func FordFulkerson(graph [][]int, source, sink int) int {
	maxFlow := 0
	parent := make([]int, len(graph))

	for {
		flow := bfs(graph, source, sink, parent)
		if flow == 0 {
			break
		}
		maxFlow += flow

		// Update the residual capacities of the edges and reverse edges along the path
		v := sink
		for v != source {
			u := parent[v]
			graph[u][v] -= flow
			graph[v][u] += flow
			v = u
		}
	}
	return maxFlow
}

// Breadth First Search to find augmenting path
func bfs(graph [][]int, source, sink int, parent []int) int {
	visited := make([]bool, len(graph))
	queue := []int{source}
	visited[source] = true
	parent[source] = -1

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]

		for v, capacity := range graph[u] {
			if !visited[v] && capacity > 0 {
				queue = append(queue, v)
				parent[v] = u
				visited[v] = true
			}
		}
	}
	if visited[sink] {
		pathFlow := 1 << 32
		v := sink
		for v != source {
			u := parent[v]
			pathFlow = min(pathFlow, graph[u][v])
			v = u
		}
		return pathFlow
	}
	return 0
}

// Helper function to find minimum of two integers
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	graph := [][]int{
		{0, 16, 13, 0, 0, 0},
		{0, 0, 10, 12, 0, 0},
		{0, 4, 0, 0, 14, 0},
		{0, 0, 9, 0, 0, 20},
		{0, 0, 0, 7, 0, 4},
		{0, 0, 0, 0, 0, 0},
	}

	source, sink := 0, 5
	maxFlow := FordFulkerson(graph, source, sink)
	fmt.Println("Maximum Flow:", maxFlow)
}

Program çalıştırıldığında çıktısı aşağıdaki gibi olacaktır.

Maximum Flow: 23

Programın çalışır haline şuradan erişilebilir.

Ford-Fulkerson algoritması, bir ağdaki maksimum akışı bulmak için yaygın olarak kullanılan etkili bir algoritmadır. Graf teorisinde önemli bir yere sahiptir ve birçok farklı alanda uygulanabilir. Bu algoritmanın anlaşılması ve uygulanması, ağ optimizasyonu, taşıma ve lojistik problemleri gibi çeşitli alanlarda önemli katkılar sağlayabilir.

hkucuk