Как проверить граф на связанность? Алгоритм Краскала

[PasSuper]

ЗАДАЧА О СЕТИ ДОРОГ НАИМЕНЬШЕЙ СТОИМОСТИ.
Задание
Написать программу на языке «Си», которая решает задачу о сети дорог наименьшей стоимости.
Дан связный неориентированный граф J, причем каждому ребру (i, j) приписан «вес», который можно понимать как стоимость дороги между пунктами i и j. Требуется выбрать из всех ребер графа такую совокупность, что по этим ребрам можно было бы пройти из любого пункта в любой другой, и чтобы общий вес этих ребер был минимальным.

Как проверить граф на связанность? Т. е. на то, что из каждой вершины можно попасть в любую другую.
Задача решается алгоритмом Краскала. Исходный код программы ниже или в прикрепленном документе

Очень жду помощи! буду очень благодарна!

[PasSuper]

исходный код программы:

#include <graphics.h>     
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

struct Rebro
{
   int p1,p2;
   int ves;
   int flag;
};

Rebro *reb;
int *ver;
int **arr;
int kolv=0,kolr=0;
float sum=0;

int Proverka(int v1, int v2)
{
	if (v1==v2) return 0;
	for (int g = 0; g<kolv; g++)
	{
		if ((reb[g].p1 == v1 && reb[g].p2==v2) || (reb[g].p1 == v2 && reb[g].p2 == v1))
		{
			return 0;
		
		}
	}
	return 1;
}

void Sohr() //funkciya sohraneniya grafa v fail
{
	FILE *fp;
	char fname[30]; //imja faila

	printf("\nVvedite nazvanie faila s rasshireniem: ");
	scanf("%s",&fname);
	fp=fopen(fname, "w");
	if(fp==NULL)
	{
		printf ("\t Oshibka!");
		getch();
		return;
	}
	fprintf(fp,"%i %i\n", kolv,kolr);

	for(int i=0; i<kolr; i++)
	{
		fprintf(fp,"%i %i %i\n", reb[i].p1, reb[i].p2, reb[i].ves);
	}

	for(i=0; i<kolv; i++)
	{
		fprintf(fp,"%i %i\n", arr[i][0], arr[i][1]);
	}
	fclose(fp);
}


void Keyboard()
{
   int i,j,a;
   int save=0;
   int min_kolr, max_kolr; //min i maks znachenie kol-va reber pri dannom kol-ve vershin
		
   clrscr();
   printf("\nVvedite kolichestvo vershin v grafe: ");
   do
   {
      scanf("%i",&kolv);	  
   }
   while(kolv<0 || kolv>50);
   
   ver=new int[kolv];

	min_kolr = kolv-1;
	max_kolr = (kolv*(kolv-1))/2;
	printf("\nVvedite kolichestvo reber grafa  ");
	do
   {
      scanf("%i",&kolr);
	  if ((kolr > max_kolr) || (kolr< min_kolr)) printf("Bad Value! Nedopustimoe kol-vo reber! Poprobuite snova ");	  
   }
   while((kolr > max_kolr) || (kolr< min_kolr));

	reb=new Rebro[kolr];
	int kolreb =kolr;
   
		for(i=0,j=0; i<kolv; i++)
		{
			a=0;
			do
			{
				do
				{	
					printf("\nVvedite nomer vershini, s kotoroi svjazana vershina %i \n (esli takih vershin bol'she net, vvedite 0) ",i+1);
					scanf("%i",&a);
				}while (a>kolv || a<0);
				int fl = 1;
		
				if(!Proverka(i+1, a)) //esli petlja ili takaja svjaz' uge est'
				{
					printf ("Bad value! Takoe rebro uge zadano ili obrazovalas' petlja. Please try again!\n");
					fl = 0;
					
				}

				if(a && fl != 0)
				{
					reb[j].p1=i+1;
					reb[j].p2=a;
					do
					{
						printf("Vvedite ves rebra: ");
						scanf("%d",&reb[j].ves);
					} while (reb[j].ves<0);
					reb[j].flag=0;
					j++;
					kolreb--;
				}
				if (kolreb == 0)
				{
					printf("Vse rebra vvedeny!\n");
					i=kolv;
					break;
				}
			} while(a!=0 && kolreb!=0);
		}
		
   
	
   arr=new int*[kolv];
   int q=360/kolv;		
    for(i=0; i<kolv; i++)
	{
		arr[i]=new int[2];
		arr[i][0]=320+cos( (M_PI/180)*(q*i) )*210;

		arr[i][1]=240+sin( (M_PI/180)*(q*i) )*210;

	}
	printf("\tDo you want to save your graph?\n");
	printf("\t[1]->YES\n\t[2]->NO\n");
	do
	{
		scanf("%i",&save);
	}
	while((save<1)||(save>2));
	if (save == 1) Sohr();
   getch();
}

