C語言求解哥尼斯堡七橋問題

• • 哥尼斯堡七橋問題介紹
  • 解題思路
  • C/C++語言代碼

哥尼斯堡七橋問題介紹

哥尼斯堡七橋問題（簡稱“七橋問題”）。17世紀東普魯士有一座哥尼斯堡城（現(xiàn)叫做加里寧格勒，位于波羅的海南岸），城中有一座島，普魯格爾河的兩條支流環(huán)繞其旁，并將整個城市劃分為北區(qū)、東區(qū)、南區(qū)和島區(qū)4個區(qū)域。共有7座橋將4個區(qū)域連接起來，如下圖所示。產(chǎn)生一個有趣的問題：一個人能否在一次步行中將7座橋全部走完然后回到出發(fā)點，且每座橋只允許經(jīng)過一次。

解題思路

抽象數(shù)據(jù)模型，將城區(qū)抽象為頂點，用A,B,C,D表示，橋抽象為邊，7條邊表示7座橋，從而將七橋問題抽象為數(shù)學問題：求經(jīng)過圖中每一條邊且僅一次的回路，又稱為歐拉回路。歐拉回路判定規(guī)則為：
（1）如果沒有一個城區(qū)通奇數(shù)橋，則無論從哪里出發(fā)都能找到歐拉回路。
（2）如果通奇數(shù)橋的城區(qū)多于兩個，則不存在歐拉回路
（3）如果只有兩個城區(qū)通奇數(shù)橋，則不存在歐拉回路，但可以從這兩個城區(qū)之一出發(fā)找到歐拉路徑（不要求回到出發(fā)點）
總結思路：依次計算與每個頂點相關聯(lián)的邊數(shù)，根據(jù)邊數(shù)為奇數(shù)的頂點個數(shù)判定是否存在歐拉回路。

C/C++語言代碼

/*哥尼斯堡七橋問題轉換為歐拉路徑求解*/ #include<iostream> using namespace std; int EulerCircult(int mat[4][4], int n) {int i, j, degree, count = 0; //count記錄通往奇數(shù)橋頂點個數(shù)for(i = 0; i < n; i++) {degree = 0;for(j = 0; j < n; j++) {degree += mat[i][j]; //這里通過累加邊數(shù)得出該頂點統(tǒng)共有多少橋連接}if(degree % 2 != 0) //判斷是否為奇數(shù)橋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<<"個地方通奇數(shù)橋，不存在歐拉回路"<<endl;else cout<<"存在歐拉回路，可以實現(xiàn)"<<endl;system("pause");return 0; }

總結

以上是生活随笔為你收集整理的C语言求解七桥问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。