Предыдущая страница реферата | 9  10  11  12  13  14  15  16  17  18  19 | Следующая страница реферата

}

bool added(int v){ // проверяет: добавлена вершина v в остов

for(int i=0;i<num_s;i++)if(v==S[i])return 1; 

return 0;

}

void prim(){ // построение остова

S = new int[calc_ver()]; 

int *alf = new int[p]; // ближайшие вершины, добавленные в остов 

int *bet = new int[p]; // длины ребер, соединяющие вершины с остовом 

int u = 0; // произвольная вершина 

S[num_s] = u; num_s++; // добавляем в остов 

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

if(graph[v][u]){alf[v] = u; bet[v] = graph[u][v];}//u - ближайшая вершина  

else {alf[v] = -1; bet[v] = MAXINT;} 

int w,x; 

for(int i=0;i<p-1;i++){ 

x = MAXINT; 

for(int v=0;v<p;v++){ // поиск ближайшей к остову вершины   

if(bet[v]<x && !added(v)){w = v; x = bet[v];}  

}  

S[num_s] = w; num_s++; // добавляем найденную вершину к остову  

// и ребро  

SST[num_ver].b=alf[w];SST[num_ver].e=w;SST[num_ver].weigh=graph[alf[w]][w];  

num_ver++;  

for(int v=0;v<p;v++){    

Рекомендуем скачать другие рефераты по теме: реферат памятники, бесплатные рефераты без регистрации.





Предыдущая страница реферата | 9  10  11  12  13  14  15  16  17  18  19 | Следующая страница реферата