DSA Edmonds-Karp

Edmonds-Karp algoritmi

Edmonds-Karp algoritmi yo‘naltirilgan graf uchun maksimal oqim masalasini yechadi.

Oqim manba cho‘qqisidan (\(s\)) chiqadi va quyilish cho‘qqisiga (\(t\)) borib tushadi, grafdagi har bir qirra esa sig‘im bilan cheklangan oqimni o‘tkazadi.

Edmonds-Karp algoritmi Ford-Fulkerson algoritmiga juda o‘xshaydi, faqat Edmonds-Karp algoritmi oqimni oshirish uchun kengaytiruvchi yo‘llarni topishda kenglik bo‘yicha qidiruv (BFS)dan foydalanadi.

Edmonds-Karp algoritmi kenglik bo‘yicha qidiruv (BFS) yordamida manbadan quyilishga qadar bo‘sh sig‘imga ega yo‘lni (u kengaytiruvchi yo‘l — augmented path deb ataladi) topib, so‘ngra shu yo‘l orqali imkon qadar ko‘p oqim yuborish orqali ishlaydi.

Edmonds-Karp algoritmi maksimal oqimga erishilguncha ko‘proq oqim yuborish uchun yangi yo‘llarni topishda davom etadi.

Yuqoridagi simulyatsiyada Edmonds-Karp algoritmi maksimal oqim masalasini yechadi: u \(s\) manba cho‘qqisidan \(t\) quyilish cho‘qqisiga qancha oqim yuborish mumkinligini aniqlaydi va bu maksimal oqim 8 ga teng.

Yuqoridagi simulyatsiyadagi sonlar kasr ko‘rinishida yozilgan: birinchi son — oqim, ikkinchi son esa sig‘im (shu qirradagi mumkin bo‘lgan maksimal oqim). Masalan, \(s \rightarrow v_2\) qirrasidagi 0/7 shu qirrada 0 oqim borligini va uning sig‘imi 7 ekanini bildiradi.

Quyida Edmonds-Karp algoritmi qanday ishlashining asosiy qadamma-qadam tavsifini ko‘rishingiz mumkin, ammo uni chindan tushunish uchun keyinroq batafsilroq to‘xtalishimiz kerak bo‘ladi.

Edmonds-Karp algoritmida qoldiq tarmoq

Edmonds-Karp algoritmi qoldiq tarmoq (residual network) deb ataladigan tuzilmani yaratib, undan foydalanish orqali ishlaydi; u asl grafning o‘ziga xos tasviridir.

Qoldiq tarmoqda har bir qirra qoldiq sig‘imga (residual capacity) ega bo‘lib, u qirraning asl sig‘imidan shu qirradagi oqim ayirilganiga teng. Qoldiq sig‘imni ma’lum oqimga ega qirradagi qolgan bo‘sh sig‘im deb qarash mumkin.

Masalan, agar \( v_3 \rightarrow v_4 \) qirrasida oqim 2 ga, sig‘im esa 3 ga teng bo‘lsa, bu qirradagi qoldiq oqim 1 ga teng, chunki bu qirra orqali yana 1 birlik oqim yuborish uchun joy bor.

Edmonds-Karp algoritmida teskari qirralar

Edmonds-Karp algoritmi oqimni orqaga yuborish uchun teskari qirralar (reversed edges) deb ataladigan narsadan ham foydalanadi. Bu umumiy oqimni oshirish uchun foydali.

Oqimni qirraga qarama-qarshi yo‘nalishda orqaga yuborish uchun tarmoqdagi har bir asl qirra uchun teskari qirra yaratiladi. Shundan so‘ng Edmonds-Karp algoritmi oqimni teskari yo‘nalishda yuborish uchun bu teskari qirralardan foydalana oladi.

Teskari qirraning oqimi ham, sig‘imi ham yo‘q, faqat qoldiq sig‘imi bor. Teskari qirraning qoldiq sig‘imi har doim unga mos asl qirradagi oqimga teng.

Misolimizda \( v_1 \rightarrow v_3 \) qirrasidagi oqim 2 ga teng, demak, unga mos teskari \( v_3 \rightarrow v_1 \) qirrasida qoldiq sig‘im 2 ga teng.

Bu shunchaki asl \( v_1 \rightarrow v_3 \) qirrasida 2 oqim bo‘lganda, xuddi shu miqdordagi oqimni shu qirra bo‘ylab, lekin teskari yo‘nalishda orqaga yuborish imkoniyati borligini bildiradi. Oqimni orqaga surish uchun teskari qirradan foydalanishni allaqachon hosil qilingan oqimning bir qismini bekor qilish deb ham qarash mumkin.

Qirralarda qoldiq sig‘imga ega qoldiq tarmoq g‘oyasi va teskari qirralar g‘oyasi Edmonds-Karp algoritmi ishlashining markazida turadi; algoritmni ushbu sahifada quyiroqda amalga oshirganimizda bu haqda batafsilroq to‘xtalamiz.

Qo‘lda bajarib ko‘rish

Boshida grafda oqim yo‘q.

Edmonds-Karp algoritmi ishni kenglik bo‘yicha qidiruv (Breadth-First Search) yordamida oqimni oshirish mumkin bo‘lgan kengaytiruvchi yo‘lni topishdan boshlaydi; bu yo‘l — \(s \rightarrow v_1 \rightarrow v_3 \rightarrow t\).

Kengaytiruvchi yo‘l topilgach, shu yo‘l orqali qancha oqim yuborish mumkinligini aniqlash uchun tor joy hisoblanadi va bu oqim: 2.

Shunday qilib, kengaytiruvchi yo‘ldagi har bir qirra orqali 2 oqim yuboriladi.

Edmonds-Karp algoritmining keyingi iteratsiyasi quyidagi qadamlarni yana bajarishdan iborat: yangi kengaytiruvchi yo‘lni topish, shu yo‘ldagi oqimni qanchaga oshirish mumkinligini aniqlash va shu yo‘ldagi qirralar bo‘ylab oqimni mos ravishda oshirish.

Keyingi topilgan kengaytiruvchi yo‘l — \(s \rightarrow v_1 \rightarrow v_4 \rightarrow t \).

Bu yo‘lda oqimni faqat 1 ga oshirish mumkin, chunki \( s \rightarrow v_1 \) qirrasida yana atigi bir birlik oqim uchun joy bor.

Keyingi topilgan kengaytiruvchi yo‘l — \(s \rightarrow v_2 \rightarrow v_4 \rightarrow t\).

Bu yo‘lda oqimni 3 ga oshirish mumkin. Tor joy (cheklovchi qirra) — \( v_2 \rightarrow v_4 \), chunki uning sig‘imi 3 ga teng.

Topilgan oxirgi kengaytiruvchi yo‘l — \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow t\).

Bu yo‘lda oqimni faqat 2 ga oshirish mumkin, chunki \( v_4 \rightarrow t \) qirrasi bu yo‘ldagi tor joy bo‘lib, unda yana atigi 2 birlik oqim uchun joy bor (\(capacity-flow=1\)).

Bu bosqichda yangi kengaytiruvchi yo‘lni topib bo‘lmaydi (\(s\) dan \(t\) ga ko‘proq oqim yuborish mumkin bo‘lgan yo‘lni topishning iloji yo‘q), demak maksimal oqim topildi va Edmonds-Karp algoritmi o‘z ishini tugatdi.

Maksimal oqim 8 ga teng. Yuqoridagi rasmda ko‘rib turganingizdek, \(s\) manba cho‘qqisidan chiqayotgan oqim (8) \(t\) quyilish cho‘qqisiga kirayotgan oqimga teng.

Shuningdek, \(s\) yoki \(t\) dan boshqa istalgan cho‘qqini olsangiz, cho‘qqiga kirayotgan oqim miqdori undan chiqayotgan oqimga teng ekanini ko‘rasiz. Buni biz oqimning saqlanishi (conservation of flow) deb ataymiz va bu barcha shunday oqim tarmoqlari (har bir qirrasi oqim va sig‘imga ega yo‘naltirilgan graflar) uchun bajarilishi shart.

Edmonds-Karp algoritmini amalga oshirish

Edmonds-Karp algoritmini amalga oshirish uchun Graph sinfini yaratamiz.

Graph grafni uning cho‘qqilari va qirralari bilan birga ifodalaydi:

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, c):
        self.adj_matrix[u][v] = c

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

3-qator: Barcha qirralar va qirra sig‘imlarini saqlash uchun adj_matrixni yaratamiz. Boshlang‘ich qiymatlar 0ga tenglanadi.

4-qator: size — grafdagi cho‘qqilar soni.

5-qator: vertex_data barcha cho‘qqilarning nomlarini saqlaydi.

7–8-qatorlar: add_edge metodi u cho‘qqisidan v cho‘qqisiga c sig‘imli qirra qo‘shish uchun ishlatiladi.

10–12-qatorlar: add_vertex_data metodi grafga cho‘qqi nomini qo‘shish uchun ishlatiladi. Cho‘qqining indeksi vertex argumenti orqali beriladi, data esa cho‘qqining nomi.

