实验要求
变量定义
因为如果我们使用局部变量，每一个函数都会使用这些变量，会让函数的参数越变越多。所以我们定义全局变量，这样就不用在参数中调用了。
#define MAX 100
int arrMap[MAX][MAX] = { 0 };//图的矩阵
int degree[MAX] = { 0 };//节点的度
int visit[MAX] = { 0 };//记录是否被访问
int euler[MAX] = { -1 };
int ans[MAX]; //欧拉路
int c[MAX][MAX]; //判断该边是否已经走过
int m = 0;//结点个数
int n = 0;//边数
根据边来生成图函数
//随机生成边
void creatSide()
{
int count = 0;
while (count < n)
{
int x = rand() % m;
int y = rand() % m;
while (x == y)
x = rand() % m;
if (!arrMap[x][y])
{
arrMap[x][y] = arrMap[y][x] = 1;
count++;
degree[x]++;
degree[y]++;
}
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < m; j++)
{
printf("%d ", arrMap[i][j]);
}
printf("\n");
}
}
判断联通函数
DFS通过递归的方式，从给定的起始顶点开始，沿着一条路径一直走到底，然后回退到上一个节点，再选择另一条路径继续走下去。当所有路径都被探索完毕时，如果所有的节点都被访问到，则图是连通的
//深度优先搜索判断是否为连通图
void DFS(int x)
{
visit[x] = 1;
for (int i = 0; i < m; i++)
{
if (!visit[i] && arrMap[x][i])
{
DFS(i);
}
}
}
//判断联通是返回1不是返回0
int judgeConnect()
{
DFS(0);
for (int i = 0; i < m; i++)
{
if (!visit[i])
{
return 0;
}
}
return 1;
}
判断是否有欧拉路
有0个或2个奇数度结点的有欧拉路。
//判断是否是（半）欧拉图
void judgeEuler()
{
int first = 0;
int num = 0;//奇数结点个数
for (int i = 0; i < m; i++)
{
if (degree[i] % 2 != 0)
{
first = i;
num++;
}
}
if (num == 1 || num > 2)
{
printf("不是欧拉图或半欧拉图\n");
}
else
{
euler[0]= first;
trav(first, 1);
if (num == 0)
{
printf("随机生成的图是欧拉图\n");
printf("该欧拉图的一条欧拉路是\n");
}
else
{
printf("随机生成的图是半欧拉图\n");
printf("该半欧拉图的一条欧拉路是\n");
}
for (int i = 0; i < n; i++)
{
printf("%d->", ans[i]);
}
printf("%d\n", ans[n]);
}
}
生成欧拉路
如果图满足所有顶点的度数都是偶数，可以从任意顶点开始，任意顺序遍历边，直到回到起始顶点，这样就能生成一条欧拉路。
如果图中仅有两个顶点的度数为奇数，首先找到这两个奇数度顶点，然后从其中一个奇数度顶点开始，遍历所有边直到另一个奇数度顶点，这样也能生成一条欧拉路。
//找欧拉路
void trav(int p, int q)
{
int flag = 1;
if (euler[n] != -1)
{
if(flag == 1)
{
for (int i = 0; i <= n; i++)
{
ans[i] = euler[i];
}
flag = 0;
}
}
for (int i = 0; i < m; i++)
{
if (arrMap[p][i] && !c[p][i])
{
euler[q] = i;
c[p][i] = c[i][p] = 1;
trav(i, q + 1);
if (!flag)return;
else c[p][i] = c[i][p] = 0;
}
}
}
源码
# define _CRT_SECURE_NO_WARNINGS 1；
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define MAX 100
int arrMap[MAX][MAX] = { 0 };//图的矩阵
int degree[MAX] = { 0 };//节点的度
int visit[MAX] = { 0 };//记录是否被访问
int euler[MAX] = { -1 };
int ans[MAX]; //欧拉路
int c[MAX][MAX]; //判断该边是否已经走过
int m = 0;//结点个数
int n = 0;//边数
//随机生成边
void creatSide()
{
int count = 0;
while (count < n)
{
int x = rand() % m;
int y = rand() % m;
while (x == y)
x = rand() % m;
if (!arrMap[x][y])
{
arrMap[x][y] = arrMap[y][x] = 1;
count++;
degree[x]++;
degree[y]++;
}
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < m; j++)
{
printf("%d ", arrMap[i][j]);
}
printf("\n");
}
}
//深度优先搜索判断是否为连通图
void DFS(int x)
{
visit[x] = 1;
for (int i = 0; i < m; i++)
{
if (!visit[i] && arrMap[x][i])
{
DFS(i);
}
}
}
//判断联通是返回1不是返回0
int judgeConnect()
{
DFS(0);
for (int i = 0; i < m; i++)
{
if (!visit[i])
{
return 0;
}
}
return 1;
}
//找欧拉路
void trav(int p, int q)
{
int flag = 1;
if (euler[n] != -1)
{
if(flag == 1)
{
for (int i = 0; i <= n; i++)
{
ans[i] = euler[i];
}
flag = 0;
}
}
for (int i = 0; i < m; i++)
{
if (arrMap[p][i] && !c[p][i])
{
euler[q] = i;
c[p][i] = c[i][p] = 1;
trav(i, q + 1);
if (!flag)return;
else c[p][i] = c[i][p] = 0;
}
}
}
//判断是否是（半）欧拉图
void judgeEuler()
{
int first = 0;
int num = 0;//奇数结点个数
for (int i = 0; i < m; i++)
{
if (degree[i] % 2 != 0)
{
first = i;
num++;
}
}
if (num == 1 || num > 2)
{
printf("不是欧拉图或半欧拉图\n");
}
else
{
euler[0]= first;
trav(first, 1);
if (num == 0)
{
printf("随机生成的图是欧拉图\n");
printf("该欧拉图的一条欧拉路是\n");
}
else
{
printf("随机生成的图是半欧拉图\n");
printf("该半欧拉图的一条欧拉路是\n");
}
for (int i = 0; i < n; i++)
{
printf("%d->", ans[i]);
}
printf("%d\n", ans[n]);
}
}
int main()
{
srand((unsigned int)time(NULL));
printf("请输入结点个数：");
scanf("%d", &m);
printf("请输入边数，需小于等于%d：", m * (m - 1) / 2);
scanf("%d", &n);
back:
creatSide();
int ret = judgeConnect();
if (ret == 0)
{
printf("该图不是连通图,结点度为\n");
for (int i = 0; i < m; i++)
{
printf("%d ", degree[i]);
}
printf("\n");
goto back;
}
else
{
judgeEuler();
}
return 0;
}
