devbox
2023面试高手
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

BFS - C语言链表实现（简单易懂）_bfs c语言实现

作者：2023面试高手 | 2024-04-18 10:06:31

赞

踩

bfs c语言实现

目录

1. BFS原理

1.1 BFS介绍

1.2 BFS如何实现？

1.3 BFS处理逻辑 可视化

2. C代码实现

2.1 队列（链表）

2.2 前期准备

2.3 BFS函数代码

2.4 主函数输出

2.5 BFS总代码

2.6 运行结果演示

3. 进阶：如何标记路径？

3.1 思路

3.2 最短路径标记的实现

3.3 BFS路径标记总代码

3.4 运行结果演示

4. 总结

1. BFS原理

1.1 BFS介绍

        BFS(广度优先探索)，与 DFS(深度优先探索) 相对应。形象地说，是一种从起点开始不断向外扩散搜索的一种搜索算法。

        如图，黑色色块代表起点，灰色代表未搜索色块，灰白色代表已搜索色块，蓝色代表当前本轮搜索到的色块，绿色代表下一轮将搜索的色块，红色代表终点。

1.2 BFS如何实现？

        （形象化描述）该算法中，首先需要一个 标记遍历的数组 ，记录已搜索过的地方。其次，对于本轮与下一轮的顺序处理，需要使用 队列 进行依次处理，这样保证了只有待上一轮处理完才会轮到下一轮处理。

        对于本轮搜索的每一个元素，会将其从队首弹出并判断是否为终点，然后将符合搜索条件的下一轮元素从队尾入队，如果无符合搜索条件的下一轮元素，则无新的元素入队。若到搜索完毕都没发现终点，则不再有新的元素入队，最后一轮元素不断退队直至队列为空；若搜索到终点，则不再搜索， 队伍剩余元素不断退队直至队列为空。

        总而言之，BFS是 顺序处理 上一轮与这一轮的元素，直至搜索到终点或再无符合搜索条件元素入队。

1.3 BFS处理逻辑 可视化

        如今有一搜索范围，确定起点与终点。

初始化：初始化标记遍历都为 0；生成队列，将起点入队，标记为 1。

搜索条件：标记遍历不为 1，地图不为墙。

循环操作：（循环终止条件：队列为空）

        (1) 将队首（此时为起点）弹出，并判断是否为终点（否，继续搜索）。

        (2) 向四周查找符合搜索条件的元素，将这些元素逐个入队，标记为1。同时判断是否为终点（否，继续搜索）。

    进入 下一个循环 ：

        (1) 将队首（此时为起点上方的元素）弹出，并判断是否为终点（否，继续搜索）。

        (2) 向四周查找符合搜索条件的元素，将这些元素逐个入队，标记为1。判断是否为终点（否，继续搜索）。

    ......处理至下一轮并 继续循环 ：

 

边界处：只将符合搜索条件的元素入队即可。

搜索到终点：停止继续搜索，不再有新元素入队，队列中剩余元素直接逐个出队直至空。

灰色为已出队元素，深蓝色为当前即将出队元素

结束后：

2. C代码实现

2.1 队列（链表）

固定头节点  head 

  1. typedef struct node
  2. {
  3.     // 坐标记录
  4.     int x;
  5.     int y;
  6.     // 第n轮搜索
  7.     int step;
  8.     // 链表链接
  9.     struct node *next;
  10. } node;
  11.  
  12. // 头节点
  13. node *head;

入队

  1. void push(node *newNode)
  2. {
  3.     node *p = head;
  4.      // 遍历至队尾
  5.     while (p->next != NULL)
  6.     {
  7.         p = p->next;
  8.     }
  9.     // 链接
  10.     p->next = newNode;
  11. }

出队

  1. void pop()
  2. {
  3.     // 删除头节点下一节点
  4.     node *temp = head->next;
  5.     head->next = temp->next;
  6.     free(temp);
  7. }

2.2 前期准备