void Sluchaino()
{
   int i,g,a;
   int min_kolr, max_kolr; //min i maks znachenie kol-va reber pri dannom kol-ve vershin
   FILE* out = fopen("graf.txt","w");
   clrscr();
   randomize();
   printf("Vvedite kolichestvo vershin grafa  ");
   	do
   {
      scanf("%i",&kolv);	  
   }
   while(kolv<0 || kolv > 50);
	fprintf(out,"%d ",kolv);
ver=new int[kolv];
		
	min_kolr = kolv-1;
	max_kolr = (kolv*(kolv-1))/2;
	printf("\nVvedite kolichestvo reber grafa  ");
	do
   {
      scanf("%i",&kolr);
	  if ((kolr > max_kolr) || (kolr< min_kolr)) printf("Bad Value! Nedopustimoe kol-vo reber! Poprobuite snova");	  
   }
   while((kolr > max_kolr) || (kolr< min_kolr));
	fprintf(out,"%d\n",kolr);
	
	
	reb=new Rebro[kolr];

	int x=0;
	int kolreb = kolr;
	
	for (int m=0; m<kolv; m++)
	{
		reb[m].p1 = 0;
		reb[m].p2 = 0;
	}
	//while(Svjaznost())
	//{
		g=0;
		while(kolreb)
		{
			for(i=0; i<kolv; i++)
			{
				reb[g].p1 = i+1;
				x = random (kolv)+1;
				if(Proverka(i+1, x))
				{
					
					reb[g].p2 = x;
					reb[g].ves = random(50)+1;
					fprintf(out,"%d %d %d\n",i+1, x, reb[g].ves);
					reb[g].flag=0;
					g++;
					kolreb--;
				}
			}
		}

	//}

   arr=new int*[kolv];
   int q=360/kolv;
	for(i=0; i<kolv; i++)
	{
		arr[i]=new int[2];
		arr[i][0]=320+cos( (M_PI/180)*(q*i) )*210;
		fprintf(out,"%d ",arr[i][0]);
		arr[i][1]=240+sin( (M_PI/180)*(q*i) )*210;
		fprintf(out,"%d\n",arr[i][1]);
	}
   fclose(out);
   getch();
}

[PasSuper]

void File() // vvod dannih o grafe is faila
{
   char fname[30]; //imja faila

   printf("Vvedite nazvanie faila s rasshireniem: ");
   scanf("%s",&fname);
	int j=0;
   FILE *fp=fopen(fname,"r");
   if(fp==NULL)
   {
	  printf("\nNe udaetsya otkryt' fail!\n");
	  getch();
	  return;
   }

   fscanf(fp,"%d %d\n",&kolv,&kolr);
   ver=new int[kolv];
   for (int l = 0; l<kolv; l++)
		ver[l] = 0;

   reb=new Rebro[kolr];

   for(int i=0; i<kolr; i++)
   {
	  fscanf(fp,"%d %d %d\n",&reb[i].p1,&reb[i].p2,&reb[i].ves);
	  reb[i].flag=0;
   }

   arr=new int*[kolv];

   for(i=0; i<kolv; i++)
   {
	  arr[i]=new int[2];
	fscanf(fp,"%d %d\n",&arr[i][0],&arr[i][1]);
   }
   fclose(fp);
}

void SortInsert() //sortirovka reber po vozrastaniyu po ih vesu
{
   int i,j;
   Rebro tmp;

   for(i=1; i<kolr; i++)
   {
	  j=i;
	  tmp.p1=reb[j].p1;
	  tmp.p2=reb[j].p2;
	  tmp.ves=reb[j].ves;
	  while((reb[j-1].ves>tmp.ves) && (j>0))
	  {
		 reb[j].p1=reb[j-1].p1;
		 reb[j].p2=reb[j-1].p2;
		 reb[j].ves=reb[j-1].ves;
		 j--;
	  }
	  reb[j].p1=tmp.p1;
	  reb[j].p2=tmp.p2;
	  reb[j].ves=tmp.ves;
   }

}

