问题:接上一篇文章我们用图这种数据结构存储好友之间的关系,那么我们如何获取2度、3度关系,或者说在迷宫中如何获取出口呢?
针对上述问题介绍俩种图的搜索算法广度搜索发(bfs)、深度搜索发(dfs)
BFS-广度搜索法–2、3度人脉
如图:
原理:我们先从起点找到最近的点,然后逐层扩大直到找到终点或者找到我们需要的层级。代码如下:
1 | public void search(Vertex end) { |
时间复杂度:E代表边,V代表点,最坏情况下访问所有的边和点,即O(V+E),可以简写为O(E)。
1 | //上述找到N度关系 |
深度优先算法
原理:类似走迷宫的场景,主要采用回溯的思想,当一条道路走不通,往回退一步选择别的道路
如图:
1 | public class DFS { |
时间复杂度,最坏情况下每个边访问俩遍所以是O(E)