zuoye3.cpp

图论课程设计的左右

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

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

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 ** 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 warshall(int **a,int **b,int n)
{
	int i,j,k;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			b[i][j]=a[i][j];
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			if(b[j][i]==1)
				for(k=0;k<n;k++)
					b[j][k]=b[j][k]|b[i][k];
		}

}
//*********************************************************
void display(int **a,int n)
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;
	}
}
//*************************************************************
void link(int **b,int n)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			if(b[i][j]==0) break;
		if(j<n) break;
	}
	if(i==n&&j==n)cout<<"该图为强连通图"<<endl;
	   
}
//*************************************************************
int main(int argc, char* argv[])
{
	int **a,**b;
	int m; 
	cout<<"请输入图的结点个数："<<endl;
    cin>>m;                   //存放结点个数
	a=creat_blank(m);
	b=creat_blank(m);
	for(int i=0;i<m;i++)
		for(int j=0;j<m;j++)
			a[i][j]=b[i][j]=0;

	information(a,m);
	warshall(a,b,m);
	cout<<"可达矩阵为："<<endl;
	display(b,m);
	link(b,m);

	delete a,b;
	return 0;
}