2019考研计算机数据结构考点：图的遍历

考研网

根据历年考试经验，数据结构所占分值为45分，所占分值比重较大;而且数据结构部分的知识比较难于理解，为方便考生更好地复习计算机专业课，新东方在线整理了考研计算机数据结构的有关内容，以供大家参考，希望对大家有所帮助。
        三、图的遍历
        1. 深度优先搜索(DFS)
    搜索策略：
    访问当前顶点vi，寻找与vi相邻且未被访问顶点vj，若存在，将其作为当前点，访问，并重复上述搜寻过程。
    否则(所有邻接点都被访问过)，退回一步，寻找与前一个顶点相邻的未被访问顶点，访问，并重复上述过程。
    若上述过程无法访问图中的所有顶点，则另选一个新顶点重新开始。
    深度优先搜索是一种纵向搜索的过程。
    　　2. 广度优先搜索(BFS)
    访问出发点v0，依次访问v0的各个未曾访问过的邻接点，然后分别从这些邻接点出发重复上述过程。
    若上述过程无法访问图中的所有顶点，则另选一个新顶点重新开
    始。
    广度优先搜索是一种横向搜索的过程。
    使用队列结构。