您好,登錄后才能下訂單哦!
C語言數(shù)據(jù)結(jié)構(gòu)與算法中怎樣完成圖的遍歷,針對(duì)這個(gè)問題,這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答,希望可以幫助更多想解決這個(gè)問題的小伙伴找到更簡(jiǎn)單易行的方法。
我們選擇使用廣度優(yōu)先搜索來完成這個(gè)圖的遍歷 --> 結(jié)果如下:
使用廣度優(yōu)先搜索來遍歷這個(gè)圖的過程如下。
首先以一個(gè)未被訪問過的頂點(diǎn)作為起始頂點(diǎn),比如以1號(hào)點(diǎn)作為起始頂點(diǎn)。
將1號(hào)點(diǎn)放到隊(duì)列中,然后將與1號(hào)點(diǎn)相鄰的未訪問過的頂點(diǎn) 即 2,3,5號(hào)頂點(diǎn)依次放入隊(duì)列中,如下圖:
接下來將2號(hào)頂點(diǎn)相鄰的未訪問過的頂點(diǎn)4號(hào)放入到隊(duì)列中。到此所有的頂點(diǎn)都訪問過了,遍歷結(jié)束。如下圖:
首先以一個(gè)未被訪問過的頂點(diǎn)作為起始頂點(diǎn),訪問其所有相鄰的點(diǎn)
然后對(duì)每個(gè)相鄰的的點(diǎn),再訪問他們相鄰的未被訪問過的頂點(diǎn),直到所有的頂點(diǎn)都被訪問過,遍歷結(jié)束。
#include <stdio.h> int main() { int i, j, m, a, b, cur,n, book[101] = { 0 }, e[101][101]; int que[10001], head, tail; scanf("%d %d", &n, &m); //初始化二維矩陣 for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) if (i == j) e[i][j] = 0; else e[i][j] = 99999999; //我們假設(shè)99999999為x //讀入頂點(diǎn)之間的邊 for (i = 1; i <= n; i++) { scanf("%d %d", &a, &b); e[a][b] = 1; e[b][a] = 1; //因?yàn)樵搱D為無向圖 } //隊(duì)列初始化 head = 1; tail = 1; //從1號(hào)頂點(diǎn)出發(fā),將1號(hào)頂點(diǎn)加入隊(duì)列 que[tail] = 1; tail++; book[1] = 1;//標(biāo)記1號(hào)頂點(diǎn)已經(jīng)入列 //當(dāng)隊(duì)列不為空時(shí)循環(huán) while (head < tail && tail <= n) { cur = que[head]; //當(dāng)前正在訪問的頂點(diǎn)編號(hào) for (i = 1; i <= n; i++) { //判斷從頂點(diǎn)cur到頂點(diǎn)i是否有邊,并判斷頂點(diǎn)i是否訪問過 if (e[cur][i] == 1 && book[i] == 0) { //如果從頂點(diǎn)cur到頂點(diǎn)i右邊,且頂點(diǎn)i沒有被訪問過,將頂點(diǎn)i入列 que[tail] = i; tail++; book[i] = 1; //標(biāo)記表示已經(jīng)訪問過 } if (tail > n) //表示所有點(diǎn)都已經(jīng)訪問過 break; } head++; //注意這個(gè)地方,不要忘記head++后,才能繼續(xù)向下拓展 } for (i = 1; i < tail; i++) printf("%d",que[i]); }
關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)與算法中怎樣完成圖的遍歷問題的解答就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,如果你還有很多疑惑沒有解開,可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。