Adjacency Matrix

Qo'shnilik matritsasi (Adjacency Matrix) — bu grafni mantiqiy qiymatlar (mantiqiy 0 va 1 lar) matritsasi sifatida ifodalash usulidir. Chekli graf kompyuter xotirasida kvadrat matritsa ko'rinishida saqlanadi, undagi mantiqiy qiymatlar esa ikki cho'qqi o'rtasida bevosita to'g'ridan-to'g'ri bog'lanish (qirra) mavjud yoki yo'qligini bildiradi.

Misol uchun, quyidagi yo'naltirilmagan grafni olaylik:

Yo'naltirilmagan graf (An undirected graph)

Biz ushbu grafni jadval / matritsa ko'rinishida quyidagicha ifodalashimiz mumkin:

Grafning matritsa ko'rinishidagi tasviri

Yuqoridagi jadval/matritsaning har bir katakchasi A[i][j] shaklida belgilanadi, bu yerda i va j — grafning cho'qqilari hisoblanadi. i cho'qqidan j cho'qqiga qirra mavjudligiga qarab A[i][j] ning qiymati 1 yoki 0 bo'ladi.

Agar i dan j ga to'g'ridan-to'g'ri qirra bo'lsa, A[i][j] qiymati 1, aks holda 0 ga teng. Masalan, 1-cho'qqidan 2-cho'qqiga qirra bor, shuning uchun A[1][2] = 1. Ammo 1-cho'qqidan 3-cho'qqiga qirra yo'q, shuning uchun A[1][3] = 0.

Yo'naltirilmagan graflarda matritsa doimo bosh diagonal bo'yicha simmetrik bo'ladi, chunki har bir (i, j) qirra uchun uning teskarisi (j, i) qirra ham mavjud.

Qo'shnilik matritsasining afzalliklari

• Qirra qo'shish, qirrani o'chirish va ikki cho'qqi (i va j) o'rtasida qirra bor-yo'qligini tekshirish kabi asosiy amallar o'ta tez — doimiy vaqtda (O(1) da) bajariladi.
• Agar graf zich (dense) bo'lib, undagi qirralar soni juda ko'p bo'lsa, qo'shnilik matritsasi eng birinchi va eng to'g'ri tanlov hisoblanadi. Graf siyrak (sparse) bo'lgan taqdirda ham, uni siyrak matritsalar uchun maxsus siqilgan tuzilmalar bilan ifodalash mumkin.
• Eng katta afzallik matritsalarning o'zidan kelib chiqadi: zamonaviy apparat vositalari (GPU) katta hajmdagi matritsa amallarini parallel ravishda soniyaning ulushlarida hisoblash imkonini beradi.
• Qo'shnilik matritsasi ustida algebraik amallarni bajarish (masalan, matritsani darajaga ko'tarish) orqali grafning tabiati va cho'qqilar orasidagi bog'liqliklar haqida chuqur ma'lumot olish mumkin.

Qo'shnilik matritsasining kamchiliklari

• Qo'shnilik matritsasi V x V o'lchamdagi xotirani talab qiladi, bu esa juda ko'p xotira sarflaydi (O(V^2)). Amaliyotda real graflar (masalan, ijtimoiy tarmoqlar, yo'l xaritalari) kam sonli ulanishlarga ega bo'ladi (siyrak graf), shuning uchun ko'plab vazifalar uchun qo'shnilik ro'yxati (adjacency list) ancha samaraliroq tanlov hisoblanadi.
• Asosiy qirra tekshirish oson bo'lsa-da, barcha kiruvchi (inEdges) yoki chiquvchi (outEdges) qirralarni topish uchun butun qator yoki ustunni to'liq ko'rib chiqish kerak bo'ladi (O(V) vaqt).

Dasturiy namunalar

Agar siz ikki o'lchovli massivlarni yaratishni bilsangiz, demak qo'shnilik matritsasini ham bemalol yarata olasiz.

// Go tilida qo'shnilik matritsasi (Adjacency Matrix) ifodalanishi
package main

import "fmt"

type Graph struct {
	numVertices int
	adjMatrix   [][]bool
}

// Matritsani initsializatsiya qilish
func NewGraph(numVertices int) *Graph {
	matrix := make([][]bool, numVertices)
	for i := range matrix {
		matrix[i] = make([]bool, numVertices)
	}
	return &Graph{
		numVertices: numVertices,
		adjMatrix:   matrix,
	}
}

// Qirra qo'shish
func (g *Graph) AddEdge(i, j int) {
	g.adjMatrix[i][j] = true
	g.adjMatrix[j][i] = true
}

// Qirrani olib tashlash
func (g *Graph) RemoveEdge(i, j int) {
	g.adjMatrix[i][j] = false
	g.adjMatrix[j][i] = false
}

// Matritsani ekranga chiqarish
func (g *Graph) PrintMatrix() {
	for i := 0; i < g.numVertices; i++ {
		fmt.Printf("%d: ", i)
		for j := 0; j < g.numVertices; j++ {
			val := 0
			if g.adjMatrix[i][j] {
				val = 1
			}
			fmt.Printf("%d ", val)
		}
		fmt.Println()
	}
}

func main() {
	g := NewGraph(4)

	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 2)
	g.AddEdge(2, 0)
	g.AddEdge(2, 3)

	g.PrintMatrix()
}

Qo'shnilik matritsasining qo'llanilishi

• Tarmoqlarda marshrutlash jadvalini (Routing Table) yaratish: Marshrutizatorlar (routerlar) orasidagi to'g'ridan-to'g'ri ulanishlarni qayd etishda.
• Navigatsiya vazifalari: Xaritalar va transport tizimlarida bevosita yo'l mavjudligini tezkor tekshirishda.