搜索算法-深度优先搜索
DFS(G, s)
for 在图G中的每⼀一个节点v
status[v] = WHITE
// 进⾏行其他初始
DFS-VISIT(s)
DFS-VISIT(v)
status[v] = GRAY
for 每⼀一个v的邻接节点
if (status[v] == WHITE)
DFS-VISIT(t)
status[v] = BLACK
如果想实现深度优先遍历的非递归实现,就需要用到stack来存储未被访问的节点,以便回溯时能够找到
DFS(G, s)
stack visted, unvisited
unvisited.push(s)
while (!unvisited.empty()) // 只有当unvisted不空
current = unvisited.pop()
for 每⼀一个current的邻接节点v and 节点v不在visited中 // 在以上的图例中是按从右向左的⽅方式来遍历这些邻接节点
unvisited.push(v)
visted.push(current)
非递归实现的图片实例,图片中显示了unvisted栈中的数据情况:
深度优先搜索的伪码实现
深度优先搜索与深度优先遍历大部分实现是相同的,只是深度优先搜索会在找到终点时就退出搜索。
以下是深度优先搜索的伪码实现:
DFS(G, s, d)
stack visted, unvisited
unvisited.push(s)
while (!unvisited.empty()) // 只有当unvisted不空
current = unvisited.pop()
if (current == d)
break;
for 每⼀一个current的邻接节点v and 节点不在visited中 // 在以上的图例中是按从右向左的⽅方式来遍历这些邻接节点
v.prev = current
unvisited.push(v)
visted.push(current)