DSA siklni aniqlash

Graflardagi sikllar

Grafdagi sikl — bir xil cho‘qqida boshlanib, o‘sha cho‘qqida tugaydigan va hech bir qirra takrorlanmaydigan yo‘l. Bu labirint bo‘ylab yurib, aynan boshlagan joyingizga qaytib kelishga o‘xshaydi.

Sikl vaziyatga qarab biroz boshqacha ta’riflanishi mumkin. Masalan, qirra bitta cho‘qqidan chiqib, yana o‘sha cho‘qqiga keladigan o‘z-o‘ziga halqa (self-loop) hal qilmoqchi bo‘lgan masalangizga qarab sikl deb hisoblanishi yoki hisoblanmasligi mumkin.

Siklni aniqlash

Graflarda sikllarni aniqlay olish muhim, chunki sikllar tarmoqlar, rejalashtirish va elektron sxemalarni loyihalash kabi ko‘plab sohalarda muammolar yoki alohida holatlarni ko‘rsatishi mumkin.

Sikllarni aniqlashning eng keng tarqalgan ikki usuli:

1. Chuqurlik bo‘yicha qidiruv (DFS): DFS aylanib chiqish grafni o‘rganadi va cho‘qqilarni tashrif buyurilgan deb belgilaydi. Joriy cho‘qqining allaqachon tashrif buyurilgan qo‘shni cho‘qqisi bo‘lsa, sikl aniqlanadi.
2. Union-Find: Bu usul dastlab har bir cho‘qqini guruh, ya’ni qism to‘plam sifatida belgilash orqali ishlaydi. So‘ngra har bir qirra uchun bu guruhlar birlashtiriladi. Har safar yangi qirra o‘rganilganda, agar ikki cho‘qqi allaqachon bitta guruhga tegishli bo‘lsa, sikl aniqlanadi.

DFS va Union-Find yordamida siklni aniqlash qanday ishlashi va ular qanday amalga oshirilishi quyida batafsilroq tushuntirilgan.

Yo‘naltirilmagan graflar uchun DFS yordamida siklni aniqlash

Yo‘naltirilmagan grafda chuqurlik bo‘yicha qidiruv (DFS) yordamida sikllarni aniqlash uchun oldingi sahifadagi DFS aylanib chiqish kodiga juda o‘xshash, faqat bir nechta o‘zgartirish kiritilgan koddan foydalanamiz.

DFS yordamida siklni aniqlash muayyan grafda A cho‘qqisidan boshlab qanday ishlashini ko‘rish uchun quyidagi animatsiyani ishga tushiring (bu oldingi animatsiya bilan bir xil).

DFS aylanib chiqish A cho‘qqisidan boshlanadi, chunki u qo‘shnilik matritsasidagi birinchi cho‘qqi. So‘ngra tashrif buyurilgan har bir yangi cho‘qqi uchun aylanib chiqish metodi hali tashrif buyurilmagan barcha qo‘shni cho‘qqilarda rekursiv chaqiriladi. F cho‘qqisiga tashrif buyurilib, uning qo‘shni cho‘qqisi C’ga allaqachon tashrif buyurilgani aniqlanganda sikl aniqlanadi.

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):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = 1
            self.adj_matrix[v][u] = 1

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

    def print_graph(self):
        print("Adjacency Matrix:")
        for row in self.adj_matrix:
            print(' '.join(map(str, row)))
        print("\nVertex Data:")
        for vertex, data in enumerate(self.vertex_data):
            print(f"Vertex {vertex}: {data}")
            
    def dfs_util(self, v, visited, parent):
        visited[v] = True

        for i in range(self.size):
            if self.adj_matrix[v][i] == 1:
                if not visited[i]:
                    if self.dfs_util(i, visited, v):
                        return True
                elif parent != i:
                    return True
        return False

    def is_cyclic(self):
        visited = [False] * self.size
        for i in range(self.size):
            if not visited[i]:
                if self.dfs_util(i, visited, -1):
                    return True
        return False

g = Graph(7)

g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')

g.add_edge(3, 0)  # D - A
g.add_edge(0, 2)  # A - C
g.add_edge(0, 3)  # A - D
g.add_edge(0, 4)  # A - E
g.add_edge(4, 2)  # E - C
g.add_edge(2, 5)  # C - F
g.add_edge(2, 1)  # C - B
g.add_edge(2, 6)  # C - G
g.add_edge(1, 5)  # B - F

