Berilgan ma’lumotlar asosida grafning qo’shnilik matritsasini tashkil qiluvchi
Download 0.99 Mb.
|
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; j scanf("%d", &temp); a[i][j] = temp; a[j][i] = temp; } } cout<<"grafning qo'shnilik matritsasi"< for (int j = 0; 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 end = 4; ver[0] = end + 1; int k = 1; int weight = d[end]; while (end != begin_index) { for (int i = 0; i { 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
ma'muriyatiga murojaat qiling