深度优先遍历的顺序

为什么这个图的遍历顺序会是:v1,v2,v5,v10,v6,v7,v3,v12,v11,v8,v4,v9?
怎么也搞不明白,简单图的深度优先看的懂,一到复杂的就懵圈了
图片描述

阅读 3.3k
评论
    2 个回答
    • 12.3k

    这得看具体代码实现了吧,深度优先只规定了往沉挖,没规定同级别的节点间怎么排序。

      • 2
      • 新人请关照

      首先,不管图的表示方式是邻接链表还是邻接矩阵,每个结点寻找与之相连的节点的顺序是固定的,看这个便利顺序应该是从小到大。
      然后就是遍历过程的原则了:

      1. 遍历过的结点标记,标记过的结点不会再次遍历
      2. 当没有结点可以遍历时,原路返回直到有其它结点可以遍历

      接下来我们看看这个图,
      v1,v2,v5,v10的遍历应该没问题,这时候v1,v2,v5,v10都被标记了,V10没有其它结点相连,所以返回,一直返回到结点V2,
      与V2相连的按照顺序有V1,V5,V6,V7,其中V1,V5被标记了,所以到V6
      与V6相连的按照顺序有V2,V7,V11,其中V2被标记了,所以到V7
      与V7相连的按照顺序有V2,V3,V6,V12,其中V2被标记了,所以到V3
      与V3相连的按照顺序有V1,V7,其中V1,V7都被标记了,所以返回到V7,
      与V7相连的按照顺序有V2,V3,V6,V12,其中V2,V3,V6被标记了,所以到V12
      与V12相连的都被标记了,所以返回,一直返回到V6
      与V6相连的按照顺序有V2,V7,V11,其中V2,V7被标记了,所以到V11
      与V11相连的按照顺序有V6,V8,其中V6被标记了,所以到V8
      与V8相连的按照顺序有V4,V11,所以到V4
      与V4相连的按照顺序有V1,V8,V9,,其中V1,V8被标记了,所以到V9
      与V9相连的都被标记了,所以返回,发现所有的结点都被标记了,结束。

      上面加粗的就是便利顺序了

        撰写回答

        登录后参与交流、获取后续更新提醒

        相似问题
        推荐文章