g.print_graph()

print("\nGraph has cycle:", g.is_cyclic())

66-qator: DFS yordamida siklni aniqlash is_cyclic() metodi chaqirilganda boshlanadi.

37-qator: visited massivi dastlab barcha cho‘qqilar uchun falsega o‘rnatiladi, chunki bu nuqtada hali hech bir cho‘qqiga tashrif buyurilmagan.

38–42-qatorlar: DFS yordamida siklni aniqlash grafdagi barcha cho‘qqilarda ishga tushiriladi. Bu graf bog‘lamli bo‘lmagan holatda barcha cho‘qqilarga tashrif buyurilishini ta’minlash uchun kerak. Agar tugunga allaqachon tashrif buyurilgan bo‘lsa, sikl bo‘lishi shart va True qaytariladi. Agar barcha tugunlarga faqat bir martadan tashrif buyurilgan bo‘lsa, ya’ni hech qanday sikl aniqlanmasa, False qaytariladi.

24–34-qatorlar: Bu DFS yordamida siklni aniqlashning cho‘qqiga tashrif buyuradigan, so‘ngra qo‘shni cho‘qqilarga rekursiv tashrif buyuradigan qismi. Agar qo‘shni cho‘qqiga allaqachon tashrif buyurilgan bo‘lsa va u ota tugun bo‘lmasa, sikl aniqlanadi va True qaytariladi.

Yo‘naltirilgan graflar uchun DFS yordamida siklni aniqlash

Yo‘naltirilgan graflarda sikllarni aniqlash uchun algoritm yo‘naltirilmagan graflardagiga hali ham juda o‘xshash, ammo kodni biroz o‘zgartirish kerak, chunki yo‘naltirilgan grafda allaqachon tashrif buyurilgan qo‘shni tugunga kelsak, bu albatta sikl borligini anglatmaydi.

Siklni aniqlashga urinib, ikkita yo‘l o‘rganiladigan quyidagi grafni ko‘rib chiqing:

O‘rganiladigan birinchi yo‘l — 1-yo‘lda A->B->C cho‘qqilariga tashrif buyuriladi, sikllar aniqlanmaydi.

O‘rganiladigan ikkinchi yo‘lda (2-yo‘l) D->B->C cho‘qqilariga tashrif buyuriladi va bu yo‘lda sikllar yo‘q, to‘g‘rimi? Ammo dasturimizga o‘zgartirish kiritilmasa, D’dan qo‘shni B cho‘qqisiga o‘tishda aslida soxta sikl aniqlanadi, chunki B’ga 1-yo‘lda allaqachon tashrif buyurilgan. Bunday soxta aniqlashlarning oldini olish uchun kod faqat tugunga aynan shu yo‘lda avval tashrif buyurilgan holatdagina siklni aniqlaydigan qilib o‘zgartiriladi.

Yuqoridagi animatsiyadagi kabi yo‘naltirilgan grafda DFS yordamida siklni aniqlashni amalga oshirish uchun yo‘naltirilmagan graflarning qo‘shnilik matritsasidagi simmetriyani olib tashlashimiz kerak. Shuningdek, joriy rekursiv yo‘lda tashrif buyurilgan cho‘qqilarni kuzatib borish uchun recStack massividan foydalanishimiz kerak.

class Graph:
    # ......
    def add_edge(self, u, v):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = 1
            self.adj_matrix[v][u] = 1
    # ......
    def dfs_util(self, v, visited, recStack):
        visited[v] = True
        recStack[v] = True
        print("Current vertex:",self.vertex_data[v])

        for i in range(self.size):
            if self.adj_matrix[v][i] == 1:
                if not visited[i]:
                    if self.dfs_util(i, visited, recStack):
                        return True
                elif recStack[i]:
                    return True
        
        recStack[v] = False
        return False

    def is_cyclic(self):
        visited = [False] * self.size
        recStack = [False] * self.size
        for i in range(self.size):
            if not visited[i]:
                print() #new line
                if self.dfs_util(i, visited, recStack):
                    return True
        return False

g = Graph(7)

# ......

g.add_edge(3, 0)  # D -> A
g.add_edge(0, 2)  # A -> C
g.add_edge(2, 1)  # C -> B
g.add_edge(2, 4)  # C -> E
g.add_edge(1, 5)  # B -> F
g.add_edge(4, 0)  # E -> A
g.add_edge(2, 6)  # C -> G

g.print_graph()

print("Graph has cycle:", g.is_cyclic())

