BFS 两个重要性质

对于进行广度优先搜索的队列中,应该始终满足两个性质:

 

性质1:若队首为第i层拓展到的节点,则队列中最多只能存在第i层和第i+1层的节点,不可能出现3层节点。

 

性质2:队列中的元素会严格按照层数单调递增,而且会按照入队的先后来判别拓展的优先程度,即先入队的一定是更优先的,而越往后越次之。

 

通过这两个性质,其实我们就可以更严格更方便更快捷更明确地设计有关BFS的程序,当已经找到一个目标节点,即可以终止程序(or过程)。

而对于单调性的优化,则可以使用单调队列、双端队列、优先队列代替普通队列,进而达到性质2的设计,不过要就具体情况分析。

原文地址:https://www.cnblogs.com/Ronald-MOK1426/p/8848716.html