算法笔记 图论和优先级队列的笔记
图论
DFS stack O(h) 不具有最短性
BFS queue O(2^h) 最短路
迪杰斯特拉算法 Dijkstra算法
-
初始化：
- 将起始节点
A的距离设为0。 - 将其他所有节点的距离设为无穷大。
- 创建一个优先队列，并将起始节点
A加入优先队列。
- 将起始节点
-
处理队列：
- 从优先队列中取出距离最小的节点
u。 - 对于
u的每个邻接节点v，计算从u到v的路径长度，如果该长度小于当前记录的v的最短路径，则更新v的最短路径并将v加入优先队列。
- 从优先队列中取出距离最小的节点
Floyd多元最短路 O(n^3)
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);拓扑排序的算法步骤
建图邻接列表
-
计算每个节点的入度：
- 对于每一个节点，计算它有多少条边指向它，并记录这些入度。
-
找到所有入度为 0 的节点并将它们放入队列：
- 初始化一个队列，将所有入度为 0 的节点入队。
-
处理队列中的节点：
- 从队列中取出一个节点，将它添加到拓扑排序结果中。
- 对这个节点的每一个邻接节点，减少它们的入度（因为这个节点已经被移除）。
- 如果某个邻接节点的入度变为 0，则将该节点入队。
-
重复步骤 3，直到队列为空：
- 如果所有节点都被处理，则成功地得到了一个拓扑排序。
- 如果还有节点未被处理且队列为空，说明图中存在环，无法进行拓扑排序。
二分图
当且仅当图中没有奇数环
优先级队列
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; };这个是最大堆还是最小堆
堆顶是优先级最高（值最大）的元素。
- 捕获参数：
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 值较小的元素。