图
请参考网页,尤其是邻接矩阵和邻接表定义:
9.1 图 - Hello 算法
图遍历:
BFS: BREADTH
队列维护遍历顺序,哈希集防止重复遍历
- 将遍历起始顶点
startVet
加入队列,并开启循环。 - 在循环的每轮迭代中,弹出队首顶点并记录访问,然后将该顶点的所有邻接顶点加入到队列尾部。
- 循环步骤
2.
,直到所有顶点被访问完毕后结束。
为了防止重复遍历顶点,我们需要借助一个哈希集合 visited
来记录哪些节点已被访问。
DFS 算法
“根 左 右”“左 根 右”“左 右 根”分别对应前序(Preorder)、中序(Inorder)、后序(Postorder)遍历,记忆:都是左先右后,只是根的位置,依次是前、中、后,因此说的是根的顺序
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Min的博客!
评论