搜索时，先标记/后标记（入队标记/出队标记）

作者： 作者的头像   AcWing金牌员工 ,  2022-10-22 11:35:34 ,  所有人可见 ,  阅读 187

5


2

先标记：

如果能保证加入的点不再更新，可以先标记。
例如：
权值相等的bfs：初次入队肯定是距离最小的情况。
ps：
先标记可以不用创建 标记数组st，直接使用 距离数组dist，初始化-1.

后标记：

如果不能保证上述，只能后标记。
例如：
dijkstra：一个点可以被更新多次，需要后标记；
双端队列：一个点可能先加入队尾，又加入队头，不满足先标记的要求。

2 评论

用户头像
yuwuy   2022-10-24 18:38         踩      回复

膜拜大佬

用户头像
AcWing金牌员工   2022-10-24 22:09         踩      回复

佬别骂

1024
x