"Data Structures in Go" kursida grafni adjacency list (qo'shnilar ro'yxati) orqali ifodalagan edingiz. Bu darsda esa graflarni ifodalashning ikkinchi keng tarqalgan usulini — adjacency matrix (qo'shnilik matritsasi) — ko'ramiz, chunki keyingi ikkita darsdagi qidiruv algoritmlari (BFS, DFS) ikkalasi bilan ham ishlashi mumkin.

Matritsani sinf jurnaliga o'xshating: har bir qator va ustun bitta o'quvchini ifodalaydi, va agar ikki o'quvchi do'st bo'lsa, ularning kesishgan katagiga "belgi" qo'yiladi. Bu — "kim kim bilan bog'langan" degan savolga bir zumda javob berish imkonini beradi: shunchaki matritsaning shu katagini tekshirasiz.

package main

import "fmt"

type Graph struct {
	nodes  []string
	matrix [][]bool
}

func NewGraph(nodes []string) *Graph {
	n := len(nodes)
	matrix := make([][]bool, n)
	for i := range matrix {
		matrix[i] = make([]bool, n)
	}
	return &Graph{nodes: nodes, matrix: matrix}
}

func (g *Graph) index(name string) int {
	for i, n := range g.nodes {
		if n == name {
			return i
		}
	}
	return -1
}

func (g *Graph) AddEdge(a, b string) {
	i, j := g.index(a), g.index(b)
	g.matrix[i][j] = true
	g.matrix[j][i] = true
}

func (g *Graph) Connected(a, b string) bool {
	i, j := g.index(a), g.index(b)
	return g.matrix[i][j]
}

func main() {
	g := NewGraph([]string{"A", "B", "C"})
	g.AddEdge("A", "B")
	fmt.Println(g.Connected("A", "B"))
	fmt.Println(g.Connected("A", "C"))
}

matrix[i][j] — i-uch va j-uch orasida bog'lanish bor-yo'qligini bildiruvchi true/false. Connected(a, b) shunchaki matritsaning mos katagini o'qiydi — bu doimiy tezlikda (qo'shnilar sonidan qat'i nazar) ishlaydi, adjacency list'da esa qo'shnilar ro'yxatini oxirigacha tekshirish kerak bo'lishi mumkin edi.

Lekin bu tezlikning narxi bor: agar uchlar soni katta bo'lsa-yu, bog'lanishlar kam bo'lsa ("siyrak graf"), matritsa ko'p bo'sh joy (xotira) egallaydi — n ta uch uchun har doim n*n katak kerak, garchi haqiqiy bog'lanishlar soni ancha kam bo'lsa ham. Shuning uchun: zich graflar (ko'p bog'lanish) uchun matritsa, siyrak graflar uchun adjacency list ko'proq afzal.