Tizimli va amaliy dasturlashtirish

O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI


MUHAMMAD ALXORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

“TIZIMLI VA AMALIY DASTURLASHTIRISH” KAFEDRASI


MA’LUMOTLAR TUZILMASI VA ALGORITMLAR
FANIDAN
6-AMALIY ISH TOPSHIRIG‘I. GRAFLARNI TASVIRLASH USULLARI. GRAFLARDA KO‘RUV ALGORITMLARI. GRAFLARDA ENG QISQA YO‘LNI ANIQLASH ALGORITMLARI.
BAJARDI: Razzoqov s
QABUL QILDI: _______________________
___________________________________

TOSHKENT – 2023

6-AMALIY ISH TOPSHIRIG‘I. GRAFLARNI TASVIRLASH USULLARI. GRAFLARDA KO‘RUV ALGORITMLARI. GRAFLARDA ENG QISQA YO‘LNI ANIQLASH ALGORITMLARI
Ishning maqsadi: Graf abstrakt ma'lumot tuzilmalarining nazariy asoslari bo'yicha bilimlarni mustahkamlash. Graflarda qayta ishlashning asosiy algoritmlarini, taqdim etish usullarini o'rganish. C++ dasturlash tilida graf tuzilmasini dasturlash ko'nikmalarini o'zlashtirish.
Graf-bu ikkita cheklangan to'plamning yig'indisi: nuqtalar to'plami va bu nuqtalarning bir qismini juft-juft qilib bog'laydigan chiziqlar to'plami. Nuqtalar to'plami grafning cho‘qqi-tugunlari deb ataladi. Grafning tugunni bog'laydigan ko'plab chiziqlar grafning qirralari (yoylari) deb ataladi.
Yo‘naltirilmagan, yo‘naltirilgan va o‘girlikka ega bo‘lgan graflarni kompyuter dasturlash tillari hotirasida ifodalash, ya'ni xotirada tashkil etish uchun statik tuzilmasi matritsadan yoki dinamik tuzilmasi ro‘yxatlardan foydalanish mumkin.
Yo‘naltirilmagan, yo‘naltirilgan va o‘girlikka ega bo‘lgan graflarni ifodalash uchun har usulining o‘zining qoida asosida shakllanadi. Shunday to‘rtta usullarni ajratish mumkin:
- Qo'shma matritsa (adjacency matrix);
- Intsidientlik matritsa (incidence matrix);
- Qo'shnilik ro'yxati (adjacency list);
- Qirralar ro'yxati (edges list).


///////////////////////////////////////////////////////////////////////////////////////////////////////////////
TOPSHIRIQNI BAJARISH NAMUNASI
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
Graf berilgan. Qo'shni matritsani yarating. Ma'lumotlar tuzilmasi bilan ishlash standart amal - protseduralari tavsiflang (tuzilmani yaratish, element qo'shish, olib tashlash, chiqarish).
#include
#include
#include
using namespace std;


void allocMatrix(int** &A, int n, int m)
{
A = new int* [n];
for (int i=0; i
A[i] = new int [m];
}


void freeMatrix(int** &A, int n)
{
for (int i=0; i
delete A[i];
delete []A;
}


void initMatrix(int** &A, int n, int m)
{
for (int i=0; i
for (int j=i; j
if (i==j) A[i][j] = 0;
else A[i][j] = A[j][i] = rand()%2;
}


void printMatrix(int** A, int n, int m)
{
for (int i=0; i
for (int j=0; j
cout << A[i][j] << ( (j!=m-1)?"\t":"\n");
}


int main()
{
srand(time(0));
setlocale(0,"rus");
int **M;
int raz=0;
cout<<"Graf tartibini kiriting\n";
cin>>raz;
int row=raz,col=raz;
allocMatrix(M,row,col);
initMatrix(M,row,col);
printMatrix(M,row,col);
freeMatrix(M,row);
system("pause");
system("cls");
main();
return 0;
}


///////////////////////////////////////////////////////////////////////////////////////////////////////////////
TOPSHIRIQNI BAJARISH NAMUNASI
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
Dijkstra algoritmi yordamida eng qisqa yo'llarni hisoblash
#include
#include
using namespace std;
const int V=5;


void Dijkstra(int GR[V][V], int st) {
int distance[V], count, index, i, u, m=st+1;
bool visited[V];
int path[V];
for (i=0; i
distance[i]=INT_MAX; visited[i]=false;
}
distance[st]=0;
for (count=0; count
int min=INT_MAX;
for (i=0; i
if (!visited[i] && distance[i]<=min){
min=distance[i]; index=i;
}
u=index;
visited[u]=true;
for (i=0; i
if (!visited[i] && GR[u][i] && distance[u]!=INT_MAX && distance[u]+GR[u][i]
distance[i]=distance[u]+GR[u][i];
}
cout<<"Masofalar matritsasi:\t\n";
for (i=0; i
if (distance[i]!=INT_MAX)
cout< "<
else cout< "<
}


int main()
{
setlocale(0,"rus");
int start, GR[V][V]={
{0, 10, 0, 30, 100},
{10, 0, 50, 0, 0},
{0, 50, 0, 20, 10},
{30, 0, 20, 0, 60},
{100, 0, 10, 60, 0},
};
for (int i=0; i
for (int j=0; j
cout << GR[i][j] <<( (j==V-1)?"\n":"\t");


cout<<"Cho`qqini tanlang >> "; cin>>start;
Dijkstra(GR, start-1);
system("pause>>void");
}