MINISTERUL EDUCAIEI REPUBLICII MOLDOVA

UNIVERSITATEA TEHNIC A MOLDOVEI

Facultatea Calculatoare, Informatic i Microelectronic

Specialitatea :Tehnologii informationale

RAPORTLucrare de laborator nr.3

Analiza,proiectarea algoritmilor Tema: Algoritmi greedy.

A efectuat: st. gr. TI-133 Urmasnchi MihailA verificat: M. Catruc

Chisinau 2014

Scopul lucrrii:1. Studierea tehnicii greedy.2. Analiza i implementarea algoritmilor greedy.

Algoritmul Kruskal:KRUSKAL(V, E)

A { } Set A will ultimately contains the edges of the MSTfor each vertex v in V do MAKE-SET(v)sort E into nondecreasing order by weight for each (u, v) taken from the sorted list do if FIND-SET(u) = FIND-SET(v) then A A {(u, v)} UNION(u, v)return A

Codul programului:#include

#include

using namespace std;

int nrConexiuni,nrVirfuri;int MA[1000][3];int fin[1000];int mid[1000][100];int q=0;

void sortare(){ int temp[3]; for(int i=0;i

MA[j+1][0]=temp[0]; MA[j+1][1]=temp[1]; MA[j+1][2]=temp[2]; } } }}

void control(){ for(int i=1;i

mid[s][1]=mid[MA[i][0]][1]; } } } if(mid[MA[i][0]][1] == mid[MA[i][1]][1]){ cout

sortare();

for(int i=0;i

{ double t1,t2; int C[200][200]; int n,i,j,k,min;

int vecin[200],mincost[200],A[200];coutn;cout

for (j=0;j0 && mincost[j]

cout