Question

列出2种图的遍历方法并简述其思想

Answer 1

深度遍历：
假设从图中的某个顶点v出发，访问此节点后，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则选另选一个未曾访问的顶点作为起始点重复上述过程，直至图中的所有节点都被访问到为止。
广度遍历：
假设从图中某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发并依次访问它们的邻接点，并使“先被访问的顶点邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点重复上述过程，直至图中所有顶点均被访问到为止。