深度优先查找和广度优先查找.docx

深度优先查找和广度优先查找 深度优先查找（DFS）和广度优先查找（BFS）用来系统地遍历图中所有点和边。 一．深度优先查找（DFS） 深度优先查找可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。在每次迭代的时候，该算法紧接着处理与当前顶点邻接的未访问顶点。（如果有若干个这样的顶点，可以任意选择一个顶点。但在实际应用中，选择哪一个邻接的未访问候选顶点主要是由图的数据结构决定的。）这个过程一直持续，直到遇到一个终点—该顶点的所有邻接顶点都已被访问过。在该终点上，该算法沿着来路后退一条边，并试着继续从那里访问未访问的顶点。在后退到起始顶点，并且起始顶点也是一个终点时，该算法最终停了下来。这