Bajardi: Xoshimov Diyorbek

Muhammad Al-Xorazmiy nomidagi
Toshkent axborot texnologiyalari universiteti

4-labaratoriya
Algaritim loyihalash

Bajardi: Xoshimov Diyorbek

Tekshirdi: Begimov Oybek

1) Variant berilishi

2)Matritsa orqali berilgan grafni qirralarini soni topish algoritmi, dasturi va natijasi
#include
using namespace std;
int main()
{
int a[6][6]=
{
{0,6,8,13,11,7},
{6,0,7,0,0,0},
{8,7,0,10,0,0},
{13,0,10,0,10,0},
{11,0,0,10,0,9},
{7,0,0,0,9,0}
};
int k=0;
for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
{
if(a[i][j]>0)
{
k++;
}
}
}
cout<<"Qirralari soni ="<}

3) Matritsaga ko'ra planar graf chizish

5. Prima algoritmi va dasturini tuzish (qisqa yo'lni topish)
// C++ da Prim algoritmi
#include
#include
using namespace std;
#define INF 9999999
// grafikdagi uchlari soni
#define V 6
// 6x6 o'lchamdagi 2D massiv yarating
//grafikni ifodalash uchun qo'shnilik matritsasi uchun
int G[V][V] = {
{0, 6, 8, 13, 11, 7},
{6, 0, 7, 0, 0, 0},
{8, 7, 0, 10, 0, 0},
{13, 0, 10, 0, 10, 0},
{11, 0, 0, 10, 0, 9},
{7, 0, 0, 0, 9, 0},
};
int main() {
int no_edge; // chekka soni
// tanlangan cho'qqini kuzatish uchun massiv yarating
// tanlangan rost bo'ladi, aks holda noto'g'ri
int selected[V];
// dastlab noto'g'ri tanlangan
memset(selected, false, sizeof(selected));
// chekka sonini 0 ga o'rnating
no_edge = 0;
// minimal kenglikdagi daraxtdagi chekka soni
// har doim (V -1) dan kichik bo'ladi, bu erda V –
//grafikdagi uchlar soni
// 0-chi uchini tanlang va uni haqiqatga aylantiring
selected[0] = true;
int x; // row number
int y; // col number
// chekka va og'irlik uchun chop etish
cout << "Edge"
<< " : "
<< "Weight";
cout << endl;
while (no_edge < V - 1) {
//S to‘plamdagi har bir qirra uchun barcha qo‘shni qirralarni toping
// , 1-bosqichda tanlangan qirragacha bo'lgan masofani hisoblang.
// agar qirra allaqachon S to'plamida bo'lsa, aks holda uni tashlang
//1-bosqichda tanlangan qirraga eng yaqin bo'lgan boshqa qirrani tanlang
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {
if (selected[i]) {
for (int j = 0; j < V; j++) {
if (!selected[j] && G[i][j]) { // tanlanmagan va chekka mavjud
if (min > G[i][j]) {
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
cout << x << " - " << y << " : " << G[x][y];
cout << endl;
selected[y] = true;
no_edge++;
}
return 0;

}