6-26-4.c

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

#include<stdio.h>
#define N 10
int n;
void print();//声明
///////////////////////////////////////////////////////////
void input(int b[N][N],char a[N])//输入邻接矩阵函数
{
	int i,j;
	printf("输入结点个数：");
	scanf(" %d",&n);
	printf("输入结点集：\n");
	for(i=0;i<n;i++)
		scanf(" %c",&a[i]);
	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])//warshall算法
                                  //求可达性矩阵
{
	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;
			 }
					
 
}
///////////////////////////////////////////////////////////
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 zfbibao(int b[N][N],int t[N][N])
{
	int i,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++)
		t[i][i]=1;
}
///////////////////////////////////////////////////////////
void chuli(int b[N][N],int t[N][N])
{
	int i,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=i+1;j<n;j++)
		      if(t[i][j]*t[j][i]==0)
			  {   
				   t[i][j]=0;
			       t[j][i]=0;
			   }
} 
			   
///////////////////////////////////////////////////////////			   
void dchbibao(int b[N][N],int t[N][N])
{
	int i,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++)
	  { 
		  if(i!=j&&b[i][j]==1)
			  t[j][i]=1;
	  }
	
  
}
/////////////////////////////////////////////////////////////////

void shangji(int b[N][N],char a[N]) 
{
	int i,j;
	printf("\n");
	for(i=0;i<n;i++)
		if(b[i][i]==1)
		{
			printf("{%c",a[i]);
			for(j=i+1;j<n;j++)
				if(b[i][j]==1)
				{
					b[j][j]=0;
					printf(",%c",a[j]);
				}
            printf("},");
		}
		printf("\b");
    printf("\n");
}

///////////////////////////////////////////////////////////

main()
{
	char A[N];
	int  B[N][N],t[N][N];
	
    input(B,A);
    printf("其可达性矩阵为\n");
    keda(B,t);
    print(t);
	/////////////////////////////////////////////强分图
	chuli(t,t);
    zfbibao(t,t);
	printf("其强分图可由以下结点集导出");
	shangji(t,A);
	/////////////////////////////////////////////弱分图  
    zfbibao(B,t);
	dchbibao(t,t);
	keda(t,t);
	printf("其弱分图可由以下结点集导出");
	shangji(t,A);

		   
	   
	   
}