void SearchTree() //ustranenie ciclov
{
   int n=1;
   int i;
   ver[reb[0].p1-1]=1; // prisvoenie znacheniya 1 vershinam, soedinyayuschim pervoe rebro
   ver[reb[0].p2-1]=1; // s etogo rebra nachnetsya poisk dereva, tak kak ono uje tochno samoi malen'koi stoimosti
   reb[0].flag=1;// cherez eto rebro proidet doroga


   while(n) 
   {
      for(i=1; i<kolr; i++)
      {
	 	if(ver[reb[i].p1-1] && ver[reb[i].p2-1])
			continue; //dorogi ne budet (obrazuetsja cikl)
		if(!ver[reb[i].p1-1] && ver[reb[i].p2-1])
	 	{
				ver[reb[i].p1-1]=1;
				reb[i].flag=1;
	   	 	i=0;
	   		 continue;
	 	}
	 	if(!ver[reb[i].p1-1] && ver[reb[i].p2-1])
		{
			ver[reb[i].p1-1]=1;
			reb[i].flag=1;
			i=0;
			continue;
		}
		if(ver[reb[i].p1-1] && !ver[reb[i].p2-1])
		{
			ver[reb[i].p2-1]=1;
			reb[i].flag=1;
			i=0;
		}
	  }
	  n=0;
	}
}

void DrawVer() //funkciya risovaniya vershin
{
   int i;
   char s[5];

   for(i=0; i<kolv; i++)
   {
	  circle(arr[i][0],arr[i][1],2);
	  sprintf(s,"%i",i+1);
	  if(arr[i][1]>10)
	 outtextxy(arr[i][0],arr[i][1]-10,s);// mestpolojenie nomera vershiny grafa i vyvod ego na ekran
	  else
	 outtextxy(arr[i][0],arr[i][1]+5,s);
   }
}

void DrawGraph() //funkciya risovaniya reber
{
   int i;
   double alpha;
   int dx,dy;

   for(i=0; i<kolr; i++)
   {
	  alpha=atan2(arr[reb[i].p1-1][0]-arr[reb[i].p2-1][0],arr[reb[i].p1-1][1]-arr[reb[i].p2-1][1]);
	  dx=(int)(2*sin(alpha));
	  dy=(int)(2*cos(alpha));
	  if(reb[i].flag) setcolor(LIGHTRED);
	  else setcolor(WHITE);
	  line(arr[reb[i].p1-1][0]-dx,arr[reb[i].p1-1][1]-dy,arr[reb[i].p2-1][0]+dx,arr[reb[i].p2-1][1]+dy);
	}
}

void DrawVes()
{
	int i;
   char s[5];
	setcolor(LIGHTRED);
	randomize();
	for(i=0; i<kolr; i++)
   {
			sprintf(s,"%d",reb[i].ves);
			outtextxy((arr[reb[i].p1-1][0]/2+arr[reb[i].p2-1][0]/2 + random(10)),(arr[reb[i].p1-1][1]/2+arr[reb[i].p2-1][1]/2 + random(10)),s);

   }
}

void Draw()
{
   if(kolv==0) return; //esli net vershin
   int gdriver=DETECT,gmode;
   initgraph(&gdriver,&gmode,"c:\\lang\\bc_31\\bgi");
   sum = 0;
   DrawVer(); // risuem vershiny
   DrawGraph(); // soedinjaem rebrami
	DrawVes();
   getch();

   SearchTree(); //zapusk funkcii ustraneniya ciklov
   for(int i=0; i<kolr; i++)
   {
	  if(reb[i].flag) sum+=reb[i].ves;
   }

   DrawGraph(); //risuem graf s podsvechennymi putyami dorog naimen'shei stoimosti
   setcolor(LIGHTRED);
   outtextxy(105,3,"Minimal'naya stoimost' seti dorog ravna ");
   char s[10];
   sprintf(s,"%f",sum);
   outtextxy(420,3,s);
   outtextxy(170, 11, "Press any key to continue!");
   getch();
   closegraph();
}

void main()
{
    int ch=0;
	do
	{
		clrscr();
		printf("\tProgramma reshaet zadachu o provedenii dorog naimen'shei stoimosti\n");

		int sposob=0; //vibor sposoba zapolnenia grafa
		printf("\nViberite sposob zapolnenia grafa:\n");
		printf("[1] -> s klaviaturi\n");
		printf("[2] -> is faila\n");
		printf("[3] -> sluchaino\n");
	
		do
		{
			scanf("%i",&sposob);
		}
	   while((sposob<1)||(sposob>3));

	   if(sposob==1) Keyboard();
	   else if(sposob==3)Sluchaino();
			else File();
	   
	   
	   for(int i=0; i<kolv; i++) ver[i]=0;
	   SortInsert();
	   Draw();
       
		clrscr();

	   printf("[1] -> nazad k menu\n");
	   printf("[2] -> EXIT\n");
	   do
	   {
			scanf("%i",&ch);
	   }
	   while((ch<1)||(ch>2));
	   
	} while (ch != 2 );

   delete[]*arr;
   delete[]ver;
   delete[]reb;
}

[MaTBeu]

