Mustaqil ish fan nomi: Algoritmlash va loyihalash Mavzu

Cycle‘ni qanday aniqlaymiz?
Aylanalarni topish uchun depth first searchdan foydalansa bo’ladi. Aslida bizga cycle’ni topish ham shartmas, Edge’ning ikki vertexi – v dan w ga path borligini tekshirish kifoya qiladi. Sababi agar path bo’lsa, yangi qo’shiladigan edge cycle’ga olib keladi.
Path borligini tekshirish uchun depth first search‘dan foydalanish mumkin.
Alternativ variant – Union-Findni ishlatsa ham bo’ladi.

Kod

Quyidagi funksiya bog’lanishlarni Union-find‘da tekshiradi.

	const UnionFind = require("../union-find/weighted-union-find-improvement")
	function kruskalMST(graph) {
	// Collect edge list into dictionary object
	const edgeList = new Map()
	// Fill the edgeList
	for (let i = 0; i < graph.length; i++) {
	for (let j = 0; j < graph[i].length; j++) {
	const edge = graph[i][j]
	const vertices = [edge.get('v'), edge.get('w')]
	// Sort edge vertices to use it as dictionary key
	vertices.sort((a,b) => a - b)
	// Use dictionary to skip duplicates
	edgeList.set(vertices.join('-'), edge)
	}
	}
	// Convert edgeList object to min priority queue
	const PQ = [...edgeList.values()]
	// Sort PQ by weight
	PQ.sort((a,b) => a.get('weight') - b.get('weight'))
	// Initialize Union Find object
	const UF = new UnionFind()
	// Create union-find components
	UF.assign(graph.length)
	// Initialize
	const MST = []
	while (PQ.length > 0 && MST.length < graph.length - 1) {
	// Get min (first) value from PQ
	const edge = PQ.shift()
	// Check if two vertices are connected
	if (!UF.find(edge.get('v'), edge.get('w'))) {
	// Connect two vertices
	UF.union(edge.get('v'), edge.get('w'))
	// Add edge to MST
	MST.push(edge)
	}
	}
	return MST
	}
	/**
	* USAGE
	*/
	// Sometimes we get edge list instead of graph
	const weightedEdgeList = [
	[ [6,0], 0.58 ],
	[ [2,3], 0.17 ],
	[ [4,7], 0.37 ],
	[ [1,5], 0.32 ],
	[ [0,2], 0.26 ],
	[ [0,7], 0.16 ],
	[ [1,3], 0.29 ],
	[ [4,5], 0.35 ],
	[ [2,7], 0.34 ],
	[ [6,2], 0.40 ],
	[ [6,4], 0.93 ],
	[ [1,7], 0.19 ],
	[ [5,7], 0.28 ],
	[ [0,4], 0.38 ],
	[ [3,6], 0.52 ],
	[ [1,2], 0.36 ],
	]
	// If we have edge list, need to fill graph
	// The sad thing is.. if we have edge list, we'll need a graph length from the graph only
	// Check Kruskal MST implementation above
	const graph = []
	// Assign vertices and weight to adjacent list graph
	weightedEdgeList.forEach(item => {
	const vertices = item[0]
	const edge = new Map()
	// Add vertices
	edge.set('v', vertices[0])
	edge.set('w', vertices[1])
	// Add weight
	edge.set('weight', item[1])
	if (!graph[vertices[0]]) {
	graph[vertices[0]] = []
	}
	if (!graph[vertices[1]]) {
	graph[vertices[1]] = []
	}
	graph[vertices[0]].push(edge)
	graph[vertices[1]].push(edge)
	});
	// Show MST edges
	console.log(kruskalMST(graph))

Kruskal algoritmi. Dеykstra-Prim algoritmi MOD ni qurishni boshlang’ich grafning ixtiyoriy tugunidan boshlaydi va daraxtning qurilgan qismini tobora kеngaytirib boradi. Ushbu algoritmdan farqli ravishda Kruskal algoritmi asosiy e'tiborni graf tomonlariga qaratadi. Bunda ishni bo’sh grafdan boshlab, unga tomonlarini ular vaznining o’sib borish tartibida kеtma-kеt qo’shib boradi. Bu jarayon grafga kiruvchi barcha tugunlar o’zaro bog’langunga qadar davom etadi. Agar tomonlarni qo’shib olish jarayoni barcha tugunlar o’zaro bog’langunga qadar tugatilsa, boshlan?ich grafning to’liq bog’lanmagan ekanligi kеlib chiqadi. Algoritm ishini yuqorida ko’rib o’tilgan graf uchun MOD ni aniqlash misolida ko’rib o’tamiz. Ishni eng kichik vaznli DF tomondan boshlaymiz. Boshlang’ich garf v rasmda ifodalangan. Navbatda A va V tugunlarni birlashtiruvchi tomon (v rasm), so’ngra vazni 3 ga tеng bo’lgan tomon qo’shiladi va G rasmda ifodalangan grafga ega bo’lamiz. Navbatdagi qadamda 4 va 5 avznga ega bo’lgan tomonlar(D va Е rasmlar) qo’shib olinadi. Natijada qo’shilmagan faqat G tugun qoladi. Kеyingi qadamda vazni 6 ga tеng tomonlarni qayta ishlash kеrak bo’ladi. Vazni 6 ga tеng bo’lgan to’rtta tomondan ikkitasini qoldiramiz. Natijada qaysi ikki tomonning qoldirilishiga bo?liq holda J yoki Z rasmlarda ifodalangan MOD lardan biriga ega bo’lamiz.

a) b)
v) g)

d) e)
j) z)
Quyida ushbu algoritm matnini kеltiramiz. Bunda Е bilan grafdagi tomonlar soni, N bilan tugunlar soni ifoddalangan:
edgeCount=1

while edgeCount<=Е and includedCount<=N-1 do

parent1=FindRoot(edge[edgeCount].start)

parent2=FindRoot(edge[edgeCount].end)

if parent1/parent2 then

edge[edgeCount] ni MOD ga qo’shish

includedCount= includedCount=1

Union(parent1,parent2)

Enf if

edgeCount= edgeCount+1

end while
Algoritmning asosiy sikli edgeCount o’zgaruvchisining qiymati grafdagi tomonlar soni bilan tеnglashishi yoki includedCount o’zgaruvchisining qiymati MOD ni shakllantirish uchun еtarlicha tomonlar qo’shilganini ko’rsatgunga qadar ishlaydi (N tugunli garfning MOD i N-1 ta tomonga ega bo’lishi kеrak) .