广度优先搜索

2018-06-03 本文已影响0人小懒额

在了解广度优先搜索之前，先看一个问题，如下图所示，从 v1 到 v7，那么怎么去找到最短路径呢？

可以先从 v1 开始，列出 v1 的下一个点有哪些？

接下来，再看 v2 和 v3 的下一个点有哪些？

再看 v5、v4、v6 这三个点的下一个点是什么？

很显然，这时候已经出现最短路径了，即 v1->v2->v5->v7。
像上面这种问题，称为最短路径问题。解决最短路径问题的算法称为广度优先搜索。
每个 v 节点和连接节点的边组成图。