Strongly Connected Components

Kuchli bog'langan komponent (Strongly Connected Component - SCC) — bu yo'naltirilgan grafning shunday bir qism-grafiki, unda ixtiyoriy bitta cho'qqidan boshqa har qanday cho'qqiga olib boruvchi yo'naltirilgan yo'l mavjud bo'ladi. Bu tushuncha faqat yo'naltirilgan graflar (directed graph) uchun amal qiladi.

Masalan:

Quyidagi yo'naltirilgan grafni ko'rib chiqaylik:

Dastlabki yo'naltirilgan graf (Initial graph)

Yuqoridagi grafning kuchli bog'langan komponentlari quyidagilardir:

Kuchli bog'langan komponentlar (Strongly Connected Components)

Ko'rib turganingizdek, birinchi kuchli bog'langan komponentda ({0, 1, 2, 3}), har bir cho'qqidan boshqa har qanday cho'qqiga yo'naltirilgan yo'llar orqali yetib borish mumkin.

Ushbu komponentlarni Kosaraju algoritmi (Kosaraju's Algorithm) yordamida topish mumkin.

Kosaraju algoritmi

Kosaraju algoritmi ikki marta ketma-ket qo'llaniladigan chuqurlik bo'yicha qidiruv (Depth-First Search - DFS) algoritmiga asoslanadi.

Algoritm 3 ta asosiy bosqichdan iborat:

1-bosqich: Butun graf bo'ylab chuqurlik bo'yicha qidiruv bajarish

0-cho'qqidan boshlaymiz, uning barcha bola cho'qqilarini aylanib chiqamiz va ziyorat qilingan cho'qqilarni belgilab boramiz. Agar biror cho'qqi allaqachon ziyorat qilingan cho'qqiga olib borsa, unda mazkur cho'qqini stekka (stack) joylaymiz (push).

Masalan: 0-cho'qqidan boshlab, 1-cho'qqiga, so'ng 2-cho'qqiga va undan keyin 3-cho'qqiga o'tamiz. 3-cho'qqi allaqachon ziyorat qilingan 0-cho'qqiga yo'nalgan, shuning uchun boshlang'ich cho'qqini (ya'ni 3-cho'qqini) stekka joylaymiz.

Grafda DFS bajarish (1-qadam)

Oldingi cho'qqiga (2-cho'qqiga) qaytamiz va uning qolgan tarmoqlari — 4, 5, 6 va 7-cho'qqilarni ketma-ket ziyorat qilamiz. 7-cho'qqidan borish uchun boshqa yo'l bo'lmagani sababli, uni stekka joylaymiz.

Grafda DFS bajarish (2-qadam)

Oldingi cho'qqiga (6-cho'qqiga) qaytamiz va uning bola cho'qqilarini ko'ramiz. Biroq, uning barcha tutashgan cho'qqilari allaqachon ziyorat qilingan, shuning uchun uni ham stekka joylaymiz.

Cho'qqilarni stekka joylash (Stacking)

Xuddi shu tariqa orqaga qaytish davom ettirilib, yakuniy stek hosil qilinadi:

Yakuniy stek (Final Stack)

2-bosqich: Dastlabki graf qirralarini teskari yo'naltirish

Grafning har bir yo'naltirilgan (u → v) qirrasini teskari (v → u) yo'nalishga aylantiramiz:

Teskari yo'naltirilgan graf (Reversed graph)

3-bosqich: Teskari graf bo'ylab chuqurlik bo'yicha qidiruv bajarish

Stekning eng yuqori qismidagi cho'qqidan boshlaymiz. Uning barcha erishiladigan cho'qqilarini aylanib chiqamiz. Ziyorat qilinmagan barcha yetib boriladigan cho'qqilar bitta kuchli bog'langan komponentni tashkil qiladi.

Masalan: Stekdan 0-cho'qqini chiqaramiz (pop). 0-cho'qqidan boshlab uning teskari grafdagi bola cho'qqilarini (0, 1, 2, 3 ketma-ketligida) aylanib chiqamiz va ularni ziyorat qilingan deb belgilaymiz. 3-cho'qqining boradigan cho'qqilari allaqachon ziyorat qilingan, natijada ushbu ziyorat qilingan cho'qqilar bitta kuchli bog'langan komponentni hosil qiladi.

