Graph Data Structure

Graf (Graph) ma'lumotlar tuzilmasi — bu ma'lumotlarni o'z ichiga olgan va bir-biri bilan qirralar orqali bog'langan tugunlar (cho'qqilar) to'plamidir.

Buni Facebook misolida tushunishga harakat qilaylik. Facebook platformasida har bir narsa bitta tugun (cho'qqi) hisoblanadi. Bu foydalanuvchi (User), fotosurat (Photo), albom (Album), tadbir (Event), guruh (Group), sahifa (Page), izoh (Comment), hikoya (Story), video (Video), havola (Link) yoki eslatma (Note) bo'lishi mumkin — ma'lumotga ega har qanday narsa bu tugundir.

Har qanday munosabat esa bitta tugundan ikkinchisiga yo'nalgan qirra (edge / aloqa) hisoblanadi. Rasm joylashtirasizmi, guruhga a'zo bo'lasizmi, sahifaga "like" bosasizmi — ushbu munosabat uchun yangi qirra hosil qilinadi:

Facebook misolida graf ma'lumotlar tuzilmasi: foydalanuvchilar, guruhlar, sahifalar — tugunlar; do'stlik, a'zolik, "like" bosish — qirralar

Facebook platformasining barcha ma'lumotlari aynan mana shunday tugunlar va qirralar to'plamidir, chunki Facebook o'z ma'lumotlarini saqlash uchun aynan graf ma'lumotlar tuzilmasidan foydalanadi.

Aniqroq aytganda, graf bu (V, E) ko'rinishidagi ma'lumotlar tuzilmasi bo'lib, quyidagilardan tashkil topadi:

• Cho'qqilar (tugunlar) to'plami V (Vertices)
• Cho'qqilarning tartiblangan juftliklari (u, v) ko'rinishida ifodalangan qirralar to'plami E (Edges)

Graf: nuqtalar kabi cho'qqilar (vertices) va ularni tutashtiruvchi qirralar (edges)

Yuqoridagi grafda:

V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}

Graf atamalari

• Qo'shnilik (Adjacency): Agar ikkita cho'qqini tutashtiruvchi qirra mavjud bo'lsa, bu cho'qqilar qo'shni (adjacent) deyiladi. Yuqoridagi grafda 2 va 3 cho'qqilari qo'shni emas, chunki ularning o'rtasida to'g'ridan-to'g'ri qirra yo'q.
• Yo'l (Path): A cho'qqisidan B cho'qqisiga o'tish imkonini beruvchi qirralar ketma-ketligi yo'l (path) deb ataladi. Masalan, 0-1, 1-2 va 0-2 yo'llari 0 cho'qqisidan 2 cho'qqisiga boruvchi yo'llardir.
• Yo'naltirilgan graf (Directed Graph / Digraph): (u, v) qirrasi mavjudligi (v, u) qirrasi ham borligini anglatmaydigan graf. Bunday grafda qirralar ularning yo'nalishini ko'rsatuvchi strelkalar bilan ifodalanadi.
• Yo'naltirilmagan graf (Undirected Graph): Qirralari ikki tomonlama bo'lgan, yo'nalish belgilanmagan graf. Agar (u, v) qirrasi bo'lsa, demak (v, u) ham mavjud.

Grafni xotirada tasvirlash

Graflar kompyuter xotirasida asosan ikki xil usulda ifodalanadi:

1. Adjacency Matrix

Qo'shnilik matritsasi:

Qo'shnilik matritsasi — bu o'lchami V x V bo'lgan ikki o'lchovli massiv (matritsa) bo'lib, unda har bir qator va ustun bitta cho'qqini bildiradi.

Agar a[i][j] elementining qiymati 1 ga teng bo'lsa, bu i cho'qqi bilan j cho'qqi o'rtasida qirra borligini bildiradi.

Yuqoridagi graf uchun qo'shnilik matritsasi:

Grafning qo'shnilik matritsasi ko'rinishi

Graf yo'naltirilmagan bo'lgani uchun, (0,2) qirrasi bilan birga (2,0) qirrasini ham 1 deb belgilaymiz. Bu esa qo'shnilik matritsasini bosh diagonali bo'yicha simmetrik qiladi.

Qo'shnilik matritsasida ikki cho'qqi o'rtasida qirra bor-yo'qligini tekshirish (a[i][j] == 1) juda tez (O(1) vaqtda) amalga oshadi, biroq barcha mumkin bo'lgan ulanishlar uchun V x V joy ajratish talab etiladi, bu esa ko'proq xotira sarflaydi.

2. Adjacency List

Qo'shnilik ro'yxati:

Qo'shnilik ro'yxatida graf bog'langan ro'yxatlar (linked lists) massivi sifatida ifodalanadi.

Massiv indeksi bitta cho'qqini ifodalaydi, unga biriktirilgan ro'yxat elementlari esa ushbu cho'qqi bilan qirra hosil qilgan boshqa cho'qqilarni bildiradi:

Qo'shnilik ro'yxati (Adjacency list) tasviri

Qo'shnilik ro'yxati xotiradan foydalanish jihatidan juda tejamkor, chunki unda faqat mavjud qirralar uchun joy ajratiladi. Millionlab cho'qqilarga ega siyrak (sparse) graflar uchun bu xotirani sezilarli darajada tejash imkonini beradi.

Graf ustida asosiy amallar

Graf ustida eng ko'p bajariladigan amallar quyidagilardir:

• Element mavjudligini tekshirish: Muayyan cho'qqi yoki qirra grafda bor-yo'qligini aniqlash.
• Grafni aylanib chiqish (Graph Traversal): Barcha cho'qqilarni ma'lum tartibda ziyorat qilish (DFS va BFS).
• Element qo'shish: Grafga yangi cho'qqi (vertex) yoki qirra (edge) kiritish.
• Yo'lni topish: Bir cho'qqidan ikkinchisiga olib boruvchi eng qisqa yoki maqbul yo'lni qidirish (Bellman-Ford, Dijkstra).

Go tilida graf namunasi

Quyida Go tilida qo'shnilik ro'yxati asosida yuqoridagi grafni hosil qilish kodi keltirilgan:

package main

import "fmt"

// Graf strukturasi (qo'shnilik ro'yxati asosida)
type Graph struct {
	vertices int
	adjList  map[int][]int
}

func NewGraph(vertices int) *Graph {
	return &Graph{
		vertices: vertices,
		adjList:  make(map[int][]int),
	}
}

// Qirra qo'shish (yo'naltirilmagan graf)
func (g *Graph) AddEdge(u, v int) {
	g.adjList[u] = append(g.adjList[u], v)
	g.adjList[v] = append(g.adjList[v], u)
}

func (g *Graph) PrintGraph() {
	for v := 0; v < g.vertices; v++ {
		fmt.Printf("Cho'qqi %d qo'shnilari: %v\n", v, g.adjList[v])
	}
}

func main() {
	// 4 ta cho'qqili graf yaratish: V = {0, 1, 2, 3}
	g := NewGraph(4)

	// Qirralar: E = {(0,1), (0,2), (0,3), (1,2)}
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(0, 3)
	g.AddEdge(1, 2)

	fmt.Println("Graf tuzilishi:")
	g.PrintGraph()
}