6-qator: Bu qator olib tashlanadi, chunki u faqat yo‘naltirilmagan graflar uchun qo‘llaniladi.

26-qator: recStack massivi yo‘lni rekursiv o‘rganish davomida qaysi cho‘qqilarga tashrif buyurilganini kuzatib boradi.

14–19-qatorlar: Avval tashrif buyurilmagan har bir qo‘shni cho‘qqi uchun DFS yordamida rekursiv siklni aniqlashni bajaring. Agar qo‘shni cho‘qqiga avval, bundan tashqari aynan shu rekursiv yo‘lda tashrif buyurilgan bo‘lsa (13-qator), sikl topilgan bo‘ladi va True qaytariladi.

Union-Find yordamida siklni aniqlash

Union-Find yordamida sikllarni aniqlash chuqurlik bo‘yicha qidiruvdan foydalanishdan juda farq qiladi.

Union-Find yordamida siklni aniqlash avval har bir tugunni o‘zining qism to‘plamiga (xalta yoki konteyner kabi) joylashtirish orqali ishlaydi. So‘ngra har bir qirra uchun har bir cho‘qqiga tegishli qism to‘plamlar birlashtiriladi. Agar qirraning cho‘qqilari allaqachon bitta qism to‘plamga tegishli bo‘lsa, bu sikl topilganini anglatadi.

Yuqoridagi animatsiyada Union-Find yordamida siklni aniqlash grafdagi qirralarni o‘rganadi. Qirralar o‘rganilgan sari A cho‘qqisining qism to‘plami kengayib, B, C va D cho‘qqilarini ham o‘z ichiga oladi. A va D orasidagi qirra o‘rganilib, A ham, D ham allaqachon bitta qism to‘plamga tegishli ekani aniqlanganda sikl aniqlanadi.

D, E va F orasidagi qirralar ham aylana hosil qiladi, ammo bu aylana aniqlanmaydi, chunki algoritm birinchi aylana aniqlanganda to‘xtaydi (True qaytaradi).

Union-Find yordamida siklni aniqlash faqat yo‘naltirilmagan graflar uchun qo‘llaniladi.

Union-Find yordamida siklni aniqlash qo‘shnilik matritsasi orqali ifodalash yordamida amalga oshiriladi, shuning uchun graf tuzilmasini cho‘qqilar va qirralar bilan sozlash asosan oldingi misollardagi bilan bir xil.

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size
        self.parent = [i for i in range(size)]  # Union-Find array

    def add_edge(self, u, v):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = 1
            self.adj_matrix[v][u] = 1

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

    def find(self, i):
        if self.parent[i] == i:
            return i
        return self.find(self.parent[i])

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        print('Union:',self.vertex_data[x],'+',self.vertex_data[y])
        self.parent[x_root] = y_root
        print(self.parent,'\n')

    def is_cyclic(self):
        for i in range(self.size):
            for j in range(i + 1, self.size):
                if self.adj_matrix[i][j]:
                    x = self.find(i)
                    y = self.find(j)
                    if x == y:
                        return True
                    self.union(x, y)
        return False

g = Graph(7)

g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')

g.add_edge(1, 0)  # B - A
g.add_edge(0, 3)  # A - D
g.add_edge(0, 2)  # A - C
g.add_edge(2, 3)  # C - D
g.add_edge(3, 4)  # D - E
g.add_edge(3, 5)  # D - F
g.add_edge(3, 6)  # D - G
g.add_edge(4, 5)  # E - F

print("Graph has cycle:", g.is_cyclic())

6-qator: parent massivi har bir qism to‘plam uchun ildiz cho‘qqini saqlaydi. Bu qirraning ikki tomonidagi cho‘qqilar allaqachon bitta qism to‘plamga tegishli ekanini tekshirish orqali siklni aniqlash uchun ishlatiladi.

17-qator: find metodi berilgan cho‘qqi tegishli bo‘lgan to‘plamning ildizini topadi.

22-qator: union metodi ikkita qism to‘plamni birlashtiradi.

29-qator: is_cyclic metodi, agar x va y cho‘qqilari allaqachon bitta qism to‘plamda bo‘lsa, siklni aniqlash uchun find metodidan foydalanadi. Agar sikl aniqlanmasa, qism to‘plamlarni birlashtirish uchun union metodidan foydalaniladi.

A cycle in a Graph is a path 
that starts and ends at the 
same , where no  
are repeated.