Berilgan ma’lumotlar asosida grafning qo’shnilik matritsasini tashkil qiluvchi


Download 0.99 Mb.
Sana22.01.2023
Hajmi0.99 Mb.
#1110687
Bog'liq
mta 12


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.
Deykstra algoritmi
Dastur kodi:
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
using namespace std;
int main()
{
int SIZE;
cout<<"graf uchlari sonini kiriting-";
cin>>SIZE;
int a[SIZE][SIZE];
int d[SIZE];
int v[SIZE];
int s=0;
int temp, minindex, min;
int begin_index=0 ;
for (int i = 0; i{
a[i][i] = 0;
for (int j = i + 1; jprintf("qovurga vaznini kiriting %d - %d: ", i , j );
scanf("%d", &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
cout<<"grafning qo'shnilik matritsasi"<for (int i = 0; i{
for (int j = 0; jprintf("%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("\neng qisqa yo'lddagi qovurg'lar og'iirligi: \n");
for (int i = 0; i{
printf("%5d ", d[i]);
s+=d[i];
}
cout<<"eng qisqa yo'l uzunligi-"<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; iif (a[i][end] != 0)
{
int temp = weight - a[i][end];
if (temp == d[i])
{
weight = temp;
end = i;
ver[k] = i + 1;
k++;
}
}
}
printf("\neng qisqa masofa yo'nalishi'\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d ", ver[i]);
getchar(); getchar();
return 0;
}


Floy usulida shu masala yechimi
Dastur kodi:
#include
#include
using namespace std;
void floyds(int b[][7])
{
int i, j, k;
for (k = 0; k < 7; k++)
{
for (i = 0; i < 7; i++)
{
for (j = 0; j < 7; j++)
{
if ((b[i][k] * b[k][j] != 0) && (i != j))
{
if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0))
{
b[i][j] = b[i][k] + b[k][j];
}
}
}
}
}
for (i = 0; i < 7; i++)
{ int s=0;
cout<<"\n"<for (j = 0; j < 7; j++)
{
cout<s+=b[i][j];
}
cout<<"umumiy uzunlik-"<}
}
int main()
{
int b[7][7];
cout<<"ENTER VALUES OF ADJACENCY MATRIX\n\n";
for (int i = 0; i < 7; i++)
{
cout<for (int j = 0; j < 7; j++)
{
cin>>b[i][j];
}
}
floyds(b);
getch();
}

Download 0.99 Mb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling