广度优先搜索算法,项目实战北京地图

718 阅读2分钟

北京很大,附上地铁图,不要迷路!!!

作为一个程序员,在北京,你很有可能住在回龙观地区,经常从龙泽上地铁,然后畅游北京。

当有一天,你老家的朋友来北京了,希望你能够带她去天安门玩一玩,你该怎么坐地铁呢?

基本要求,我们乘坐地铁,绿色出行,但希望换乘的最少。

此时,有可能你并不懂广度优先搜索算法,但实际上你已经运用了它。

找出从龙泽到天安门东的最短路径问题,就叫做广度优先搜索

下图列除了部分可以到达的路线:

从龙泽前往天安门东的最短路径需要三步,这种问题被称之为最短路径问题,那么解决最短路径问题的算法被称之为广度优先搜索

是不是这种概念,非常容易理解。

那我们进一步对广度优先搜索进行一个说明:

  • 广度优先搜索是一种用于图的查找算法,可以解决两类问题

    • 从节点A出发,能够到达节点B么!

    • 从节点A出发,前往节点B的路径中,最短的是哪条路径!

举个🌰

金融场景下,借款人A到平台借款,逾期未还,假定我们知道他的朋友中(朋友13)会帮助他还,这个例子可能不是特别的恰当,但可以帮助大家说明问题,并深入理解广度优先搜索

广度优先搜索,不仅查找从借款人A到朋友13的路径,而且找到的是最短路径,为什么要找到最短路径呢,原因是图关系中,越近找到,说明关系越紧密。

如果你懂知识图谱技术的话,那可能直接用最短路径算法,就可以直接获取到。那么不用知识图谱的图计算技术,就可以用到队列的技术来实现

那么这里需要注意一个问题,这个问题就是当执行到朋友1时,要把借款人自己给去除掉,否则就变成了死循环了

最后的总结:

  • 广度优先搜索指出是否有从A到B的路径

  • 广度优先搜索将会找出最短路径

  • 可以先创建图,然后再根据图关系使用广度优先搜索算法来解决问题

  • 你需要按照加入的顺序去检查,否则找到的不是最短路径,因此如果你用的不是知识图谱的图算法技术,那么就必须是队列

  • 对于检查过的人,就不要再检查了,否则会造成死循环