Graflarni amalga oshirish

Grafni oddiy tarzda amalga oshirish

Graf ustida algoritmlarni ishga tushirishdan oldin avval uni qandaydir tarzda amalga oshirishimiz kerak.

Grafni amalga oshirish uchun quyidagiga o‘xshash qo‘shnilik matritsasidan foydalanamiz.

Har bir cho‘qqi uchun ma’lumotlarni, bu holatda A, B, C va D harflarini saqlash uchun ma’lumotlar qo‘shnilik matritsasidagi indekslarga mos keladigan alohida massivga quyidagicha joylashtiriladi:

vertexData = [ 'A', 'B', 'C', 'D']

Yuqoridagi rasmdagi kabi yo‘naltirilmagan va vaznsiz graf uchun i va j cho‘qqilar orasidagi qirra 1 qiymati bilan saqlanadi. U (j,i) va (i,j) ikkala joyda ham 1 sifatida saqlanadi, chunki qirra ikkala yo‘nalishda ham boradi. Ko‘rib turganingizdek, bunday yo‘naltirilmagan graflar uchun matritsa diagonal bo‘yicha simmetrik bo‘ladi.

Keling, aniqroq misolni ko‘rib chiqaylik. Yuqoridagi qo‘shnilik matritsasida A cho‘qqisi 0 indeksida, D cho‘qqisi esa 3 indeksida, shuning uchun A va D orasidagi qirra (0,3) va (3,0) pozitsiyalarida 1 qiymati sifatida saqlanadi, chunki qirra ikkala yo‘nalishda ham boradi.

Quyida yuqoridagi rasmdagi yo‘naltirilmagan grafning oddiy amalga oshirilishi berilgan.

vertexData = ['A', 'B', 'C', 'D']

adjacency_matrix = [
    [0, 1, 1, 1],  # Edges for A
    [1, 0, 1, 0],  # Edges for B
    [1, 1, 0, 0],  # Edges for C
    [1, 0, 0, 0]   # Edges for D
]

def print_adjacency_matrix(matrix):
    print("\nAdjacency Matrix:")
    for row in matrix:
        print(row)

print('vertexData:',vertexData)
print_adjacency_matrix(adjacency_matrix)

Bu amalga oshirish asosan shunchaki ikki o‘lchovli massiv, ammo biz hozirgina amalga oshirgan grafda cho‘qqilar qirralar orqali qanday bog‘langanini yaxshiroq tushunish uchun ushbu funksiyani ishga tushirishimiz mumkin:

def print_connections(matrix, vertices):
    print("\nConnections for each vertex:")
    for i in range(len(vertices)):
        print(f"{vertices[i]}: ", end="")
        for j in range(len(vertices)):
            if matrix[i][j]:  # if there is a connection
                print(vertices[j], end=" ")
        print()  # new line

Grafni sinflar yordamida amalga oshirish

Grafni saqlashning to‘g‘riroq usuli — sinflar yordamida abstraksiya qatlamini qo‘shish, shunda grafning cho‘qqilari, qirralari va tegishli metodlari, masalan, keyinroq amalga oshiradigan algoritmlarimiz bir joyda jamlanadi.

Python va Java kabi o‘rnatilgan obyektga yo‘naltirilgan funksionallikka ega dasturlash tillari graflarni sinflar yordamida amalga oshirishni bunday o‘rnatilgan funksionallikka ega bo‘lmagan C kabi tillarga qaraganda ancha osonlashtiradi.

Yuqoridagi yo‘naltirilmagan grafni sinflar yordamida quyidagicha amalga oshirish mumkin.

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}")

g = Graph(4)
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_edge(0, 1)  # A - B
g.add_edge(0, 2)  # A - C
g.add_edge(0, 3)  # A - D
g.add_edge(1, 2)  # B - C

g.print_graph()

Yuqoridagi kodda yo‘naltirilmagan graflar uchun hosil bo‘ladigan matritsa simmetriyasi 9 va 10-qatorlarda ta’minlanadi va bu 29–32-qatorlarda grafdagi qirralarni initsializatsiya qilishda bizga biroz kod tejash imkonini beradi.

Yo‘naltirilgan va vaznli graflarni amalga oshirish

Yo‘naltirilgan va vaznli grafni amalga oshirish uchun yo‘naltirilmagan grafning oldingi amalga oshirilishiga bir nechta o‘zgartirish kiritishimiz kifoya.

Yo‘naltirilgan graflar yaratish uchun oldingi misol kodidagi 10-qatorni olib tashlashimiz kifoya, shunda matritsa endi avtomatik ravishda simmetrik bo‘lmaydi.

Kiritishimiz kerak bo‘lgan ikkinchi o‘zgarish — add_edge() metodiga weight argumentini qo‘shish, shunda ikki cho‘qqi orasida qirra borligini bildirish uchun shunchaki 1 qiymatidan foydalanish o‘rniga qirrani aniqlash uchun haqiqiy vazn qiymatidan foydalanamiz.

Quyida yuqoridagi yo‘naltirilgan va vaznli grafning amalga oshirilishi berilgan.

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

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

    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(lambda x: str(x) if x is not None else '0', row)))
        print("\nVertex Data:")
        for vertex, data in enumerate(self.vertex_data):
            print(f"Vertex {vertex}: {data}")

g = Graph(4)
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_edge(0, 1, 3)  # A -> B with weight 3
g.add_edge(0, 2, 2)  # A -> C with weight 2
g.add_edge(3, 0, 4)  # D -> A with weight 4
g.add_edge(2, 1, 1)  # C -> B with weight 1

g.print_graph()

3-qator: Dastlab barcha qirralar Nonega o‘rnatiladi.

7-qator: Endi qo‘shimcha weight argumenti yordamida qirraga vazn qo‘shish mumkin.

10-qator: 10-qatorni olib tashlash orqali grafni endi yo‘naltirilgan qilib sozlash mumkin.

Keyingi sahifada graflarni qanday aylanib chiqish mumkinligini ko‘ramiz, undan keyingi sahifalarda esa graf ma’lumotlar tuzilmasida ishlashi mumkin bo‘lgan turli algoritmlarni ko‘rib chiqamiz.

The edges, and edge weights, 
in a graph are normally 
implemented in an  matrix.