算法笔记 图论和优先级队列的笔记

图论

DFS       stack     O(h)     不具有最短性

BFS       queue    O(2^h)   最短路

迪杰斯特拉算法

• 初始化：

  • 将起始节点 A 的距离设为 0。
  • 将其他所有节点的距离设为无穷大。
  • 创建一个优先队列，并将起始节点 A 加入优先队列。

• 处理队列：

  • 从优先队列中取出距离最小的节点 u。
  • 对于 u 的每个邻接节点 v，计算从 u 到 v 的路径长度，如果该长度小于当前记录的 v 的最短路径，则更新 v 的最短路径并将 v 加入优先队列。

优先级队列

lambda函数中 >是最小堆， <是最大堆

greater是最小堆，less是最大堆

• 最大堆：默认情况下，priority_queue 是最大堆，因为它使用 < 比较函数。这意味着较大的元素具有较高的优先级。
• 最小堆：通过使用 greater<> 比较函数，priority_queue 变成了最小堆。greater<> 确保较小的元素具有较高的优先级。
• 自定义比较函数：使用 lambda 表达式或其他自定义比较函数，可以灵活地定义优先级规则。

auto tupleCmp =[](const auto& e1,const auto& e2){ auto&& [x1,y1,d1]=e1; auto&& [x2,y2,d2]=e2; return d1>d2; };这个是最大堆还是最小堆

堆顶是优先级最高（值最大）的元素。

1. 捕获参数：
   • const auto& e1 和 const auto& e2：这两个参数是要比较的元素，类型自动推断。
2. 结构化绑定：
   • auto&& [x1, y1, d1] = e1; 和 auto&& [x2, y2, d2] = e2;：使用结构化绑定来解包元素。这些元素应该是类似于 tuple 或 pair 的结构，其中 d1 和 d2 是我们要比较的第三个元素（假设它们是优先级或距离）。
3. 返回比较结果：
   • return d1 > d2;：比较 d1 和 d2。如果 d1 大于 d2，则返回 true。

在 priority_queue 中，如果比较函数返回 true，表示 e1 应该排在 e2 之前。默认情况下，priority_queue 是最大堆，即较大的元素优先。然而，在这个自定义比较函数中：

• 当 d1 > d2 时，e1 被认为优先级更高，排在 e2 前面。
• 因此，较小的 d 会被认为优先级较低。

结论：

这个比较函数实际上创建了一个 最小堆，因为 priority_queue 会根据 d 的值按升序排列，即优先处理 d 值较小的元素。