本文首发在:刘冲的博客。
图遍历搜索算法是一种非常迷人的算法,它是一种将抽象枯燥的逻辑与较为直观的“图”相结合的算法。本文将讨论图遍历搜索算法背后的逻辑,并且通过简单的实例来理解广度优先搜索算法的工作原理。
图遍历搜索算法简介
按照最浅显的解释,访问(visiting)
和探索(exploring)
图并且进行处理的过程就称为“图遍历”,在这个过程中,关键在于要 visiting 和 exploring 图中的每个顶点和边,还要争取所有的顶点只被搜索一次。
图遍历搜索算法有广度优先搜索、深度优先搜索等,挑战在于针对具体的问题,选择使用最适合的图遍历技术,若要做到这一点,需要“知己知彼”,本文将较为详细的讨论广度优先搜索算法(Breadth-First Search Algorithm)。
什么是广度优先搜索算法?
首先,广度优先搜索算法属于图遍历算法,因此前文讨论图遍历算法的特点,广度优先搜索算法都有。在该算法中,我们可以任意选择一个随机的初始节点(称作源节点或者根节点),并且以 visiting 和 exploring 所有节点及其子节点的方式开始遍历图。
广度优先遍历搜索的最通俗介绍 如何实现广度优先搜索算法?广度优先遍历搜索可用于哪些行业?