宽度优先搜索的基本思路是什么？

2023-08-23 17:00:00 · baa · 乐百管

宽度优先搜索的基本思路是通过已找到和未找到顶点之间的边界向外扩展。算法首先搜索与源顶点距离为k的所有顶点，然后再搜索与源顶点距离为k+1的其他顶点。为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：白色

宽度优先搜索的基本思路是通过已找到和未找到顶点之间的边界向外扩展。算法首先搜索与源顶点距离为k的所有顶点，然后再搜索与源顶点距离为k+1的其他顶点。为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：白色、灰色或黑色。算法开始前，所有顶点都是白色，随着搜索的进行，顶点逐渐变成灰色，然后变为黑色。在搜索中第一次碰到一个顶点时，该顶点被发现并变为非白色顶点。灰色和黑色顶点都已被发现，但是宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。在宽度优先搜索过程中，建立了一棵宽度优先树，起始时只包含根节点，即源顶点。在扫描已发现顶点的邻接表的过程中，每发现一个白色顶点v，顶点v及边(u,v)就被添加到树中。宽度优先树中，结点u是结点v的先辈或父母结点。宽度优先搜索与深度优先搜索的区别在于搜索顺序不同，深度优先搜索使用栈实现，而宽度优先搜索使用队列实现。

_{免责声明：本内容来源于第三方作者授权、网友推荐或互联网整理，旨在为广大用户提供学习与参考之用。所有文本和图片版权归原创网站或作者本人所有，其观点并不代表本站立场。如有任何版权侵犯或转载不当之情况，请您通过400-62-96871或关注我们的公众号与我们取得联系，我们将尽快进行相关处理与修改。感谢您的理解与支持！}