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

图论

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; };这个是最大堆还是最小堆

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

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 值较小的元素。