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

int num_edge; //количество ребер в остове

int n; //количество ребер

bool *nov; //признак прохода вершины

void sort(edge *arr){ //сортировка ребер по весу

edge tmp;

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

for(int j=n-1;j>i;j--)

if(arr[j].weigh<arr[j-1].weigh){

tmp = arr[j-1]; arr[j-1] = arr[j]; arr[j] = tmp;

}

}

int smezh(int v1,edge v2){

//определяет вершину смежную с v1 через ребро v2

if(v1==v2.beg)return(v2.end);

else if(v1==v2.end)return(v2.beg);

else return -1; // вершина v1 и ребро v2 не инцидентны

}

bool cycle(int v,int v0){ //определяет наличие цикла

nov[v] = 0; // v пройдена

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

if(smezh(v,SST[i])!=-1) //если смежны

if(smezh(v,SST[i])==v0)return 1; //из конца ребра пришли в начало

else if(nov[smezh(v,SST[i])]) // новая вершина

if(cycle(smezh(v,SST[i]),v0))return 1;

nov[v] = 1; //возвращаемся назад

return 0;

}

void kruskal(){

num_edge = 0; //остов пуст