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

Laboratoriya ishi №2. Graflar bilan ishlashning elementar algoritmlari.

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

Nazariy qism:

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:
  

Dastur Kodi:

#define _CRT_SECURE_NO_WARNINGS

#include

#include

#define SIZE 6

int main()

{

int a[SIZE][SIZE];

int d[SIZE];

int v[SIZE];

int temp, minindex, min;

int begin_index = 0;

system("chcp 1251");

system("cls");

for (int i = 0; i

{

a[i][i] = 0;

for (int j = i + 1; j

printf("masofani kiriting %d - %d: ", i + 1, j + 1);

scanf("%d", &temp);

a[i][j] = temp;

a[j][i] = temp;

}

}

for (int i = 0; i

{

for (int j = 0; j

printf("%5d ", a[i][j]);

printf("\n");

}

for (int i = 0; i

{

d[i] = 10000;

v[i] = 1;

}

d[begin_index] = 0;

do {

minindex = 10000;

min = 10000;

for (int i = 0; i

{

if ((v[i] == 1) && (d[i]

{

min = d[i];

minindex = i;

}

}

if (minindex != 10000)

{

for (int i = 0; i

{

if (a[minindex][i] > 0)

{

temp = min + a[minindex][i];

if (temp < d[i])

{

d[i] = temp;

}

}

}

v[minindex] = 0;

}

} while (minindex < 10000);

printf("\nTepaliklardagi eng qisqa masofalar: \n");

for (int i = 0; i

printf("%5d ", d[i]);

int ver[SIZE];

int end = 4;

ver[0] = end + 1;

int k = 1;

int weight = d[end];

while (end != begin_index)

{

for (int i = 0; i

if (a[i][end] != 0)

{

int temp = weight - a[i][end];

if (temp == d[i])

{

weight = temp;

end = i;

ver[k] = i + 1;

k++;

}

}

}

printf("\nQisqa yo'l\n");

for (int i = k - 1; i >= 0; i--)

printf("%3d ", ver[i]);

getchar(); getchar();

return 0;

}

Dastur Natijasi:

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 с.