Stekning yuqori qismidan boshlab barcha cho'qqilarni aylanib chiqish

Stekdan navbatdagi yuqori cho'qqini olamiz. Agar u allaqachon ziyorat qilingan bo'lsa, uni tashlab yuboramiz. Aks holda, stekning yuqorisidagi ziyorat qilinmagan cho'qqidan boshlab yuqoridagi tartibda DFS o'tkazamiz.

Agar allaqachon ziyorat qilingan bo'lsa, cho'qqini stekdan chiqarish

Navbatdagi kuchli bog'langan komponentni ajratib olish

Shunday qilib, grafning barcha kuchli bog'langan komponentlari aniqlanadi:

Grafning barcha kuchli bog'langan komponentlari

Dasturiy namunalar

// Go tilida Kosaraju algoritmi yordamida kuchli bog'langan komponentlarni topish
package main

import "fmt"

type Graph struct {
	V   int
	adj [][]int
}

func NewGraph(v int) *Graph {
	return &Graph{
		V:   v,
		adj: make([][]int, v),
	}
}

// Grafga qirra qo'shish
func (g *Graph) AddEdge(s, d int) {
	g.adj[s] = append(g.adj[s], d)
}

// DFS orqali aylanib chiqish
func (g *Graph) dfs(s int, visited []bool) {
	visited[s] = true
	fmt.Printf("%d ", s)
	for _, neighbor := range g.adj[s] {
		if !visited[neighbor] {
			g.dfs(neighbor, visited)
		}
	}
}

// Grafni transponirlash (qirralarni teskarisiga o'girish)
func (g *Graph) transpose() *Graph {
	gr := NewGraph(g.V)
	for s := 0; s < g.V; s++ {
		for _, d := range g.adj[s] {
			gr.AddEdge(d, s)
		}
	}
	return gr
}

// Cho'qqilarni ziyorat qilish tugash tartibi bo'yicha stekka yig'ish
func (g *Graph) fillOrder(s int, visited []bool, stack *[]int) {
	visited[s] = true
	for _, neighbor := range g.adj[s] {
		if !visited[neighbor] {
			g.fillOrder(neighbor, visited, stack)
		}
	}
	*stack = append(*stack, s)
}

// Kuchli bog'langan komponentlarni chop etish
func (g *Graph) PrintSCC() {
	stack := make([]int, 0)
	visited := make([]bool, g.V)

	// 1-bosqich: Stekni to'ldirish
	for i := 0; i < g.V; i++ {
		if !visited[i] {
			g.fillOrder(i, visited, &stack)
		}
	}

	// 2-bosqich: Grafni teskari yo'naltirish
	gr := g.transpose()
	for i := 0; i < g.V; i++ {
		visited[i] = false
	}

	// 3-bosqich: Teskari grafda DFS bajarish
	for len(stack) > 0 {
		s := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if !visited[s] {
			gr.dfs(s, visited)
			fmt.Println()
		}
	}
}

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

	fmt.Println("Kuchli bog'langan komponentlar (Strongly Connected Components):")
	g.PrintSCC()
}

Kosaraju algoritmining murakkabligi

Kosaraju algoritmi chiziqli vaqtda, ya'ni O(V + E) da ishlaydi (bunda V — cho'qqilar soni, E — qirralar soni).

• Vaqt murakkabligi: O(V + E) — birinchi DFS O(V + E), grafni transponirlash O(V + E), ikkinchi DFS O(V + E) vaqt oladi.
• Xotira murakkabligi: O(V) — rekursiya steki, visited massivi va transponirlangan graf uchun.

Kuchli bog'langan komponentlarning qo'llanilishi

• Avtotransport vositalarini marshrutlash dasturlarida (Vehicle routing applications): Bir tomonlama harakatga ega yo'l tarmoqlarida berk ko'chalarni va aylanma yo'llarni aniqlash.
• Xaritalash tizimlarida (Maps): Shahar ko'chalari va navigatsiya tarmoqlarini tahlil qilishda.
• Format tekshiruvida modelni tekshirish (Model-checking in formal verification): Tizim holatlari graflarida cheksiz sikllar yoki yopiq zanjirlarni topishda.