DSA graflarni aylanib chiqish

Graflarni aylanib chiqish

Grafni aylanib chiqish — bitta cho‘qqidan boshlab, barcha cho‘qqilarga yoki iloji boricha ko‘prog‘iga tashrif buyurilmaguncha qirralar bo‘ylab boshqa cho‘qqilarga borish demakdir.

Grafni qanday aylanib chiqish mumkinligini tushunish graflarda ishlaydigan algoritmlar qanday ishlashini tushunish uchun muhim.

Grafni aylanib chiqishning eng keng tarqalgan ikki usuli:

• Chuqurlik bo‘yicha qidiruv (Depth First Search, DFS)
• Kenglik bo‘yicha qidiruv (Breadth First Search, BFS)

DFS odatda stek yordamida yoki rekursiya (u chaqiruvlar stekidan foydalanadi) orqali amalga oshiriladi, BFS esa odatda navbat yordamida amalga oshiriladi.

Chuqurlik bo‘yicha qidiruv orqali aylanib chiqish

Chuqurlik bo‘yicha qidiruv "chuqur" ketadi deyiladi, chunki u cho‘qqiga, so‘ngra qo‘shni cho‘qqiga, keyin o‘sha cho‘qqining qo‘shni cho‘qqisiga va hokazo tashrif buyuradi va shu tarzda har bir rekursiv iteratsiyada boshlang‘ich cho‘qqidan masofa ortib boradi.

Chuqurlik bo‘yicha qidiruv (DFS) orqali aylanib chiqish muayyan grafda D cho‘qqisidan boshlab qanday bajarilishini ko‘rish uchun quyidagi animatsiyani ishga tushiring (u oldingi animatsiya bilan bir xil).

DFS aylanib chiqish D cho‘qqisidan boshlanadi va D cho‘qqisini tashrif buyurilgan deb belgilaydi. So‘ngra tashrif buyurilgan har bir yangi cho‘qqi uchun aylanib chiqish metodi hali tashrif buyurilmagan barcha qo‘shni cho‘qqilarda rekursiv chaqiriladi. Shuning uchun yuqoridagi animatsiyada A cho‘qqisiga tashrif buyurilganda aylanib chiqish davom etadigan keyingi cho‘qqi C yoki E cho‘qqisi bo‘ladi (amalga oshirishga bog‘liq).

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):
        visited[v] = True
        print(self.vertex_data[v], end=' ')

        for i in range(self.size):
            if self.adj_matrix[v][i] == 1 and not visited[i]:
                self.dfs_util(i, visited)

    def dfs(self, start_vertex_data):
        visited = [False] * self.size
        start_vertex = self.vertex_data.index(start_vertex_data)
        self.dfs_util(start_vertex, visited)

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("\nDepth First Search starting from vertex D:")
g.dfs('D')

60-qator: DFS aylanib chiqish dfs() metodi chaqirilganda boshlanadi.

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

35-qator: visited massivi dfs_util() metodiga argument sifatida yuboriladi. visited massivi bu tarzda argument sifatida yuborilganda dfs_util() metodiga aslida qiymatlari bor massivning o‘zi emas, balki visited massiviga havola yuboriladi. Shuning uchun dasturimizda har doim faqat bitta visited massivi bo‘ladi va dfs_util() metodi tugunlarga tashrif buyurilgan sari unga o‘zgartirishlar kiritishi mumkin (25-qator).

28–30-qatorlar: Joriy v cho‘qqi uchun barcha qo‘shni tugunlar, agar ularga hali tashrif buyurilmagan bo‘lsa, rekursiv chaqiriladi.

Kenglik bo‘yicha qidiruv orqali aylanib chiqish

Kenglik bo‘yicha qidiruv qo‘shni cho‘qqilarning qo‘shni cho‘qqilariga tashrif buyurishdan oldin cho‘qqining barcha qo‘shni cho‘qqilariga tashrif buyuradi. Bu boshlang‘ich cho‘qqidan bir xil masofadagi cho‘qqilarga boshlang‘ich cho‘qqidan uzoqroqdagi cho‘qqilardan oldin tashrif buyurilishini anglatadi.

Kenglik bo‘yicha qidiruv (BFS) orqali aylanib chiqish muayyan grafda D cho‘qqisidan boshlab qanday bajarilishini ko‘rish uchun quyidagi animatsiyani ishga tushiring.

Yuqoridagi animatsiyada ko‘rib turganingizdek, BFS aylanib chiqish uzoqroqdagi cho‘qqilarga tashrif buyurishdan oldin boshlang‘ich cho‘qqidan bir xil masofadagi cho‘qqilarga tashrif buyuradi. Masalan, A cho‘qqisiga tashrif buyurilgandan so‘ng B, F va G cho‘qqilaridan oldin E va C cho‘qqilariga tashrif buyuriladi, chunki o‘sha cho‘qqilar uzoqroqda joylashgan.

