图论实验

//输入一个图的邻接矩阵，自动算出每个点的度数，判断它是否满足握手定理，是否可以构成
//欧拉图，是否满足哈密尔顿图的充分条件。
#include<cmath>
#include<iostream>
using namespace std;

int main(){
loop:cout<<"此程序适用于无向图！"<<endl<<endl; 
    int row;
        cout<<"请输入该图的点数："<<endl;
        cin>>row;
        int AdjMat[row][row];//定义一个邻接矩阵，行列从键盘获得 
        cout<<"请输入矩阵"<<endl;
        for(int i=0;i<row;i++)
                for(int j=0;j<row;j++)
                        cin>>AdjMat[i][j];

        int tmp=0;
        for(int i=0;i<row;i++)
                for(int j=0;j<row;j++){
                    if(AdjMat[i][j]!=AdjMat[j][i]||AdjMat[i][i]==1) 
                    tmp++;
                        }
         if(tmp>0){
         cout<<"ERROR!"<<endl<<"此程序应用于无向图！"<<endl;
         goto loop;
         }
                 
     
     
     int deg[row];//定义邻接矩阵的度数 
     int i=0;
     while(i<row){
                   deg[i]=0;
                   for(int j=0;j<row;j++){
                           if(AdjMat[i][j]==1)
                           deg[i]++;
                           }
                   i++;
                   }
     
     
     
     
     int k=1;
    
     cout<<endl<<"点\t度数 "<<endl;//打印度数 
      for(int i=0;i<row;i++)
      cout<<k++<<'\t'<<deg[i]<<endl; 
      
      //求总度数
      int sumDeg=0;
      for(int i=0;i<row;i++)
      sumDeg+=deg[i]; 
      cout<<endl<<"该图各点的总度数为："<<sumDeg<<endl; 
      
      
      
      //判断是否满足握手定理
      int side=0;//定义图的边数，遍历数组求边数
      for(int i=0;i<row;i++)
      for(int j=0;j<row;j++){
              if(AdjMat[i][j]==1)
              side++; 
              }
      side=side/2;  
      cout<<endl<<"该图的边数为："<<side<<endl;
      if(sumDeg==2*side)
      cout<<endl<<"该图满足握手定理"<<endl;
      else
      cout<<endl<<"该图不满足握手定理"<<endl; 
      
      
      
      
      //判断是否构成欧拉图
       int tmp1=0;
       for(int i=0;i<row;i++){
               if(deg[i]%2==0)
               tmp1++;
               }
       if(tmp1==row)
       cout<<endl<<"该图构成欧拉图"<<endl; 
       else
       cout<<endl<<"该图不构成欧拉图"<<endl;
       
       
       
       //判断是否满足哈密尔顿图的充分条件
       int tmp2;
       for(int i=0;i<row;i++){
               if(deg[i]>deg[i++]){
                                   tmp2=deg[i];
                                   deg[i]=deg[i++];
                                   deg[i++]=tmp2;
                                   }
               }
       cout<<endl<<"度数最小的两点的度数和为："<<(deg[0]+deg[1])<<endl;
       cout<<endl<<"该图共有 "<<row<<" 个点"<<endl; 
       if((deg[0]+deg[1])>=row)
       cout<<endl<<(deg[0]+deg[1])<<">="<<row<<"满足哈密尔顿图的充分条件" <<endl;
       else
       cout<<endl<<(deg[0]+deg[1])<<"<"<<row<<"不满足哈密尔顿图的充分条件" <<endl;
       cout<<endl; 
   
               system("pause");
            return 0;
}