Tag Archives: 图的遍历

数据结构重读 - 图的遍历(概念)

图的遍历:从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次。

图比树复杂,为了避免同一顶点被访问多次,可以设置一个辅助数组,初始值置为False或者0。当访问到后,设置值为真或被访问的次序ID。

图遍历主要有两种:深度优先搜索、广度优先搜索。

深度优先遍历

是树的先根遍历的推广。

从图中某个顶点v出发,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v相连通的路径都被访问到。然后再另选一个未被访问的结点做为起始点。

代[......]

继续阅读