【离散数学】图的随机生成和欧拉（回）路的确定（c语言实现）

实验

实验内容

编程随机生成含m个结点和n条边的无向简单图并能进行（半）欧拉图的判定，若是则给出欧拉（回）路。

实验要求

实验要求如下：

• 对给定m个结点和n条边，随机生成相关邻接矩阵以确定某无向连通简单图。

• 基于度的计算进行欧拉图和半欧拉图的判定。

• 若符合则给出至少一条欧拉回路或欧拉路

具体实现

具体实现思路可以参考下面：

变量定义

因为如果我们使用局部变量，每一个函数都会使用这些变量，会让函数的参数越变越多。
所以我们将这些变量定义为全局变量，这样就不用在参数中调用了。

#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;//边数

根据边来生成图函数

• 通过调用随机函数给定两个0到m-1的不同值x和y来生成一条边。
• 将生成边与已有边集合比较，不重复则加入边集合（若用邻接矩阵表示图，则验证对应[x[y是否为1）。
• 直至生成n条边。
• 判断是否连通，若否需重新生成。

//随机生成边
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
#include
#include
#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;
}