6-26-5.c

这是离散数学中集合与图论部分的算法实现 压缩包中有六个算法

 #include<stdio.h>
 #define N 20
 int n;//结点个数
 int f,q;//标志 
///////////////////////////////////////////////////////////
 void print(int t[N][N])//输出矩阵函数
{
   int i,j;
   for(i=0;i<n;i++)
	{	
		for(j=0;j<n;j++)
            printf(" %d ",t[i][j]);
		    printf("\n");
	}
}	
///////////////////////////////////////////////////////////
void Input(int b[N][N])//输入矩阵函数
{
    int i,j;
    printf("输入邻接矩阵(以零结束)：\n");
	    for(i=0;i<n;i++)
		   for(j=0;j<n;j++)
			   scanf("%d ",&b[i][j]);
	 printf("其邻接矩阵为：\n");
     print(b);
}
///////////////////////////////////////////////////////////
void keda(int b[N][N],int t[N][N])//求可达性矩阵
                                  //以后判断用
{
	int i,k,j;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
	       t[i][j]=b[i][j]; 
	for(i=0;i<=n;i++)
		for(j=0;j<n;j++)
		    for(k=0;k<n;k++)	
			 if(t[j][i]==1)   
				{
		        	if(t[j][k]==1)
						t[j][k]=1;
					else 
						if(t[i][k]==1)
						    t[j][k]=1;
					    else 
							t[j][k]=0;
			 }
			
}
///////////////////////////////////////////////////////////
int panduan(int b[N][N],int t[N][N])//首先判断其是否是树
{
	int i,j;
	int e=0;
	int k=1;
    for(i=0;i<N;i++)
		for(j=0;j<N;j++)
	       t[i][j]=b[i][j]; 
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			e=e+t[i][j];
    
    keda(t,t);
	for(i=0;i<n;i++)
		for(j=i+1;j<n;j++)
		{
			if(t[i][j]==1&&t[j][i]==1)
				k=0;break;
		}
		if(e==n-1&&k==1)//无回路且e=v-1
		{	
		     printf("\n\n  此有向图是一棵树\n");
		     f=1;//标志赋 1
		}
		else 
		{
			printf("\n    此有向图根本不是树\n");
		     f=0;
		}
		return f;
}
///////////////////////////////////////////////////////////
int genshu(int b[N][N])//判断其是否为根树
{ 
	int i,j;
	 int k1=0;
	 int k2=0;
	 int k=0;
 for(j=0;j<n;j++)
	 { 
		 for(i=0;i<n;i++)
		 {
			 k=k+b[i][j];
		 }
	  
		 if(k==0)
		 {   
			 k1++;
	     	 f=j;
		 }
		 if(k==1)
			 k2++;
		 k=0;
	 }
	 
	 if(k1==1&&k2==n-1)
	 {
		 printf("********它也是根树********\n");
	     printf("\n其根为:   %d\n",f+1);
		 q=1;//标志赋 1
	 }
	 else 
	 { 
		 printf("\n******但它不是根树****** \n");
		 q=0;
	 }
	 return q;
}
///////////////////////////////////////////////////////////
void genye(int b[N][N])//找出树叶	
{
	int i,j,k;
    printf("\n其树叶为: \n");
	printf("    { ");
	 for(i=0;i<n;i++)
	 {	
		 for(j=0;j<n;j++)
         {
			k=k+b[i][j];
		 }
	     
		 if(k==0)
		 {
		    f=i;
		    
			printf("%d, ",f+1);
		 }
		 k=0;
		
	 }
	 printf("\b\b ");	
	 printf(" }");
	printf("\n");	    	 
}
/////////////////////////////////////////////////////////// 
 void main()
 {
	 int i;
	 int b[N][N];
	 int t[N][N];
     printf("输入结点个数：");
	 scanf(" %d",&n);
	 printf("其默认的结点为:\n");
	 for(i=0;i<n;i++)
		 printf("%d, ",i+1);
	 printf("\b\b \n");
     Input(b);
	 panduan(b,t);
      if(f==1)
	  {  
	    genshu(b);
		if(q==1)
		{
		  genye(b);
		}
	  }
 }