我一直認為用C語言來描述數據結構（尤其是這種簡單的）是一個非常不錯的方式。

C語言在表示數據，存取數據，表現數據結構里都沒有那么多“捷徑”可以走，所以用C語言寫基礎的數據結構的代碼，是非常方便讀者理解的。

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

題目描述

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

輸入：

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

輸出

2

---

題解

這是一個典型的廣度優先查找，查找從A點到B點的最少轉機次數。

一開始不喜歡DFS，喜歡BFS，覺得遞歸實在是太復雜了。做完這題發現，BFS要理解好那個存儲狀態的隊列也不容易。比如下面代碼的que里面的s，在數組里每個s會是什么樣子的呢？s什么時候+1呢？+1的時候是基于什么的呢？這里邏輯就有點繞了。

不過機智的我還是弄明白了，對于每次s要+1的時候，取決于現在的頭指針指向的哪個點（即本次轉機的出發機場是哪里）。

最后，輸出尾指針-1（因為尾指針每次都要++以指向下一個空格子）里的s屬性的值就可以。

具體可以看代碼。

#include<stdio.h>
int a[2000][2000], book[2000];struct note
{int x;//城市編號int s;//轉機次數
};
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){//當前正在訪問的頂點的編號cur = que[head].x;// 從1~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; //轉機次數+1，基于的是頭指針下的stail++;book[i] = 1;}//如果tail>n則表示所有頂點都被訪問過if (que[tail].x == n){flag = 1;break;}}if (flag == 1)break;//這里不要忘記，拓展完之后，要將頭指針+1head++;}printf("%d ", que[tail - 1].s);return 0;
}

輸出結果：

總結

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

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