#include <stdio.h>
#define KNOTENZAHL 5

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

void InitialisiereAlles(short AA[KNOTENZAHL][KNOTENZAHL],short  FF[KNOTENZAHL],short  DD[KNOTENZAHL],short VV[KNOTENZAHL],short  QEQE[KNOTENZAHL])
{
	short i=0,j=0; 
	
	for(i=0;i<KNOTENZAHL;i++)
	{
		FF[i]=0;
		DD[i]=KNOTENZAHL;
		QEQE[i]=-1;
		VV[i]=-1;
		for(j=0;j<KNOTENZAHL;j++)
		      AA[i][j]=0; 
	}
	return;  
}

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

void EingabeA(short AA[KNOTENZAHL][KNOTENZAHL])
{
	short i=0,j=0; 
	
	for(i=0;i<KNOTENZAHL;i++)
	{
		for(j=0;j<KNOTENZAHL;j++)
		{
			if(i!=j)
			{
				printf("Falls es eine Kante vom Knoten %hi zum Knoten %hi gibt, geben Sie bitte 1 ein, sonst 0: ",(i+1),(j+1));
				scanf("%hi",&AA[i][j]);
				while(AA[i][j]!=0 && AA[i][j]!=1)
				{
					printf("Noch einmal ordentlich: ");
					scanf("%hi",&AA[i][j]); 
				}
			}
		}
	} 
	return;
}
  
/*----------------------------------------------*/ 
 
void KontrollausgabeA(short AA[KNOTENZAHL][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 sk, short  DD[KNOTENZAHL],short VV[KNOTENZAHL])
{
	short i=0,dd=0,vv=0;
       
	printf("Startknoten:  %hi.\n",(sk+1));
	for(i=0;i<KNOTENZAHL;i++)
	{
		if(i!=sk)
		{
			printf("Knoten %hi: ",(i+1)); 
			if(VV[i]==-1)
			{
				printf("unerreichbar.\n");
			}
			else  
			{
				printf("Abstand zum Startknoten: %hi; Vorgaenger: %hi",DD[i],(VV[i]+1));
				dd=DD[i];
				vv=VV[i];
				while(dd>1)
				{
					vv=VV[vv];
					dd--;
					printf(", %hi",(vv+1));
				}
				printf(". \n");	 
			}
		}
	}
	return;    
}
    
/*----------------------------------------------*/   

int main(void)
{
  
	short s=0,Q=0,knz=KNOTENZAHL;
	short A[KNOTENZAHL][KNOTENZAHL], F[KNOTENZAHL], D[KNOTENZAHL],V[KNOTENZAHL], QE[KNOTENZAHL];
	short u=0,v=0,i=0,frage=1;
  
	InitialisiereAlles(A,F,D,V,QE);
  
	printf("Dieses Programm fuehrt eine Breitensuche in einem Graphen mit den Knoten 1,2,...%hi durch.\nZunaechst geben Sie bitte die Adjazenzmatrix ein.\n",knz);
  
	EingabeA(A); 
	KontrollausgabeA(A);
  
	while(frage==1)
	{
		InitialisiereRest(F,D,V,QE);  
    
		printf("Von welchem Startknoten aus sollen wir suchen?\nGeben Sie eine Zahl zwischen 1 und %hi ein: ",knz);
		scanf("%hi",&s);
		while(s<1 || s>knz)
		{
			     printf("Noch einmal ordentlich: ");
			     scanf("%hi",&s); 
		}
		
		s=s-1;
		F[s]=1;
		D[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[v]=D[u]+1;
					V[v]=u;
					QE[Q]=v;
					Q=Q+1;     
				}
			}
    
			F[u]=2;
		}
  
		AusgabeSuchergebnis(s,D,V);
  
		printf("Moechten Sie denselben Graphen von einem anderen Startknoten aus durchsuchen?\nIn diesem Falle geben Sie nun eine 1 ein.\nMoechten Sie das Programm beenden, geben Sie eine 0 ein. \nIhr Wunsch: ");
		scanf("%hi",&frage); 
  
	}
  
  
	return(0);
}