CS61B 学习笔记 - BFS & DFS

BFS

直接放伪代码：

初始化一个空队列，称为 fringe
将起始节点入队 fringe
标记 起始节点

while fringe 非空：
    出队 fringe，并存储为节点 v
    for v 的所有邻居节点 n:
        if n 没有被标记：
            n 入队 fringe
            标记 n
            设置 edgeTo[n] = v
            设置 distTo[n] = distTo[v] + 1

这个幻灯片演示了广度优先搜索是如何运作的

DFS

初始化一个空栈，称为 fringe
将起始节点入栈 fringe

while fringe 非空：
    从 fringe 出栈一个节点 vertex
    if vertex 没有被标记：
        标记 vertex
        访问 vertex（对 vertex 进行操作）
        for v 所有的邻居节点 neighbor：
            if neighbor 没有被标记：
                neighbor 入栈 fringe