Wa1kingDead

0x20 搜索

0x10 基本数据结构(3) 0x60 图论(1) 日常训练(6)

/ 注册

全部文章 / 0x20 搜索（共3篇）

暑期训练之广搜变形

一、双端队列BFS最基本的宽搜，其实等价于在一张边权都为1的图上执行的宽度优先遍历，求出每个点相对于起点的最短距离。然而如果图上的边权不全为1呢？我们可以通过双端队列+宽搜来计算。算法的框架基本相同，只是在每个节点上沿着分支拓展的时候稍作改变。例如：如果这条分支的边权为0，就把这条分支的新节点从队头...

2020-06-28

2 421

暑期训练之搜索(BFS)

宽度优先搜索按照距开始阶段由近及远的顺序进行搜索，因此很容易地来求最短路径、最少操作之类问题的答案。我们借助一个队列来实现宽搜，起初，队列中仅仅包含起始状态。在宽搜的过程中，我们不断地从队头取出状态，对于该状态面临的所有分支，把沿着每一条分支到达的下一个状态（尚未访问过或者能够被更新成更优的解）插入...

2020-06-26

2 450

暑期训练之搜索(DFS)

暑假开始了，之前搜索学的不扎实，于是现在开始重新学习搜索。········DFS篇·························································································一、部分和问题 #include <...

2020-06-26

1 436