zuoye1.cpp

图论课程设计的左右

// zuoye1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "stdlib.h"

//*******************************************************
int ** creat_blank(int n)
{
	int **p;
	for(int i=0;i<n;i++)
		p=new int * [n];
	for(i=0;i<n;i++)
		p[i]=new int [n];
	return p;
}
//********************************************************

void display(int **b,int n)    
{
	for( int i=0;i<n;i++)
		 {
			 for(int j=0;j<n;j++)
		   	 cout<<b[i][j]<<" ";
			 cout<<endl;
		 }
}
//*******************************************************
void road(int **a,int **c,int n,int m)    // vi 和 vj 之间长度为 m 的通路的个数
{
	int **b=creat_blank(n);

	m--;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
	    	b[i][j]=a[i][j];	
    while(m!=0)
	{
	 for( i=0;i<n;i++)
		for(int j=0;j<n;j++)
			c[i][j]=0;

     for( i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++)
			{
				c[i][j]+=a[i][k]*b[k][j];
			}
	 
      for( i=0;i<n;i++)
		for(int j=0;j<n;j++)
			b[i][j]=c[i][j];
			m--;
	}
	delete b;
}
//********************************************************************
void loop_matrix(int **a,int **c,int **d,int n)   //求可达矩阵
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			 d[i][j]=a[i][j];
   for(int q=0;q <n-1;q++)
	{
		road(a,c,n,q+2);
		for( i=0;i<n;i++)
			for(int j=0;j<n;j++)
			{   
				d[i][j]+=c[i][j];
				if(d[i][j]) d[i][j]=1;
			}
	}
	
	
}
//********************************************************************
void information(int **a,int n)                   //读入图的邻接矩阵
{
   cout<<"请输入图的邻接矩阵"<<endl;
   for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>a[i][j];
		
}
//*******************************************************************
int sum_loop_number(int **a,int **c,int n,int m)              //通路为m的总数
{   
	int sum=0;
	road(a,c,n,m);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
            sum+=c[i][j];
	return sum;
}
//*********************************************************************
int main(int argc, char* argv[])
{
    int **a,**c,**d,n,m,p,j;
    cout<<"请输入图的结点个数："<<endl;
	cin>>n;
    a=creat_blank(n);
	c=creat_blank(n);
	d=creat_blank(n);
	for(int i=0;i<n;i++)                 //数组初始化
		for( j=0;j<n;j++)
			a[i][j]=c[i][j]=d[i][j]=0;

   
	information(a,n);
	while(true)
	{
		cout<<" 0--求两个结点之间长度为m的通路个数 1--求某点长度为m的回路的个数"<<endl;
	    cout<<"      2--求长度为m的通路总数 3--求可达矩阵 4--结束"<<endl;
		cin>>p;
		switch(p){
		case 0: 
			cout<<"请输入通路长度："<<endl;
			cin>>m;
			road(a,c,n,m);
			cout<<"请输入结点序号"<<endl;
			cin>>i>>j;
			cout<<i<<"与"<<j<<"的通路个数为"<<c[i-1][j-1]<<endl<<endl;
			break;
		case 1:
			cout<<"请输入通路长度："<<endl;
			cin>>m;
			road(a,c,n,m);
			cout<<"请输入结点序号"<<endl;
			cin>>i;
			cout<<i<<"与"<<i<<"的通路个数为"<<c[i-1][i-1]<<endl<<endl;
			break;
    	case 2:
           	cout<<"请输入通路长度："<<endl;
			cin>>m;
            cout<<"长度为m的通路总数为"<<sum_loop_number(a,c,n,m)<<endl<<endl;
			break;
		case 3:
            loop_matrix(a,c,d,n);
			display(d,n);
			break;
		case 4:
			exit(0);
		}
	}
	delete a,c,d;
   return 0;
}