[关闭]
@jtahstu 2017-09-15T02:39:07.000000Z 字数 1327 阅读 393

无向图的深度和广度优先遍历 - C++

算法


本文来自《啊哈!算法》第5章第1节 点击下载PDF文件查看

需要解决的问题

一个无向图,怎么从深度和广度来遍历这个图,也就是怎么个走法

需要了解和学习的点

代码

深度优先遍历

  1. /**
  2. * 图的深度优先遍历
  3. * 啊哈算法 P131
  4. * by jtahstu at 2017-09-14
  5. */
  6. #include <iostream>
  7. #include <climits>
  8. using namespace std;
  9. int book[101] = {0}, sum, n, m, e[101][101] = {0};
  10. void dfs(int cur) {
  11. cout << cur << " ";
  12. sum++;
  13. if (sum == n)return;
  14. for (int i = 1; i <= n; i++) { //循环达到回溯的效果
  15. if (book[i] == 0 && e[cur][i] == 1) {
  16. book[i] = 1;
  17. dfs(i);
  18. }
  19. }
  20. return;
  21. }
  22. int main(int argc, const char *argv[]) {
  23. cin >> n >> m; //n个节点,m条边
  24. for (int i = 1; i <= n; i++) //初始化
  25. for (int j = 1; j <= n; j++) {
  26. if (i == j)
  27. e[i][j] = 0;
  28. else
  29. e[i][j] = INT_MAX;
  30. }
  31. int a, b;
  32. for (int k = 1; k <= m; k++) { //矩阵表示
  33. cin >> a >> b;
  34. e[a][b] = 1;
  35. e[b][a] = 1;
  36. }
  37. book[1] = 1;
  38. dfs(1);
  39. return 0;
  40. }
  41. /**
  42. 5 4
  43. 3 2
  44. 3 4
  45. 2 5
  46. 2 1
  47. 5 5
  48. 1 2
  49. 1 3
  50. 1 5
  51. 2 4
  52. 3 5
  53. */

广度优先遍历

  1. /**
  2. * 图的广度优先遍历
  3. * 啊哈算法 P134
  4. * by jtahstu at 2017-09-14
  5. */
  6. #include <iostream>
  7. #include <climits>
  8. using namespace std;
  9. int main() {
  10. int n, m, a, b, cur, book[101] = {0}, e[101][101] = {0};
  11. int que[101], head = 1, tail = 1;
  12. cin >> n >> m; //n个节点,m条边
  13. for (int i = 1; i <= n; i++) //初始化
  14. for (int j = 1; j <= n; j++) {
  15. if (i == j)
  16. e[i][j] = 0;
  17. else
  18. e[i][j] = INT_MAX;
  19. }
  20. for (int i = 1; i <= m; i++) { //图的矩阵表示
  21. cin >> a >> b;
  22. e[a][b] = 1;
  23. e[b][a] = 1;
  24. }
  25. que[1] = 1;
  26. tail++;
  27. book[1] = 1; //走过的标记为1
  28. while (head < tail) {
  29. cur = que[head];
  30. for (int i = 1; i <= n; i++) { //当前顶点往下的所有可能都存到队列中去
  31. if (book[i] == 0 && e[cur][i] == 1) {
  32. que[tail] = i;
  33. tail++;
  34. }
  35. if (tail > n)
  36. break;
  37. }
  38. head++; //表示当前点遍历结束,下个点
  39. }
  40. for (int i = 1; i <= n; i++) {
  41. cout << que[i] << " ";
  42. }
  43. return 0;
  44. }
  45. /**
  46. 5 4
  47. 1 3
  48. 1 5
  49. 3 2
  50. 5 4
  51. */
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注