广度优先搜索和深度优先搜索

广度优先搜索

广度优先搜索（Breadth-First-Search，BFS）类似于二叉树的层序遍历算法（借助队列），其基本思想是：首先访问起始顶点，接着由v出发，依次访问v的各个未访问过的邻接顶点w1，W2,…，Wn，然后依次访问w1，W2,…，Wn的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点……以此类推，直到图中所有顶点都被访问过为止。Dijkstra 单源最短路径算法和Prim最小生成树算法也应用了类似的思想。