C语言求解七桥问题

C语言求解哥尼斯堡七桥问题

• • 哥尼斯堡七桥问题介绍
  • 解题思路
  • C/C++语言代码

哥尼斯堡七桥问题介绍

哥尼斯堡七桥问题（简称“七桥问题”）。17世纪东普鲁士有一座哥尼斯堡城（现叫做加里宁格勒，位于波罗的海南岸），城中有一座岛，普鲁格尔河的两条支流环绕其旁，并将整个城市划分为北区、东区、南区和岛区4个区域。共有7座桥将4个区域连接起来，如下图所示。产生一个有趣的问题：一个人能否在一次步行中将7座桥全部走完然后回到出发点，且每座桥只允许经过一次。

解题思路

抽象数据模型，将城区抽象为顶点，用A,B,C,D表示，桥抽象为边，7条边表示7座桥，从而将七桥问题抽象为数学问题：求经过图中每一条边且仅一次的回路，又称为欧拉回路。欧拉回路判定规则为：
（1）如果没有一个城区通奇数桥，则无论从哪里出发都能找到欧拉回路。
（2）如果通奇数桥的城区多于两个，则不存在欧拉回路
（3）如果只有两个城区通奇数桥，则不存在欧拉回路，但可以从这两个城区之一出发找到欧拉路径（不要求回到出发点）
总结思路：依次计算与每个顶点相关联的边数，根据边数为奇数的顶点个数判定是否存在欧拉回路。

C/C++语言代码

/*哥尼斯堡七桥问题转换为欧拉路径求解*/ #include<iostream> using namespace std; int EulerCircult(int mat[4][4], int n) {int i, j, degree, count = 0; //count记录通往奇数桥顶点个数for(i = 0; i < n; i++) {degree = 0;for(j = 0; j < n; j++) {degree += mat[i][j]; //这里通过累加边数得出该顶点统共有多少桥连接}if(degree % 2 != 0) //判断是否为奇数桥count++;}return count; } int main() {int mat[4][4] = {{0, 1, 2, 2}, {1, 0, 1, 1}, {2, 1, 0, 0}, {2, 1, 0, 0}};int num = EulerCircult(mat, 4);if(num >= 2) cout<<"有"<<num<<"个地方通奇数桥，不存在欧拉回路"<<endl;else cout<<"存在欧拉回路，可以实现"<<endl;system("pause");return 0; }

总结

以上是生活随笔为你收集整理的C语言求解七桥问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。