Question

深度优先遍历的思想是什么？

Answer 1

深度优先遍历类似树的先序遍历，是树的先序遍历的推广。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先遍历的思想是：首先访问图中某指定的起始点vi，然后由vi出发访问它的任一个邻接点vj，再从vj出发访问vj任一个未被访问的邻接点vk，接着从vk出发进行类似的访问，如此进行下去，一直到某顶点已没有未被访问过的邻接点，则退回一步，找前一个顶点的其他尚未被访问的邻接点。如果有尚未被访问的邻接点，则访问此顶点后，再从该顶点出发进行与前述类似的访问；如果退回一步后，前一个顶点也没有未被访问的邻接点，则再向前回退一步再进行搜索，重复上述过程，直到所有顶点均被访问过为止。