Algoritimlarni loyihalash” fanidan Labaratotiya ishi-7-8 Mavzu

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

“Algoritimlarni loyihalash” fanidan

Labaratotiya ishi-7-8

Mavzu: Graflar bilan ishlovchi sodda algoritmlar.Graflarni tasvirlash. Eniga va tubiga qarab qidirish.

Bajardi: CAL024 Samsokov Navruzbek

Тoshkent – 2020

Laboratoriya mashg’uloti №7-8. Graflar bilan ishlovchi sodda algoritmlar.Graflarni tasvirlash. Eniga va tubiga qarab qidirish

#include

using namespace std;

#define V 7

int v;

int minKey(int key[], bool mstSet[])

{

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (mstSet[v] == false && key[v] < min)

min = key[v], min_index = v;

return min_index;

}

int findpath(int a[V][V], int s, int g){

int p=V;

int x[V];

int infinity=1000;

int t[V];

int h[V];

int u;

for (u=0;u


{

t[u]=infinity;

x[u]=0;

}

h[s]=0;

t[s]=0;

x[s]=1;

v=s;

while(1)

{

for(u=0;u

{

if(a[v][u]==0)continue;

if(x[u]==0 && t[u]>t[v]+a[v][u])

{

t[u]=t[v]+a[v][u];

h[u]=v;

}

}

int w=infinity;

v=-1;

for(u=0;u


{

if(x[u]==0 && t[u]

{

v=u;

w=t[u];

}

}

if(v==-1)

{

cout<<"\nBu uchlar oralig'ida hech qanday yo'l yoq "<

break;

}

if(v==g) {

cout<

u=g;

while(u!=s)

{

cout<";

u=h[u];

}

cout<

break;

}

x[v]=1;

}

}

void printMST(int parent[], int graph[V][V])

{

cout<<"uchlari: | og'irligi\n";

for (int i = 1; i < V; i++)

cout<

}

void primMST(int graph[V][V])

{

int parent[V];

int key[V];

bool mstSet[V];

for (int i = 0; i < V; i++)

key[i] = INT_MAX, mstSet[i] = false;

key[0] = 0;

parent[0] = -1;

for (int count = 0; count < V - 1; count++)

{

int u = minKey(key, mstSet);

mstSet[u] = true;

for (int v = 0; v < V; v++)

if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])

parent[v] = u, key[v] = graph[u][v];

}

printMST(parent, graph);

}

void printgraph(int graph[V][V]){

for (int i = 0; i

{ cout< ";

for (int j = 0; j

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

printf("\n");

}

}

int main()

{

int graph[V][V] = { { 0, 0, 21, 71, 0, 0, 63 },

{ 0, 0, 9, 83, 7, 0, 70 },

{ 21, 9, 0, 0, 0, 18, 0 },

{ 71, 83, 0, 0, 57, 87, 93 },

{ 0, 7, 0, 57, 0, 6, 59 },

{ 0, 0, 18, 87, 6, 0, 66 },

{ 63, 70, 0, 93, 59, 66, 0 } };

cout<<"Berilgan graph: \n";

printgraph(graph);

cout<

mark:

cout<<"\n*************** Menu ****************\n";

cout<<"1. Grafning uchlari va og'irligi\n";

cout<<"2. Grafning uchlari orasidagi eng qisqa masofa va uning og'irligi\n\n";

int n;

cout<<"\n\nMenyudan tanlang: ";

cin>>n;

system("CLS");

switch(n){

case 1: {

cout<<"\nBerilgan graph: \n";

printgraph(graph);

cout<

primMST(graph);

break;

}

case 2: {

cout<<"\nBerilgan graph: \n";

printgraph(graph);

int a,b;

cout<<"\nOrasidagi masofani topish kerak bo'lgan uchlarni kiririting:(0-7) ";

cin>>a>>b;

findpath(graph,a,b);

break;

}

default: cout<<"Mavjud bo'lmagan buyruqni tanladingiz";

}

cout<<"\n\nBosh menyuga qaytasizmi? (ha/yoq)\n";

string q;

cin>>q;

if(q=="ha"){

goto mark;

}else{

exit;

}

return 0;

}