Реферат: Графы. Решение практических задач с использованием графов (С++)

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++){

if(graph[v][w] && !added(v))// меняем ближайшую вершину остова

if(bet[v]>graph[v][w]){alf[v]=w; bet[v]=graph[v][w];}

}

}

}

void out(){

int weight=0;

fprintf(fo,"%d\n",num_ver);

for(int i=0;i<num_ver;i++){

fprintf(fo,"%2d\ %2d\ %2d\n",SST[i].b,SST[i].e,SST[i].weigh);