做菠菜网站,西安未央区今天出啥事了,中小企业还需要网站吗,临汾网站开发图论
DFS stack O(h) 不具有最短性
BFS queue O(2^h) 最短路 迪杰斯特拉算法 初始化#xff1a; 将起始节点 A 的距离设为 0。将其他所有节点的距离设为无穷大。创建一个优先队列#xff0c;并将起始节点 A 加入优先队列。 处理队列#xff1a; …图论
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 d1d2; };这个是最大堆还是最小堆 堆顶是优先级最高值最大的元素。 捕获参数 const auto e1 和 const auto e2这两个参数是要比较的元素类型自动推断。结构化绑定 auto [x1, y1, d1] e1; 和 auto [x2, y2, d2] e2;使用结构化绑定来解包元素。这些元素应该是类似于 tuple 或 pair 的结构其中 d1 和 d2 是我们要比较的第三个元素假设它们是优先级或距离。返回比较结果 return d1 d2;比较 d1 和 d2。如果 d1 大于 d2则返回 true。
在 priority_queue 中如果比较函数返回 true表示 e1 应该排在 e2 之前。默认情况下priority_queue 是最大堆即较大的元素优先。然而在这个自定义比较函数中
当 d1 d2 时e1 被认为优先级更高排在 e2 前面。因此较小的 d 会被认为优先级较低。
结论
这个比较函数实际上创建了一个 最小堆因为 priority_queue 会根据 d 的值按升序排列即优先处理 d 值较小的元素。
