我一直認(rèn)為用C語言來描述數(shù)據(jù)結(jié)構(gòu)（尤其是這種簡(jiǎn)單的）是一個(gè)非常不錯(cuò)的方式。

C語言在表示數(shù)據(jù)，存取數(shù)據(jù)，表現(xiàn)數(shù)據(jù)結(jié)構(gòu)里都沒有那么多“捷徑”可以走，所以用C語言寫基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)的代碼，是非常方便讀者理解的。

畢竟，C語言極有可能成為一個(gè)程序員的入門語言。

題目描述

小哼和小哈一同坐飛機(jī)去旅游，他們現(xiàn)在位于1號(hào)城市，目標(biāo)是5號(hào)城市，可是1號(hào)城市并沒有到5號(hào)城市的直航。不過小哼已經(jīng)收集了很多航班的信息，現(xiàn)在小哼希望找到一種乘坐方式，使得轉(zhuǎn)機(jī)的次數(shù)最少，如何解決呢?

輸入：

5 7 1 5
1 2
1 3
2 3
2 4
3 4
3 5
4 5

輸出

2

---

題解

這是一個(gè)典型的廣度優(yōu)先查找，查找從A點(diǎn)到B點(diǎn)的最少轉(zhuǎn)機(jī)次數(shù)。

一開始不喜歡DFS，喜歡BFS，覺得遞歸實(shí)在是太復(fù)雜了。做完這題發(fā)現(xiàn)，BFS要理解好那個(gè)存儲(chǔ)狀態(tài)的隊(duì)列也不容易。比如下面代碼的que里面的s，在數(shù)組里每個(gè)s會(huì)是什么樣子的呢？s什么時(shí)候+1呢？+1的時(shí)候是基于什么的呢？這里邏輯就有點(diǎn)繞了。

不過機(jī)智的我還是弄明白了，對(duì)于每次s要+1的時(shí)候，取決于現(xiàn)在的頭指針指向的哪個(gè)點(diǎn)（即本次轉(zhuǎn)機(jī)的出發(fā)機(jī)場(chǎng)是哪里）。

最后，輸出尾指針-1（因?yàn)槲仓羔樏看味家?#43;+以指向下一個(gè)空格子）里的s屬性的值就可以。

具體可以看代碼。

#include<stdio.h>
int a[2000][2000], book[2000];struct note
{int x;//城市編號(hào)int s;//轉(zhuǎn)機(jī)次數(shù)
};
struct note que[2000];int main()
{int i, j, n, m, x, y, start, end;int cur, head, tail;scanf("%d %d %d %d", &n, &m, &start, &end);for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)if (i == j)a[i][j] = 0;elsea[i][j] = 99999999;for (i = 1; i <= m; i++){scanf("%d %d", &x, &y);a[x][y] = 1;a[y][x] = 1;}head = 1;tail = 1;que[tail].x = start;que[tail].s = 0;book[1] = start;tail++;int flag = 0;while (head < tail){//當(dāng)前正在訪問的頂點(diǎn)的編號(hào)cur = que[head].x;// 從1~n進(jìn)行嘗試for (i = 1; i <= n; i++){if (a[cur][i] != 99999999 && book[i] == 0){que[tail].x = i;que[tail].s = que[head].s + 1; //轉(zhuǎn)機(jī)次數(shù)+1，基于的是頭指針下的stail++;book[i] = 1;}//如果tail>n則表示所有頂點(diǎn)都被訪問過if (que[tail].x == n){flag = 1;break;}}if (flag == 1)break;//這里不要忘記，拓展完之后，要將頭指針+1head++;}printf("%d ", que[tail - 1].s);return 0;
}

輸出結(jié)果：

總結(jié)

以上是生活随笔為你收集整理的[C] 图的广度优先搜索——最少转机的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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