Map & Sign

  1. #define ROW 8
  2. #define COL 8
  3. // ROW * COL Map
  4. // 0为路径，1为墙，2为终点
  5. int map[ROW + 2][COL + 2] = {
  6.     {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
  7.     {1, 0, 0, 0, 0, 0, 0, 0, 1, 1},
  8.     {1, 1, 1, 1, 0, 1, 1, 1, 1, 1},
  9.     {1, 0, 0, 1, 0, 0, 1, 0, 1, 1},
  10.     {1, 0, 1, 0, 0, 1, 1, 0, 1, 1},
  11.     {1, 0, 1, 0, 1, 1, 1, 0, 1, 1},
  12.     {1, 0, 1, 0, 0, 0, 0, 0, 1, 1},
  13.     {1, 0, 0, 0, 1, 1, 1, 0, 1, 1},
  14.     {1, 1, 1, 1, 1, 1, 1, 0, 2, 1},
  15.     {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
  16. };
  17. int sign[ROW + 2][COL + 2] = {};

方向

  1. // += direction[i].x
  2. // += direction[i].y
  3. struct
  4. {
  5.     int x;
  6.     int y;
  7. } direction[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

2.3 BFS函数代码

  1. // 以 x, y 坐标为起点
  2. int bfs(int x, int y)
  3. {
  4.     // 记录最小步数
  5.     int MinStep = 0;
  6.     // 记录是否已抵达终点
  7.     int flag = 0;
  8.  
  9.     // 初始化头节点        
  10.     head = (node *)malloc(sizeof(node));
  11.     head->next = NULL;
  12.  
  13.     // 起点节点入队
  14.     node *start = (node *)malloc(sizeof(node));
  15.     start->x = x;
  16.     start->y = y;
  17.     start->step = 0;
  18.     start->next = NULL;
  19.  
  20.     push(start);
  21.  
  22.     // 标记遍历为 1
  23.     sign[x][y] = 1;
  24.     // 在地图上标记起点为 5
  25.     map[x][y] = 5;
  26.  
  27.     do
  28.     {
  29.         // 提取队首（注意此时还未出队）
  30.         node *prevNode = head->next;
  31. 		
  32.         // 如果当前已找到终点，队首直接出队，不再继续搜索
  33.         if (flag)
  34.         {
  35.             pop();
  36.             continue;
  37.         }
  38.  
  39.         // 未找到，继续搜索
  40.         int i;
  41.         for (i = 0; i < 4; ++i)
  42.         {
  43.             // 对四个方向进行搜索判断
  44.             // 新建节点存储待判断元素信息
  45.             node *newNode = (node *)malloc(sizeof(node));
  46.             newNode->x = prevNode->x + direction[i].x;
  47.             newNode->y = prevNode->y + direction[i].y;
  48.             newNode->step = prevNode->step + 1;
  49.             newNode->next = NULL;
  50.  
  51.             // 若找到终点，标记后不再搜索
  52.             if (map[newNode->x][newNode->y] == 2)
  53.             {
  54.                 flag = 1;
  55.                 // 地图上标记为 3
  56.                 map[newNode->x][newNode->y] = 3;
  57.                 // 记录最小步数
  58.                 MinStep = newNode->step;
  59.                 free(newNode);
  60.                 break;
  61.             }
  62.  
  63.             // 若符合搜索条件，入队并标记
  64.             else if (sign[newNode->x][newNode->y] == 0 && map[newNode->x][newNode->y] == 0)
  65.             {
  66.                 // 入队
  67.                 push(newNode);
  68.                 // 标记遍历为 1
  69.                 sign[newNode->x][newNode->y] = 1;
  70.                 // 地图上标记为 3
  71.                 map[newNode->x][newNode->y] = 3;
  72.             }
  73.             // 不符合搜索条件
  74.             else
  75.                 free(newNode);
  76.         }
  77.         // 此处的下一级元素全部入队后，队首出队
  78.         pop();
  79.     } while (head->next != NULL);
  80.  
  81.     return MinStep;
  82. }

2.4 主函数输出

  1. int main()
  2. {
  3.     // 输出初始Map状态
  4.     int i, j;
  5.     for (i = 1; i <= ROW; ++i)
  6.     {
  7.         for (j = 1; j <= COL; ++j)
  8.         {
  9.             printf("%d ", map[i][j]);
  10.         }
  11.         putchar(10);
  12.     }
  13.     putchar(10);
  14.  
  15.     // BFS 从 1,1 开始
  16.     int MinStep = bfs(1, 1);
  17.  
  18.     // 输出最小步数
  19.     if (MinStep)
  20.         printf("MinStep = %d\n", MinStep);
  21.     else
  22.         printf("Not Found!");
  23.  
  24.     for (i = 1; i <= ROW; ++i)
  25.     {
  26.         for (j = 1; j <= COL; ++j)
  27.         {
  28.             printf("%d ", map[i][j]);
  29.         }
  30.         putchar(10);
  31.     }
  32.  
  33.     // 小心内存泄漏
  34.     free(head);
  35.     return 0;
  36. }

2.5 BFS总代码

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define ROW 8
  5. #define COL 8
  6.  
  7. typedef struct node
  8. {
  9.     int x;
  10.     int y;
  11.     int step;
  12.     struct node *next;
  13. } node;
  14. node *head;
  15.  
  16. struct
  17. {
  18.     int x;
  19.     int y;
  20. } direction[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  21.  
  22. int map[ROW + 2][COL + 2] = {
  23.     {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
  24.     {1, 0, 0, 0, 0, 0, 0, 0, 1, 1},
  25.     {1, 1, 1, 1, 0, 1, 1, 1, 1, 1},
  26.     {1, 0, 0, 1, 0, 0, 1, 0, 1, 1},
  27.     {1, 0, 1, 0, 0, 1, 1, 0, 1, 1},
  28.     {1, 0, 1, 0, 1, 1, 1, 0, 1, 1},
  29.     {1, 0, 1, 0, 0, 0, 0, 0, 1, 1},
  30.     {1, 0, 0, 0, 1, 1, 1, 0, 1, 1},
  31.     {1, 1, 1, 1, 1, 1, 1, 0, 2, 1},
  32.     {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
  33. };
  34. int sign[ROW + 2][COL + 2] = {};
  35.  
  36. void push(node *newNode)
  37. {
  38.     node *p = head;
  39.     while (p->next != NULL)
  40.     {
  41.         p = p->next;
  42.     }
  43.     p->next = newNode;
  44. }
  45.  
  46. void pop()
  47. {
  48.     node *temp = head->next;
  49.     head->next = temp->next;
  50.     free(temp);
  51. }
  52.  
  53. int bfs(int x, int y)
  54. {
  55.     int MinStep = 0;
  56.     int flag = 0;
  57.      
  58.     head = (node *)malloc(sizeof(node));
  59.     head->next = NULL;
  60.  
  61.     node *start = (node *)malloc(sizeof(node));
  62.     start->x = x;
  63.     start->y = y;
  64.     start->step = 0;
  65.     start->next = NULL;
  66.  
  67.     push(start);
  68.  
  69.     sign[x][y] = 1;
  70.     map[x][y] = 5;
  71.  
  72.     do
  73.     {
  74.         node *prevNode = head->next;
  75. 		
  76.         if (flag)
  77.         {
  78.             pop();
  79.             continue;
  80.         }
  81.  
  82.         int i;
  83.         for (i = 0; i < 4; ++i)
  84.         {
  85.             node *newNode = (node *)malloc(sizeof(node));
  86.             newNode->x = prevNode->x + direction[i].x;
  87.             newNode->y = prevNode->y + direction[i].y;
  88.             newNode->step = prevNode->step + 1;
  89.             newNode->next = NULL;
  90.  
  91.             if (map[newNode->x][newNode->y] == 2)
  92.             {
  93.                 flag = 1;
  94.                 map[newNode->x][newNode->y] = 3;
  95.                 MinStep = newNode->step;
  96.                 free(newNode);
  97.                 break;
  98.             }
  99.  
  100.             else if (sign[newNode->x][newNode->y] == 0 && map[newNode->x][newNode->y] == 0)
  101.             {
  102.                 push(newNode);
  103.                 sign[newNode->x][newNode->y] = 1;
  104.                 map[newNode->x][newNode->y] = 3;
  105.             }
  106.             else
  107.                 free(newNode);
  108.         }
  109.         pop();
  110.     } while (head->next != NULL);
  111.     return MinStep;
  112. }
  113.  
  114. int main()
  115. {
  116.     int i, j;
  117.     for (i = 1; i <= ROW; ++i)
  118. 	{
  119.         for (j = 1; j <= COL; ++j)
  120.         {
  121.             printf("%d ", map[i][j]);
  122.         }
  123.         putchar(10);
  124.     }
  125.     putchar(10);
  126.  
  127.     int MinStep = bfs(1, 1);
  128.  
  129.     if(MinStep)
  130.         printf("Min step = %d\n", MinStep);
  131.     else
  132.         printf("Not Found!");
  133.  
  134.     for (i = 1; i <= ROW; ++i)
  135.     {
  136.         for (j = 1; j <= COL; ++j)
  137.         {
  138.             printf("%d ", map[i][j]);
  139.         }
  140.         putchar(10);
  141.     }
  142. 	
  143.     free(head);
  144.     return 0;
  145. }

2.6 运行结果演示

3. 进阶：如何标记路径？

3.1 思路

        首先，要求记录每一子节点的父节点。

        于是，应在结构体中增加父节点指针。

  1. typedef struct node
  2. {
  3.     struct node *prev;    // 父节点
  4.     int x;
  5.     int y;
  6.     int step;
  7.     struct node *next;
  8. } node;

        其次，所有入队节点应保留用于回溯查询。

        于是，不能弹出队首，应将指针指向下一节点。

        最后，要记得 free 防止内存泄漏哦！

  1. void quit()
  2. {
  3.     while (head->next != NULL)
  4.     {
  5.         node *temp = head->next;
  6.         head->next = temp->next;
  7.         free(temp);
  8.     }
  9.     free(head);
  10.     head = NULL;
  11. }

3.2 最短路径标记的实现

        从终点开始不断向前找父节点直至  NULL 。

  1. void route()
  2. {
  3.     node *p = head;
  4.     // 遍历到队尾（终点节点）
  5.     while (p->next != NULL)
  6.     {
  7.         p = p->next;
  8.     }
  9.     // 从终点节点的上一节点开始向前寻找路径（父节点）
  10.     p = p->prev;
  11.     while (p->prev != NULL)
  12.     {
  13.         // 在地图上标记为 4
  14.         map[p->x][p->y] = 4;
  15.         // 向前到父节点
  16.         p = p->prev;
  17.     }
  18. }

3.3 BFS路径标记总代码

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define ROW 8
  5. #define COL 8
  6. // 高亮显示
  7. #define Green "\033[1;32m"
  8. // 清除高亮
  9. #define None "\033[m"
  10.  
  11. typedef struct node
  12. {
  13.     struct node *prev;
  14.     int x;
  15.     int y;
  16.     int step;
  17.     struct node *next;
  18. } node;
  19. node *head;
  20.  
  21. struct
  22. {
  23.     int x;
  24.     int y;
  25. } direction[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  26.  
  27. int map[ROW + 2][COL + 2] = {
  28.     {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
  29.     {1, 0, 0, 0, 0, 0, 0, 0, 1, 1},
  30.     {1, 1, 1, 1, 0, 1, 1, 1, 1, 1},
  31.     {1, 0, 0, 1, 0, 0, 1, 0, 1, 1},
  32.     {1, 0, 1, 0, 0, 1, 1, 0, 1, 1},
  33.     {1, 0, 1, 0, 1, 1, 1, 0, 1, 1},
  34.     {1, 0, 1, 0, 0, 0, 0, 0, 1, 1},
  35.     {1, 0, 0, 0, 1, 1, 1, 0, 1, 1},
  36.     {1, 1, 1, 1, 1, 1, 1, 0, 2, 1},
  37.     {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
  38. };
  39. int sign[ROW + 2][COL + 2] = {};
  40.  
  41. void push(node *newNode)
  42. {
  43.     node *p = head;
  44.     while (p->next != NULL)
  45.     {
  46.         p = p->next;
  47.     }
  48.     p->next = newNode;
  49. }
  50.  
  51. void quit()
  52. {
  53.     while (head->next != NULL)
  54.     {
  55.         node *temp = head->next;
  56.         head->next = temp->next;
  57.         free(temp);
  58.     }
  59.     free(head);
  60.     head = NULL;
  61. }
  62.  
  63. void route()
  64. {
  65.     node *p = head;
  66.     while (p->next != NULL)
  67.     {
  68.         p = p->next;
  69.     }
  70.     p = p->prev;
  71.     while (p->prev != NULL)
  72.     {
  73.         map[p->x][p->y] = 4;
  74.         p = p->prev;
  75.     }
  76. }
  77.  
  78. int bfs(int x, int y)
  79. {
  80.     int flag = 0;
  81.  
  82.     head = (node *)malloc(sizeof(node));
  83.     head->next = NULL;
  84.  
  85.     node *start = (node *)malloc(sizeof(node));
  86.     // 初始化 start 节点的父节点为 NULL 用于终止路径标记
  87.     start->prev = NULL;
  88.     start->x = x;
  89.     start->y = y;
  90.     start->step = 0;
  91.     start->next = NULL;
  92.  
  93.     push(start);
  94.     sign[x][y] = 1;
  95.     map[x][y] = 5;
  96.  
  97.     node *prevNode = head;
  98.     do
  99.     {
  100.         // 指向下一节点
  101.         prevNode = prevNode->next;
  102.         if (flag)
  103.             continue;
  104.  
  105.         int i;
  106.         for (i = 0; i < 4; ++i)
  107.         {
  108.             node *newNode = (node *)malloc(sizeof(node));
  109.             // 记录父节点
  110.             newNode->prev = prevNode;
  111.             newNode->x = prevNode->x + direction[i].x;
  112.             newNode->y = prevNode->y + direction[i].y;
  113.             newNode->step = prevNode->step + 1;
  114.             newNode->next = NULL;
  115.             if (map[newNode->x][newNode->y] == 2)
  116.             {
  117.                 flag = 1;
  118.                 // 终点节点入队
  119.                 push(newNode);
  120.                 break;
  121.             }
  122.             else if (sign[newNode->x][newNode->y] == 0 && map[newNode->x][newNode->y] == 0)
  123.             {
  124.                 push(newNode);
  125.                 sign[newNode->x][newNode->y] = 1;
  126.                 map[newNode->x][newNode->y] = 3;
  127.             }
  128.             else
  129.                 free(newNode);
  130.         }
  131.     } while (prevNode->next != NULL);
  132.     // 前进直至终点节点
  133. 	
  134.     // 输出终点节点步数
  135.     return prevNode->step;
  136. }
  137.  
  138. int main()
  139. {
  140.     // 便于之后高亮显示，否则会乱码
  141.     system("cls");
  142. 	
  143.     int i, j;
  144.     for (i = 1; i <= ROW; ++i)
  145.     {
  146.         for (j = 1; j <= COL; ++j)
  147.         {
  148.             printf("%d ", map[i][j]);
  149.         }
  150.         putchar(10);
  151.     }
  152.     putchar(10);
  153.  
  154.     int MinStep = bfs(1, 1);
  155.     // 标记最短路径
  156.     route();
  157.  
  158.     if(MinStep)
  159.         printf("Min step = %d\n", MinStep);
  160.     else
  161.         printf("Not Found!");
  162. 	
  163.     for (i = 1; i <= ROW; ++i)
  164.     {
  165.         for (j = 1; j <= COL; ++j)
  166.         {
  167.             // 高亮显示路径
  168.             if (map[i][j] == 4)
  169.                 printf(Green "%d " None, map[i][j]);
  170.             else
  171.                 printf("%d ", map[i][j]);
  172.         }
  173.         putchar(10);
  174.     }
  175. 	
  176.     // 防止内存泄漏
  177.     quit();
  178.     return 0;
  179. }

3.4 运行结果演示

4. 总结

        BFS广度优先算法的实现要注意入队与出队时机、循环结束条件以及继续搜索条件。

        试试看自己写一遍，想想如果想以矩形方式扩散搜索该怎么实现呢？（如下图）

（文中代码皆已经过编译运行）

文章为本人原创，创作不易，感谢支持！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/445374
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号