Как проверить граф на связанность? Т. е. на то, что из каждой вершины можно попасть в любую другую.

Сделать цикл по всем вершинам. Начинаете с одной вершины. Ищете переходы на следующую. Помечаете предыдущую, как пройденную (чтобы не ходить по 2 раза). Потом повторяете переход. Проверили одну вершину, переходите к следующей. И так пока не пройдете.

[PasSuper]

Суть мне понятна. Ребра сортируются по возрастанию их веса. Через первое ребро точно есть дорога. Дальше перебором ищется следующее ребро (допустим дорога точно идет через ребро 1-3, тогда следующим будет ребро, у которого есть вершина 1 или 3 с наименьшим весом). В итоге, если после такого перебора не удалось добраться до каких-то вершин - будет ошибка. Допустим, всего 7 вершин, а перебрали мы всего 4 ->до остальных вершин путей нет.

Но я не понимаю, как это реализовать.
Знаю, что скорее всего проверка должна быть в фунции SearchTree, там как раз выше описанный алгоритм реализуется. Я просто не понимаю, как именно это сделать.

[Sapfil]

не совсем понимаю, что нужно... можете сделать пару рисунков (хоть в paint-е) и вложить сюда?

[PasSuper]

Во вложении объяснила еще раз алгоритм на конкретном примере. Надо проверить, не является ли граф разорванным.

[LeBron]

Сообщение от PasSuper

Суть мне понятна. Ребра сортируются по возрастанию их веса. Через первое ребро точно есть дорога. Дальше перебором ищется следующее ребро (допустим дорога точно идет через ребро 1-3, тогда следующим будет ребро, у которого есть вершина 1 или 3 с наименьшим весом). В итоге, если после такого перебора не удалось добраться до каких-то вершин - будет ошибка. Допустим, всего 7 вершин, а перебрали мы всего 4 ->до остальных вершин путей нет.

Нет, Вы описываете нечто, больше похожее на алгоритм Прима. Почитайте, что такое и как работает система непересекающихся подмножеств.
Чтоб был именно Краскал, надо после сортировки пройтись по всем ребрам, и для каждого ребра проверять, соеденяет ли оно 2 пока несвязанных подмножества вершин (2 пока определенные разные компоненты связности). Если да - объеденить эти 2 подмножества. Тогда можно не проверять вначале связность, а посмотреть вконце - сколько компонент связности получилось. Если сравнивать с простой проверкой на связность вначале - это работает быстрее, если с "умной" - это кодить меньше надо.

[PasSuper]

по крайней мере, так объяснил мой преподаватель. Значит нужно так делать...
Помогите с реализацией, пожалуйста!

[Sapfil]

Вот так у меня задаются ребра:

	int reb[9][3] = {1,2,2, 1,3,7, 1,4,8, 2,3,4, 2,4,5, 3,4,1, 5,6,6, 5,7,2, 6,7,4};

Здесь у меня массив из 9 строчек. В каждой из которых по 3 значения. первые два значения - это номера точек, которые соединяются этим ребром, а третье значение - вес ребра. Исходные данные взял из вашего графического файла.

Вот так я проверяю на связанность:

bool point[7] = {true};
	for (i=1; i<7; i++)
		point[i] = false;
	
	for (i=0; i<9; i++)
		if (point[reb[i][1]-1] | point[reb[i][0]-1])
			point[reb[i][1]-1] = point[reb[i][0]-1] = true;
	for (i=1; i<7; i++)
		point[0] = point[0]&point[i];
           if (point[0] == true)
                {...}

Здесь создается массив points, состоящий из семи элементов по количеству точек. Значение true для каждой точки означает, что данная точка присоединена к системе. Изначально значение true присвоено только первой точке (point[0]).

Затем перебираются все ребра и если в ребре хотябы одна точка уже присоединена к системе, то обоим присваивается значение true.

Затем значения всех элементов point логически перемножаются. Если все элементы point равны единице(true), то и результат перемножения равен единице - значит граф связанный. Если же хотя бы один элемент point равен нулю(false) - то результат перемножения всех элементов равен нулю - значит граф не связанный.

Этот алгоритм будет работать только в том случае, если в массиве reb все певые элементы строк (первая точка ребра) - будут раполагаться по возрастанию. В противном случае нужно сначала сортировать массив reb.

По исходным данным, конечно, граф не связанный.

Насчет алгоритма Краскала - спросил у википедии. Встаю на сторону PasSuper. Запрограммировал этот алгоритм и изменил исходные данные для первой точки вот так: ...1,6,2,... , чтобы связать граф. При таких исходных данных он мне подключил следующие ребра (по порядку подключения)
№6, №4, №2, №1, №9, №8. Надеюсь, это правильно...