本文主要是介绍多源 BFS,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
例题一
解法(bfs)(多个源头的最短路问题)
算法思路:
对于求的最终结果,我们有两种⽅式:
• 第⼀种⽅式:从每⼀个 1 开始,然后通过层序遍历找到离它最近的 0 。
这⼀种⽅式,我们会以所有的 1 起点,来⼀次层序遍历,势必会遍历到很多重复的点。并且如果
矩阵中只有⼀个 0 的话,每⼀次层序遍历都要遍历很多层,时间复杂度较⾼。
• 换⼀种⽅式:从 0 开始层序遍历,并且记录遍历的层数。当第⼀次碰到 1 的时候,当前的层数
就是这个 1 离 0 的最短距离。
这⼀种⽅式,我们在遍历的时候标记⼀下处理过的 1 ,能够做到只⽤遍历整个矩阵⼀次,就能得
到最终结果。
但是,这⾥有⼀个问题, 0 是有很多个的,我们怎么才能保证遇到的 1 距离这⼀个 0 是最近的
呢?其实很简单,我们可以先把所有的 0 都放在队列中,把它们当成⼀个整体,每次把当前队列⾥⾯的所有元素向外扩展⼀次。
例题二
解法:
算法思路:
正难则反:
从边上的 1 开始搜索,把与边上 1 相连的联通区域全部标记⼀下;然后再遍历⼀遍矩阵,看看哪些位置的 1 没有被标记即可标记的时候,可以⽤「多源 bfs 」解决。
例题三
解法:
算法思路:
01矩阵的变型题,直接⽤多源 bfs 解决即可。
例题四
解法:
算法思路:
01矩阵的变型题,直接⽤多源 bfs 解决即可。
这篇关于多源 BFS的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!