Adjacency List

Qo'shnilik ro'yxati (Adjacency List) — bu grafni bog'langan ro'yxatlar (linked lists) massivi ko'rinishida ifodalash usulidir. Massivning indeksi muayyan bitta cho'qqini bildiradi va unga biriktirilgan bog'langan ro'yxatning har bir elementi ushbu cho'qqi bilan bevosita qirra hosil qilgan boshqa cho'qqilarni ifodalaydi.

Masalan, quyidagi yo'naltirilmagan grafni olaylik:

Yo'naltirilmagan graf (An undirected graph)

Biz bu grafni kompyuter xotirasida bog'langan ro'yxat shaklida quyidagicha tasvirlashimiz mumkin:

Grafning bog'langan ro'yxat (Adjacency list) ko'rinishidagi tasviri

Bu yerda 0, 1, 2, 3 — grafning cho'qqilari bo'lib, ularning har biri o'ziga qo'shni bo'lgan barcha cho'qqilar bilan bog'langan ro'yxat hosil qiladi. Masalan, 1-cho'qqi 0 va 2 cho'qqilariga qo'shnidir. Shuning uchun yuqoridagi rasmda 1-cho'qqining ro'yxati 0 va 2 bilan bog'langan.

Qo'shnilik ro'yxatining afzalliklari

• Qo'shnilik ro'yxati xotiradan foydalanish jihatidan nihoyatda tejamkordir, chunki unda faqat mavjud qirralar uchun joy ajratiladi. Millionlab cho'qqilar va kam sonli qirralarga ega siyrak graf (sparse graph) uchun bu xotirani ulkan miqdorda tejash imkonini beradi.
• Muayyan bir cho'qqiga tutashgan barcha qo'shni cho'qqilarni topish juda oson va tez kechadi (faqat shu cho'qqining ro'yxatini aylanib chiqish kifoya).

Qo'shnilik ro'yxatining kamchiliklari

• Ikki aniq cho'qqi (u va v) o'rtasida qirra bor yoki yo'qligini tekshirish qo'shnilik matritsasiga qaraganda sekinroq kechadi, chunki buning uchun u cho'qqisining ro'yxatini boshidan oxirigacha ko'rib chiqish talab etiladi (O(deg(u)) vaqt).

Qo'shnilik ro'yxatining tuzilishi

Eng oddiy qo'shnilik ro'yxati cho'qqini saqlash uchun bitta tugun (node) tuzilmasi hamda tugunlarni birlashtirish uchun graf tuzilmasidan iborat bo'ladi.

Biz grafning asosiy ta'rifiga — cho'qqilar va qirralar to'plamiga {V, E} asoslanamiz. Oddiylik uchun belgilanmagan grafdan foydalanamiz, ya'ni cho'qqilar o'z indekslari (0, 1, 2, 3) orqali aniqlanadi.

Quyidagi C tili misolida tuzilmani ko'rib chiqamiz:

struct node {
    int vertex;
    struct node* next;
};

struct Graph {
    int numVertices;
    struct node** adjLists;
};

struct node** adjLists yozuvi sizni cho'chitmasin — bu yerda biz shunchaki struct node* ko'rsatkichlar massiviga yo'naltirilgan ko'rsatkichni belgilayapmiz. Chunki kompilyatsiya vaqtida graf nechta cho'qqidan iborat bo'lishini oldindan bilmaymiz, shuning uchun massiv xotirasini dinamik tarzda ajratamiz.

C++ tilida qo'shnilik ro'yxati

C++ tilida ichki std::list yoki std::vector STL konteynerlaridan foydalanish orqali tuzilmani yanada toza va qulay ko'rinishga keltirish mumkin:

class Graph {
    int numVertices;
    list<int> *adjLists;
    
public:
    Graph(int V);
    void addEdge(int src, int dest);
};

Java tilida qo'shnilik ro'yxati

Java tilida bog'langan ro'yxatlar massivini yaratish uchun Java Collections to'plamidan (LinkedList yoki ArrayList) foydalaniladi:

class Graph {
    private int numVertices;
    private LinkedList<Integer> adjLists[];
}

Ro'yxat turi siz saqlamoqchi bo'lgan ma'lumotga bog'liq. Agar graf cho'qqilari matnli nomlarga ega bo'lsa, butun son o'rniga lug'at yoki obyekt saqlash mumkin.

Python tilida qo'shnilik ro'yxati

Python dasturlash tili o'zining qulay sintaksisi bilan ajralib turadi. Cho'qqilar va ularning qirralarini ifodalash uchun oddiy lug'at (dict) va to'plamlar (set) to'liq yetarli hisoblanadi:

graph = {
    'A': set(['B', 'C']),
    'B': set(['A', 'D', 'E']),
    'C': set(['A', 'F']),
    'D': set(['B']),
    'E': set(['B', 'F']),
    'F': set(['C', 'E'])
}

Dasturiy namunalar

// Go tilida bog'langan ro'yxat asosida qo'shnilik ro'yxati (Adjacency List)
package main

import "fmt"

type Node struct {
	vertex int
	next   *Node
}

type Graph struct {
	numVertices int
	adjLists    []*Node
}

func NewGraph(vertices int) *Graph {
	return &Graph{
		numVertices: vertices,
		adjLists:    make([]*Node, vertices),
	}
}

// Qirra qo'shish (yo'naltirilmagan graf)
func (g *Graph) AddEdge(s, d int) {
	// s dan d ga
	newNode := &Node{vertex: d, next: g.adjLists[s]}
	g.adjLists[s] = newNode

	// d dan s ga
	newNode = &Node{vertex: s, next: g.adjLists[d]}
	g.adjLists[d] = newNode
}

// Grafni ekranga chop etish
func (g *Graph) PrintGraph() {
	for v := 0; v < g.numVertices; v++ {
		fmt.Printf("Vertex %d: ", v)
		temp := g.adjLists[v]
		for temp != nil {
			fmt.Printf("-> %d ", temp.vertex)
			temp = temp.next
		}
		fmt.Println()
	}
}

func main() {
	g := NewGraph(4)
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(0, 3)
	g.AddEdge(1, 2)

	g.PrintGraph()
}

Qo'shnilik ro'yxatining qo'llanilishi

• Qirralari kam bo'lgan siyrak graflarda ma'lumotlarni saqlash va aylanib chiqish uchun qo'shnilik ro'yxatidan foydalanish ancha tezkor va xotirani kam talab qiladi.