欧拉图的判定

一、实验目的：判定一个图是否是欧拉图
二、实验内容：
1)题目：
.
（1）（2）（3）
各图的邻接矩阵：
V1 V2 V3 V4 V5 V6 V1 0 1 1 0 0 0
V2 1 0 1 1 0 0
V3 1 1 0 1 1 0
V4 0 1 1 0 1 1
V5 0 0 1 1 0 1
V6 0 0 0 1 1 0
V1 V2 V3 V4 V5 V6 V1 0 1 1 0 0 0
V2 1 0 1 2 0 0
V3 1 1 0 1 1 0
V4 0 2 1 0 1 2
V5 0 0 1 1 0 2
V6 0 0 0 2 2 0
V1 V2 V3 V4 V5 V6 V7 V1 0 1 1 0 0 0 0
V2 1 0 1 1 0 0 0
V3 1 1 0 1 1 0 0
V4 0 1 1 0 1 1 0
V5 0 0 1 1 0 1 0 V6 0 0 0 1 1 0 0 V7 0 0 0 0 0 0 0 2)代码：
#include "stdio.h"
#include "math.h"
#define m 6 /*定义结点个数*/
float M=1000000.0; /*用于比较权重选择最优路径*/
float B[m][m]={0},D[m][m]={0},C[m]={0}; /*记录权重*/
int E[m][m]={0}; /*记录两点间的路径是否被选择*/
int X[m]={0},Y[m]={0}; /*记录已选择的点*/
int s=0;
int judge() /*判断是否所有点都已连接*/
{
int k,s=0,t=0,flag1=0;
for(k=0;k<m;k++)
{
if(X[k]==0) {flag1=0;t=k+1;break;}
else flag1=1;
}
if(flag1==0) s=t;
return s;
}
void search() /*选择从所有已连点到未连点中权重最小但大于0的路径*/ {
float M1=0.0;
int i,j,k1=0,k2=0;
M1=M;
for(i=0;i<m;i++)
{
if(X[i]==1)
{
for(j=0;j<m;j++)
{
if(Y[j]==0)
{
if(B[i][j]<M1&&B[i][j]>0)
{M1=B[i][j];k1=i;k2=j;}
}
}
}
}
if(M1==M) s=1;
else
{E[k1][k2]=1; B[k1][k2]=B[k2][k1]=M; X[k2]=1; Y[k2]=1;}
}
void main()
{
int r=0,flag=0,flag1=0;
int i,j;
printf("输入图的邻接矩阵：\n");
for(i=0;i<m;i++)
for(j=0;j<m;j++)
{
scanf("%f",&B[i][j]);
D[i][j]=B[i][j];
}
X[0]=1;Y[0]=1;
while(1)
{
s=0; flag=0;
search();
if(s==1)
{
r=judge();
if(r==0)
{flag=1;break;}
else
{flag=2;break;}
}
}
if(flag==1)
{ printf("该图有最小支撑树，是连通图！");
for(i=0;i<m;i++)
{
for(j=0;j<m;j++)
C[i]=C[i]+D[i][j];
if(fmod(C[i],2)==1) {flag1=1;break;}
}
if(flag1==1) printf("\n该图不是欧拉图!\n");
else printf("\n该图是欧拉图!\n");
}
else printf("\n该图是不连通的，不是欧拉图!\n"); }
3）运行结果：
三、使用环境
适用于解决各种欧拉图的判定问题，在使用时需根据实际情况来更改预定义的m的值。