Graph sinfida kenglik bo‘yicha qidiruv (Breadth-First-Search) yordamida kengaytiruvchi yo‘llarni topadigan bfs metodi ham bor:

    def bfs(self, s, t, parent):
        visited = [False] * self.size
        queue = []  # Using list as a queue
        queue.append(s)
        visited[s] = True

        while queue:
            u = queue.pop(0)  # Pop from the start of the list

            for ind, val in enumerate(self.adj_matrix[u]):
                if not visited[ind] and val > 0:
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u

        return visited[t]

15–18-qatorlar: visited massivi kengaytiruvchi yo‘lni qidirish davomida bir xil cho‘qqilarga qayta tashrif buyurmaslikka yordam beradi. queue navbati o‘rganilishi kerak bo‘lgan cho‘qqilarni saqlaydi, qidiruv har doim s manba cho‘qqisidan boshlanadi.

20–21-qatorlar: queue navbatida o‘rganilishi kerak bo‘lgan cho‘qqilar bor ekan, u yerdan keyingi cho‘qqiga yo‘l topish uchun queue navbatidan birinchi cho‘qqini olib chiqing.

23-qator: Joriy cho‘qqiga qo‘shni bo‘lgan har bir cho‘qqi uchun.

24–27-qatorlar: Agar qo‘shni cho‘qqiga hali tashrif buyurilmagan bo‘lsa va shu cho‘qqiga boradigan qirrada qoldiq sig‘im bo‘lsa: uni o‘rganilishi kerak bo‘lgan cho‘qqilar navbatiga qo‘shing, tashrif buyurilgan deb belgilang va qo‘shni cho‘qqining parent qiymatini joriy u cho‘qqisiga tenglang.

parent massivi cho‘qqining otasini saqlab, quyilish cho‘qqisidan orqaga qarab manba cho‘qqisigacha yo‘l hosil qiladi. parent keyinroq Edmonds-Karp algoritmida, bfs metodidan tashqarida, kengaytiruvchi yo‘ldagi oqimni oshirish uchun ishlatiladi.

29-qator: Oxirgi qator visited[t]ni qaytaradi; agar kengaytiruvchi yo‘l t quyilish tugunida tugasa, u true bo‘ladi. true qaytarilishi kengaytiruvchi yo‘l topilganini bildiradi.

edmonds_karp metodi Graph sinfiga qo‘shadigan oxirgi metodimiz:

    def edmonds_karp(self, source, sink):
        parent = [-1] * self.size
        max_flow = 0

        while self.bfs(source, sink, parent):
            path_flow = float("Inf")
            s = sink
            while(s != source):
                path_flow = min(path_flow, self.adj_matrix[parent[s]][s])
                s = parent[s]

            max_flow += path_flow
            v = sink
            while(v != source):
                u = parent[v]
                self.adj_matrix[u][v] -= path_flow
                self.adj_matrix[v][u] += path_flow
                v = parent[v]

            path = []
            v = sink
            while(v != source):
                path.append(v)
                v = parent[v]
            path.append(source)
            path.reverse()
            path_names = [self.vertex_data[node] for node in path]
            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)

        return max_flow

Dastlab parent massivida yaroqsiz indeks qiymatlari bo‘ladi, chunki boshida kengaytiruvchi yo‘l yo‘q; max_flow qiymati 0ga teng va while sikli oqimni oshirish mumkin bo‘lgan kengaytiruvchi yo‘l mavjud ekan, max_flowni oshirishda davom etadi.

35-qator: Tashqi while sikli oqimni oshirish mumkin bo‘lgan kengaytiruvchi yo‘llar mavjud ekan, Edmonds-Karp algoritmi oqimni oshirishda davom etishini ta’minlaydi.

36–37-qatorlar: Kengaytiruvchi yo‘l bo‘ylab boshlang‘ich oqim cheksiz, oqimni mumkin bo‘lgan oshirish miqdori esa quyilish cho‘qqisidan boshlab hisoblanadi.

38–40-qatorlar: path_flow qiymati quyilish cho‘qqisidan manba cho‘qqisi tomon orqaga yurib topiladi. Yo‘l bo‘ylab qoldiq sig‘imning eng kichik qiymati shu yo‘l orqali qancha oqim yuborish mumkinligini belgilaydi.

42-qator: path_flow qiymati path_flow qadar oshiriladi.

44–48-qatorlar: Kengaytiruvchi yo‘l bo‘ylab quyilishdan manbaga qarab orqaga qadamma-qadam yurib, to‘g‘ri qirralarda qoldiq sig‘im path_flow qadar kamaytiriladi, teskari qirralarda esa qoldiq sig‘im path_flow qadar oshiriladi.

50–58-qatorlar: Kodning bu qismi faqat chop etish uchun — shunda har safar kengaytiruvchi yo‘l topilganini va shu yo‘l orqali qancha oqim yuborilganini kuzatib borishimiz mumkin.

