Toshkent axborot texnologiyalari universiteti fargona filiali

Chizma:

Yechim:
const graph = { 1: [2, 3, 4], 2: [4], 3: [4, 5], 4: [5] };

// 1 tug'unidan 5 tug'uniga borish yo'lini topish

const queue = [1];
const visited = new Set();
const parent = {};
let found = false;


while (queue.length > 0) {
const current = queue.shift();
visited.add(current);
if (current === 5) {
found = true;
break;
}
for (const neighbor of graph[current]) {
if (!visited.has(neighbor)) {
parent[neighbor] = current;
queue.push(neighbor);
}
}
}

// Natijani ekranga chiqaramiz

if (found) {
console.log("5 tug'uniga borish mumkin!");
let path = "5";
let node = 5;
while (node !== 1) {
path = parent[node] + " -> " + path;
node = parent[node];
}
console.log("Yo'l: " + path);
} else {
console.log("5 tug'uniga borish imkonsiz!");
}

Natija:


Laborato‘riya ishi – 6

Mavzu: Kesishmaydigan to‘plam ostilari va birlashmalarini qidirish algoritmi. NP-to‘liq masalalar. NP-to‘liq masalalarga keltirish usullari.

Ishdan maqsad. Kesishmaydigan to‘plam ostilari va birlashmalarini qidirish algoritmi. NP-to‘liq masalalar. NP-to‘liq masalalarga keltirish usullari.
Qo’yilgan masala. Kesishmaydigan to’plam ostilari va birlashmalarini qidirish algoritmi.
Ish tartibi:

• 
  Tajriba ishi nazariy ma’lumotlarini o‘rganish;
  
• 
  Berilgan topshiriqning algoritmini ishlab chiqish;
  
• 
  C++ dasturlash muhitida dasturni yaratish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.