上一节介绍了图的基本概念，这一节介绍图的搜索算法。
图的搜索算法，最直观的理解就是从一个顶点到另一个顶点的路径。
最简单的是广度优先搜索和深度优先搜索，这也是这一节介绍的内容。另外还有A*、IDA*等启发式搜索算法。
本节内容以无向图为例，以下代码是图的代码实现。
讯享网
广度优先搜索（Breadth-First-Search），简称BFS。一种“地毯式”的搜索策略，即先搜索跟起始点最近的顶点，慢慢往外扩散搜索。
代码实现如下：
讯享网
通过下图来介绍BFS是如何执行的。
时间复杂度分析：
- 时间复杂度：O(E)。E表示图的边数
- 空间复杂度：O(V)。V表示图的顶点数
深度优先搜索（Depth-First-Search），简称DFS。最直观的例子是“走迷宫”，往最里面走，遇到分叉路先走一边然后再退回来走另一边，直到走到终点。
代码实现如下：
时间复杂度分析：
- 时间复杂度：O(E)。E表示图的边数
- 空间复杂度：O(V)。V表示图的顶点数
如何找出社交网络中某个用户的三度好友关系？
社交网络可以用图来表示，找出某个用户的三度好友，即是从某个顶点（某个用户）走三步到达的顶点（三度好友）。
可使用BFS或DFS来实现，增加一个值来保存好友是第几度的，遍历过程里把度分别为1、2、3的顶点保存到结果集里。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/153574.html