Graph sinfini aniqlagach, muayyan grafni initsializatsiya qilish uchun cho‘qqilar va qirralarni aniqlash kerak. Edmonds-Karp algoritmi misolining to‘liq kodi quyidagicha:

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, c):
        self.adj_matrix[u][v] = c

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def bfs(self, s, t, parent):
        visited = [False] * self.size
        queue = []  # Using list as a queue
        queue.append(s)
        visited[s] = True

        while queue:
            u = queue.pop(0)  # Pop from the start of the list

            for ind, val in enumerate(self.adj_matrix[u]):
                if not visited[ind] and val > 0:
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u

        return visited[t]

    def edmonds_karp(self, source, sink):
        parent = [-1] * self.size
        max_flow = 0

        while self.bfs(source, sink, parent):
            path_flow = float("Inf")
            s = sink
            while(s != source):
                path_flow = min(path_flow, self.adj_matrix[parent[s]][s])
                s = parent[s]

            max_flow += path_flow
            v = sink
            while(v != source):
                u = parent[v]
                self.adj_matrix[u][v] -= path_flow
                self.adj_matrix[v][u] += path_flow
                v = parent[v]

            path = []
            v = sink
            while(v != source):
                path.append(v)
                v = parent[v]
            path.append(source)
            path.reverse()
            path_names = [self.vertex_data[node] for node in path]
            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)

        return max_flow

# Example usage:
g = Graph(6)
vertex_names = ['s', 'v1', 'v2', 'v3', 'v4', 't']
for i, name in enumerate(vertex_names):
    g.add_vertex_data(i, name)

g.add_edge(0, 1, 3)  # s  -> v1, cap: 3
g.add_edge(0, 2, 7)  # s  -> v2, cap: 7
g.add_edge(1, 3, 3)  # v1 -> v3, cap: 3
g.add_edge(1, 4, 4)  # v1 -> v4, cap: 4
g.add_edge(2, 1, 5)  # v2 -> v1, cap: 5
g.add_edge(2, 4, 3)  # v2 -> v4, cap: 3
g.add_edge(3, 4, 3)  # v3 -> v4, cap: 3
g.add_edge(3, 5, 2)  # v3 -> t,  cap: 2
g.add_edge(4, 5, 6)  # v4 -> t,  cap: 6

source = 0; sink = 5
print("The maximum possible flow is %d " % g.edmonds_karp(source, sink))

Edmonds-Karp algoritmining vaqt murakkabligi

Edmonds-Karp va Ford-Fulkerson o‘rtasidagi farq shundaki, Edmonds-Karp kengaytiruvchi yo‘llarni topish uchun kenglik bo‘yicha qidiruvdan (BFS), Ford-Fulkerson esa chuqurlik bo‘yicha qidiruvdan (DFS) foydalanadi.

Bu Edmonds-Karp ishlashi uchun ketadigan vaqtni Ford-Fulkersonnikiga qaraganda oldindan aytish osonroq ekanini anglatadi, chunki Edmonds-Karp algoritmiga maksimal oqim qiymati ta’sir qilmaydi.

Cho‘qqilar soni \(V\) va qirralar soni \(E\) bo‘lsa, Edmonds-Karp algoritmining vaqt murakkabligi quyidagiga teng

\[ O(V \cdot E^2) \]

Bu Edmonds-Karp algoritmi Ford-Fulkerson kabi maksimal oqimga emas, balki bizda qancha cho‘qqi va qirra borligiga bog‘liq ekanini anglatadi.

Edmonds-Karp uchun bunday vaqt murakkabligi hosil bo‘lishining sababi shundaki, u vaqt murakkabligi \(O(E+V)\) bo‘lgan BFS’ni ishga tushiradi.

Ammo Edmonds-Karp uchun yomon holatni — qirralar soni \(E\) cho‘qqilar soni \(V\) dan ancha katta bo‘lgan zich grafni faraz qilsak, BFS’ning vaqt murakkabligi \(O(E)\) ga aylanadi.

BFS har bir kengaytiruvchi yo‘l uchun bir marta ishlashi kerak va Edmonds-Karp algoritmi ishlashi davomida aslida \(V \cdot E \) ga yaqin kengaytiruvchi yo‘l topilishi mumkin.

Demak, eng yomon holatda vaqt murakkabligi \(O(E)\) bo‘lgan BFS \(V \cdot E \) martaga yaqin ishlashi mumkin, ya’ni Edmonds-Karp uchun umumiy vaqt murakkabligi quyidagicha bo‘ladi: \( O(V \cdot E \cdot E) = O(V \cdot E^2) \).