#include <stdio.h>
#define KNOTENZAHL 5

/*-------------------------------------*/

void InitialisiereAD(short AA[KNOTENZAHL][KNOTENZAHL], short  DD[KNOTENZAHL][KNOTENZAHL])
{
	short i=0,j=0; 
	
	for(i=0;i<KNOTENZAHL;i++)
	{
		for(j=0;j<KNOTENZAHL;j++)
		{
			AA[i][j]=0; 
			DD[i][j]=KNOTENZAHL;
		}
	}
	return;  
}
 
/*-------------------------------------*/

void InitialisiereFVQE(short  FF[KNOTENZAHL], short VV[KNOTENZAHL],short  QEQE[KNOTENZAHL])/* Hier bleibt die Adjazenzmatrix und die  Abstandsmatrix unveraendert*/
{
	short i=0; 
       
	for(i=0;i<KNOTENZAHL;i++)
	{
		FF[i]=0;
		QEQE[i]=-1;
		VV[i]=-1;
	 
	}
	return;  
}  


/*-------------------------------------*/


void EingabeA(short AA[KNOTENZAHL][KNOTENZAHL], short knotenzahl)
{
	short i=0, eingabe=0; 
	
	printf("Geben Sie dazu jeweils die zu dem genannten Knoten adjazenten Knoten ein; Abschluss durch Eingabe von '0'.\n");
 
	  for(i=0;i<knotenzahl;i++)
	{
		printf("Zum %hi. Knoten adjazente Knoten:\n", (i+1));
		scanf("%hi", &eingabe);
	   
		while(eingabe)
		{
			if(eingabe<0 || eingabe ==(i+1) || eingabe > knotenzahl)
			printf("Unzulaessige Eingabe, wird ignoriert.\n");
			else
			AA[i][(eingabe-1)]=1;
		  
			scanf("%hi", &eingabe);
		}
	   
	} 
	return;
}
  
 
/*-------------------------------------*/
 
void KontrollausgabeA(short AA[KNOTENZAHL][KNOTENZAHL], short  knotenzahl)
{
	short i=0,j=0; 
	
	for(i=0; i<knotenzahl; i++)
	{
		for(j=0; j<knotenzahl; j++)
		{
			if(i!=j)
				printf("Kante vom Knoten %hi zum Knoten %hi:  %hi.\n",(i+1),(j+1),AA[i][j]);
		}
	} 
	return;
} 

 
/*-------------------------------------*/
  
void AusgabeSuchergebnis(short  DD[KNOTENZAHL][KNOTENZAHL], short knotenzahl)
{
	short s=0, i=0;
       
	for(s=0;s<knotenzahl;s++)
	{      
       
		printf("Startknoten:  %hi.\n",(s+1));
		for(i=0;i<knotenzahl;i++)
		{

			printf("Knoten %hi: ",(i+1)); 
			if(DD[s][i]==knotenzahl)
				printf("unerreichbar.\n");
			else  
				printf("Abstand zum Startknoten: %hi.\n", DD[s][i] );
		}
	  
	}  
	return;    
}

 
/*-------------------------------------*/

void Abstandsbestimmer(short  A[KNOTENZAHL][KNOTENZAHL], short  D[KNOTENZAHL][KNOTENZAHL], short knz)
{
	short s=0, Q=0;
	short  F[KNOTENZAHL], V[KNOTENZAHL], QE[KNOTENZAHL];
	short u=0,v=0,i=0;
       
    
	for(s=0; s<knz;s++)
	{
		InitialisiereFVQE(F, V, QE);  
  
		F[s]=1;
		D[s][s]=0;
		V[s]=-1;
		Q=1;
		QE[0]=s;
	
		while(Q>0)
		{
			u=QE[0];
			Q=Q-1;
			for(i=1;i<(Q+1);i++)
				QE[(i-1)]=QE[i]; 

			QE[Q]=-1;
	
			for(v=0;v<KNOTENZAHL;v++)
			{
				if(A[u][v]==1 && F[v]==0)
				{
					F[v]=1;
					D[s][v]=D[s][u]+1;
					V[v]=u;
					QE[Q]=v;
					Q=Q+1;
				}
			}
    
			F[u]=2;
		}
  
	}
     
	return;
  
}
 
/*-------------------------------------*/

int main(void)
{
  
	short knz=KNOTENZAHL;
	short A[KNOTENZAHL][KNOTENZAHL],  D[KNOTENZAHL][KNOTENZAHL];
  
	printf("Dieses Programm fuehrt eine Breitensuche in einem Graphen mit den Knoten 1, 2, ...%hi ohne Schlingen durch.\nZunaechst geben Sie bitte die Adjazenzmatrix ein.\n",knz);
     
	InitialisiereAD(A,D);    
  
	EingabeA(A, knz); 
	KontrollausgabeA(A, knz);
  
	Abstandsbestimmer(A, D, knz);
  
	AusgabeSuchergebnis(D, knz);
  
	return(0);
  
}