Kenglik bo‘yicha qidiruv orqali aylanib chiqish barcha qo‘shni cho‘qqilarni (agar ularga hali tashrif buyurilmagan bo‘lsa) navbatga qo‘yish, so‘ngra keyingi cho‘qqiga tashrif buyurish uchun navbatdan foydalanish orqali shu tarzda ishlaydi.

Kenglik bo‘yicha qidiruv orqali aylanib chiqish uchun ushbu kod misoli bfs() metodidan tashqari yuqoridagi chuqurlik bo‘yicha qidiruv kod misoli bilan bir xil:

def bfs(self, start_vertex_data):
    queue = [self.vertex_data.index(start_vertex_data)]
    visited = [False] * self.size
    visited[queue[0]] = True
          
    while queue:
        current_vertex = queue.pop(0)
        print(self.vertex_data[current_vertex], end=' ')
      
        for i in range(self.size):
            if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
                queue.append(i)
                visited[i] = True

2–4-qatorlar: bfs() metodi boshlang‘ich cho‘qqi joylashgan navbatni yaratish, visited massivini yaratish va boshlang‘ich cho‘qqini tashrif buyurilgan deb belgilash bilan boshlanadi.

6–13-qatorlar: BFS aylanib chiqish navbatdan cho‘qqini olish, uni chop etish va qo‘shni cho‘qqilarni, agar ularga hali tashrif buyurilmagan bo‘lsa, navbatga qo‘shish, so‘ngra shu tarzda navbatdan cho‘qqilarni olishda davom etish orqali ishlaydi. Navbatdagi oxirgi elementning tashrif buyurilmagan qo‘shni cho‘qqilari qolmaganda aylanib chiqish tugaydi.

Yo‘naltirilgan grafni DFS va BFS orqali aylanib chiqish

Chuqurlik bo‘yicha va kenglik bo‘yicha aylanib chiqishlarni aslida juda kam o‘zgartirishlar bilan (yo‘naltirilmagan graflar o‘rniga) yo‘naltirilgan graflarda ishlaydigan qilib amalga oshirish mumkin.

Yo‘naltirilgan grafni DFS yoki BFS yordamida qanday aylanib chiqish mumkinligini ko‘rish uchun quyidagi animatsiyani ishga tushiring.

Yo‘naltirilmagan graf o‘rniga yo‘naltirilgan grafni aylanib chiqishga o‘tish uchun add_edge() metodidagi oxirgi qatorni olib tashlashimiz kifoya:

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

Grafni qurishda ham ehtiyot bo‘lishimiz kerak, chunki endi qirralar yo‘naltirilgan.

Quyidagi kod misolida yuqoridagi animatsiyadagi yo‘naltirilgan grafni BFS va DFS orqali aylanib chiqishning ikkalasi ham mavjud:

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):
        visited[v] = True
        print(self.vertex_data[v], end=' ')

        for i in range(self.size):
            if self.adj_matrix[v][i] == 1 and not visited[i]:
                self.dfs_util(i, visited)

    def dfs(self, start_vertex_data):
        visited = [False] * self.size

        start_vertex = self.vertex_data.index(start_vertex_data)
        self.dfs_util(start_vertex, visited)
        
    def bfs(self, start_vertex_data):
        queue = [self.vertex_data.index(start_vertex_data)]
        visited = [False] * self.size
        visited[queue[0]] = True
        
        while queue:
            current_vertex = queue.pop(0)
            print(self.vertex_data[current_vertex], end=' ')
            
            for i in range(self.size):
                if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
                    queue.append(i)
                    visited[i] = True

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(3, 4)  # D -> E
g.add_edge(4, 0)  # E -> A
g.add_edge(0, 2)  # A -> C
g.add_edge(2, 5)  # C -> F
g.add_edge(2, 6)  # C -> G
g.add_edge(5, 1)  # F -> B
g.add_edge(1, 2)  # B -> C

g.print_graph()

print("\nDepth First Search starting from vertex D:")
g.dfs('D')

print("\n\nBreadth First Search starting from vertex D:")
g.bfs('D')

Graflarni aylanib chiqish bo‘yicha ikkita asosiy algoritmni ko‘rib chiqqanimizdan so‘ng, keyingi sahifalarda graf ma’lumotlar tuzilmasida boshqa algoritmlar qanday ishlashi mumkinligini ko‘rib chiqamiz.