首页 > 代码库 > 第五章 图的遍历（深度遍历，广度遍历，城市地图，最少转机）
第五章 图的遍历（深度遍历，广度遍历，城市地图，最少转机）
深度和广度优先搜索：
单词分解：首先是搜索
深度和广度：是针对图的遍历而言的
图：由顶点和边组成
图的遍历：把图中每一个顶点都访问一次
一：
输入：
5 5（顶点数，边数）
1 2
1 3
1 5
2 4
3 5
输出：
1 2 4 3 5
（按时间戳输出）深度遍历
1 2 3 5 4
（按时间戳输出）广度遍历
1 #include <stdio.h> 2 int map[10][10], book[10], n, m,sum; 3 void dfs(int cur) 4 { 5 int i; 6 printf("%d ",cur); 7 sum++; 8 if (sum == n) 9 return; 10 for (i = 1;i <= n;i++) 11 { 12 if (book[i] == 0 && map[i][cur]) 13 { 14 book[i] = 1; 15 dfs(i); 16 } 17 } 18 return; 19 } 20 void bfs(int front) 21 { 22 int que[100]; 23 int head = 0, tail = 0; 24 int i; 25 que[tail++] = front; 26 book[front] = 1; 27 while (head < tail) 28 { 29 for (i = 1;i <= n;i++) 30 { 31 if (map[que[head]][i] && book[i]==0) 32 { 33 book[i] = 1; 34 que[tail++] = i; 35 } 36 } 37 head++; 38 } 39 for (i = 0;i < tail;i++) 40 printf("%d ",que[i]); 41 printf("\n"); 42 } 43 int main() 44 { 45 int x, y,i; 46 scanf("%d%d",&n,&m); 47 for (i = 1;i <= m;i++) 48 { 49 scanf("%d%d",&x,&y); 50 map[x][y] = 1; 51 map[y][x] = 1; 52 } 53 /*book[1] = 1; 54 dfs(1); 55 printf("\n");*/ 56 bfs(1); 57 return 0; 58 }
二：城市地图
输入（5个顶点，8条边）：
5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3
输出：
9
（从城市1到城市5的最短距离）
1 #include <stdio.h> 2 int map[10][10], book[10], n; 3 int min = 99999; 4 void dfs(int cur,int sum) 5 { 6 int i; 7 if (min < sum) 8 return; 9 if (cur == n) 10 { 11 if (min > sum) 12 min = sum; 13 return; 14 } 15 for (i = 1;i <= n;i++) 16 { 17 if (book[i] == 0 && map[i][cur]) 18 { 19 book[i] = 1; 20 dfs(i, sum + map[i][cur]); 21 book[i] = 0; 22 } 23 } 24 return; 25 } 26 int main() 27 { 28 int e,i,x,y,t; 29 scanf("%d%d",&n,&e); 30 for (i = 1;i <= n;i++) 31 { 32 scanf("%d%d%d", &x, &y, &t); 33 map[x][y] = t; 34 map[y][x] = t; 35 } 36 book[1] = 1; 37 dfs(1,0); 38 printf("%d\n",min); 39 40 return 0; 41 }
三：最少转机（图的广度优先遍历）
第五章 图的遍历（深度遍历，广度遍历，城市地图，最少转机）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。