最少转机--图的广度优先遍历

本文主要是介绍最少转机--图的广度优先遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最少转机–图的广度优先遍历

要求

求城市1到城市5最少转机数？

思路

同样使用图的邻接矩阵存储法存储地图。使用广度优先遍历求解，先将城市1加入队列，然后从队列取出，查找城市1可以到达的城市并依次加入队列，在从队列中取出一个城市继续查找，相当于每次推进了一步，找到城市5，程序结束。一个小技巧，在每个城市记录转机次数， 等于上一个城市次数加1。

代码

#include <stdio.h>#define N 6
#define M 6int a[N][M] = {{ 0,  0,  0,  0,  0,  0},{ 0,  0,  1,  1, -1, -1},     { 0,  1,  0,  1,  1, -1},     { 0,  1,  1,  0,  1,  1},     { 0, -1,  1,  1,  0,  1},   { 0, -1, -1,  1,  1,  0}      };
struct node
{int x;int s;       // 转机次数
};int b[M] = {0};
struct node queue[40];
int head = 0, tail = 0;
int flag = 0;int main() {int cur = 1;queue[tail].x = cur;queue[tail].s = 0;tail++;b[cur] = cur;while(head < tail) {cur = queue[head].x;head++;for (int i = 1; i < M; ++i) {if (a[cur][i] == 1 && b[i] == 0) {queue[tail].x = i;queue[tail].s = queue[head-1].s + 1;tail++;b[i] = 1;if (i == 5) {flag = 1;break;}}}if (flag) {break;}}if (flag) {printf("%d \n", queue[tail-1].s);} else {printf("not found\n");}return 0;
}

这篇关于最少转机--图的广度优先遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---