Ishdan maqsad: Talabalarda graflar bilan ishlash algoritmlari haqida ko’nikmalar hosil qilish va ular bilan ishlashni o’rganish

TOPSHIRIQ

C++ (Python, Java) tilida quyidagi amallarni bajaruvchi dastur tuzing:

• 
  Foydalanuvchidan vaznli yo’nalishsiz grafning uchlari va qovurg’alari sonini, mavjud qovurg’alarning ro’yhati va og’irligini so’rovchi;
  
• 
  Berilgan ma’lumotlar asosida grafning qo’shnilik matritsasini tashkil qiluvchi;
  
• 
  Garfning boshlang’ich va oxirgi uchlarini so’rovchi;
  
• 
  Ekranga berilgan uchlar orasidagi qisqa masofani va uning og’irligini chiqaruvchi;
  
• 
  Quyidagi graf asosida tekshirib ko’ruvchi:
  

Masalani Deykstra va Floyd algoritmlari asosida yeching va ularning samaradorligini solishtiring.

Nazorat savollari:

1. 
   Deykstra va Floyd algoritmlari graflarning qaysi ko’rinishlari bilan ishlaydi?
   
2. 
   Grafni tasvirlash nima sababdan algoritmning samaradorligiga ta’sir ko’rsatadi?
   
3. 
   Nima sababdan kenglik bo’yicha qidirish yetarlicha resurstalab algoritm hisoblanadi?
   
4. 
   Grafni kenglik bo’yicha aylanish algoritmining afzalligi nimada?
   
5. 
   Grafni aylanib o’tish algoritmlarini rekursiya yordamida dasturiy joriy qilinganda nima baza sifatida ajratiladi va dekompazitsiya qanday tashkil qilinadi?
   

Adabiyotlar ro’yhati:

1. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн; пер. с англ. – 2-е изд. – М.: Вильямс, 2011. – 1 296 с.

2. Кристофидес, Н. Теория графов: Алгоритмический подход / Н. Кристофидес. – М.: Мир, 1978. – 434 с.

3. Седжвик, Р. Фундаментальные алгоритмы на С++: Алгоритмы на графах / Р. Седжвик; пер. с англ. – СПб.: Диасофт, 2002. – 496 с.

4. Скиена, С. Алгоритмы. Руководство по разработке / С. Скиена; пер. с англ. – 2-е изд. – СПб.: БХВ-Петербург, 2011.– 720 с.

5. Троелсен, Э. С# и платформа .NET 3.0, специальное издание / Э. Троелсен. – СПб.: Питер, 2008. – 1 456 с.