Алгоритм Соллина построения дерева минимального веса, страница 2

Arrow *ar;

int x,y;

for(int i=0;i<=8;i++)  //вывод шахматной доски

{

if(i<8)

{

setcolor(15);

moveto(40*(i+1)+15,30);

sprintf(msg, "%d",i);

outtext(msg);

moveto(30,40*(i+1)+15);

sprintf(msg, "%d",i);

outtext(msg);

}

line(40,40*(i+1),360,40*(i+1));

line(40*(i+1),40,40*(i+1),360);

}

for(i=0;i<8;i++) //вывод надписей к вершинам и вывод значений весов ребер

{

if(i<7) {

moveto(peak[i][0]*40+45,peak[i][1]*40+45);

circle(peak[i][0]*40+60,peak[i][1]*40+60, 8);

sprintf(msg, " %d",i);

outtext(msg);}

moveto(370,50+20*i);

sprintf(ms,"weight of edge (%d,%d)=%d",ed2[i][0],ed2[i][1],lng[i]);

outtext(ms);

}

while (tmp) //вывод самого графа

{

if (tmp->first)

{

ar=tmp->first;

while (ar)

{

setcolor (ar->color+1);

line (tmp->x*40+58,tmp->y*40+58,ar->end->x*40+58,ar->end->y*40+58);

ar=ar->next;

}

}

tmp=tmp->next;

}

}

int is_full (void) //1 если весь граф одного цвета

{

Node *tmp=start_node;

int k;

while (tmp)

{

if (tmp->color) k=tmp->color; //найдем раскрашеную вершину

tmp=tmp->next;

}

tmp=start_node;

while (tmp)

{

if (tmp->color!=k) return 0;

tmp=tmp->next;

}

return 1;

}

void put (void) //нахождение минимального пути методом Соллина

{

float summa,min;

int first_color;

Node *tmp=start_node, *min_svaz;

Arrow *ar,*min_ar, *tmp_a;

while (tmp) //соеденим каждую точку с её ближайшим соседом

{

min=1000;

ar=tmp->first;

while (ar)

{

if (ar->lengh < min)

{

min_svaz=ar->end;

min_ar=ar;

min=ar->lengh;

}

ar=ar->next;

}//нашли ближайшего соседа

color++;

tmp->color=color;

min_ar->color=color;

tmp_a=min_ar->end->first; //найдем ветвь, идущую в обратном направлении

while (tmp_a->end!=tmp) tmp_a=tmp_a->next;

tmp_a->color=color;

min_svaz->color=color;

print ();

getch ();

tmp=tmp->next;

}

//теперь все вершины, входящие в одну компоненту связности, окрасим в один цвет

getch ();

cleardevice();

tmp=start_node;

while (tmp)

{

ar=tmp->first;

while (ar)

{

if (ar->color!=0)

{

first_color=ar->end->color=tmp->color;

ar->color=first_color;

tmp_a=ar->end->first; //найдем ветвь, идущую в обратном направлении

while (tmp_a->end!=tmp) tmp_a=tmp_a->next;

tmp_a->color=first_color;

print ();

}

ar=ar->next;

}

tmp=tmp->next;

}

print ();

getch ();

while (!is_full())

{

min=1000;

tmp=start_node;

while (tmp)

{

ar=tmp->first;

while (ar)

{

if (ar->end->color != tmp->color && ar->lengh<min)

{

min=ar->lengh;

min_svaz=tmp;

min_ar=ar;

}

ar=ar->next;

}

tmp=tmp->next;

}//получили минимальную связь

int min_color;

if (min_svaz->color< min_ar->end->color) min_color=min_svaz->color;

else min_color=min_ar->end->color;

first_color=min_color;

min_svaz->color=first_color;

min_ar->color=first_color;

min_ar->end->color=first_color;

tmp_a=min_ar->end->first; //найдем ветвь, идущую в обратном направлении

while (tmp_a->end!=min_svaz) tmp_a=tmp_a->next;

tmp_a->color=first_color;

print ();

getch ();

}

}

float ves (void) //вычисление минимального веса

{

float ves=0;

Node  *tmp=start_node;

Arrow *ar;

while (tmp)

{

if (!tmp->p)

{

tmp->p=1;

ar=tmp->first;

while (ar)

{

if (ar->end->p==0 && ar->color!=0)

{

ves+=ar->lengh;

ar->end->p=1;

}

ar=ar->next;

}

}

tmp=tmp->next;

}

return ves;

}

void main(void)

{

clrscr();

int gdriver = DETECT, gmode, errorcode;

initgraph(&gdriver, &gmode, "..\\bgi");

getch();

for(int i=0;i<7;i++) add_node(i); //заполняем узлы

for (i = 0; i < 16; i++) add_arrow (edge[i][0], edge[i][1],i); //строим дерево

print(); //выводим информацию о графе

getch();

put ();

printf ("minimal summary weight = %f", ves ());

getch ();

}

Экранная форма: