深度优先遍历(Depth First Search)

您所在的位置：网站首页 › 常用的图的遍历方法有深度优先遍历和广度优先遍历 › 深度优先遍历(Depth First Search)

深度优先遍历(Depth First Search)

#深度优先遍历(Depth First Search)| 来源: 网络整理| 查看: 265

深度优先遍历，也称深度优先查找、深度优先搜索等。

基本思想

假设初始状态时图中所有顶点都未曾被访问，则深度优先遍历算法从图中某个顶点(任一顶点)出发，访问此顶点并把该顶点标记为已访问，然后依次从该顶点邻接的未被访问的顶点出发，深度优先遍历图，直至图中所有和该顶点有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。

伪代码实现

假设图G(V, E)表示要遍历的图，深度优先遍历的伪代码实现如下：

使用邻接矩阵或邻接表表示图G(V, E) 使用visited[VertexCount]数组记录顶点是否已被访问，其中true表示已访问，false表示未访问 for i=0;i

【本文地址】

深度优先遍历(Depth First Search)

深度优先遍历(Depth First Search)

今日新闻

推荐新闻