图论

无权图的最短路算法

输入: 所有节点 , 所有边

1. 初始化一个空队列

2. 初始化下表

   vertex	visit	dist	path
   	false	∞	0
   	false	∞	0
   ...	...	...	...
   	false	∞	0

   1. 将 (是否访问过)全设置为
   2. 将 (最短路长度)全设置为无穷
   3. 将 (最短路径)全都设置为

3. 将起点 添加到队列

4. 将 设置为 ， 设置为

5. 开始循环，直到队列清空

   1. 取出队列顶部元素
   2. 遍历与 相邻的所有未被访问过 的节点
      1. 将 插入队列

时间复杂度:

非负有权图的最短路算法(Dijkstra)

输入: 所有节点 , 所有边

1. 初始化一个空的优先队列，按到起点的距离排序，距离小的在前

2. 初始化下表

   vertex	dist	path
   	∞	0
   	∞	0
   ...	...	...
   	∞	0

   1. 把 全都设置为无穷
   2. 把 全都设置为

3. 把起点 的距离设置为 :

4. 将起点 插入队列

5. 开始循环，直到队列被清空

   1. 取出队列顶部元素
   2. 遍历所有与 相邻的节点
      1. 新的路径

      是从 到 的边的权重

      1. 如果 :
         • 将 插入队列，如果节点u已经在队列中，则修改节点到起点的距离

C++代码(邻接表):

const int N = 1e5 + 5;
int n, m;
vector<PLL> g[N];
int path[N];

vector<ll> dijkstra(int start)
{
    priority_queue<PLL, vector<PLL>, greater<PLL>> q;
    vector<ll> dist(n + 1, 1e15);
    dist[start] = 0;
    q.push({0, start});
    while(q.size()) {
        auto [dist_v, v] = q.top();
        q.pop();
        if(dist[v] < dist_v)  continue;
        for(auto [u, e] : g[v]) {
            auto d = dist[v] + e;
            if(d < dist[u]) {
                dist[u] = d;
                path[u] = v;
                q.push({d, u});
            }
        }
    }
    return dist;
}

返回值是一个数组，表示从起点到每个节点的最短路径长度

时间复杂度:

最小生成树(Prim)

输入: 所有节点 , 所有边

1. 初始化一个空的优先队列，按边的权重排序，权重小的在前
2. 初始化 visited 数组，表示节点是否被访问过
3. 初始化一个空的边集合，表示最小生成树的边
4. 将起点 的所有边加入队列
5. 将起点 的 设置为
6. 开始循环，直到队列被清空
   1. 取出队列顶部元素
   2. 如果 和 都已经被访问过，则跳过
   3. 将 加入最小生成树的边集合
   4. 将 和 中未被访问的节点加入队列，并将其 设置为

c++代码(邻接表):

ll prim(int s)
{
    ll sum = 0;
    unordered_set<ll> st;
    priority_queue<PLL, vector<PLL>, greater<PLL>> pq;
    for(auto [v, e] : g[s]) {
        pq.push({e, v});
    }
    st.insert(s);
    while (pq.size())
    {
        auto [e, v] = pq.top();
        pq.pop();
        if(st.count(v))
            continue;
        sum += e;
        st.insert(v);
        for(auto [u, d] : g[v]) {
            pq.push({d, u});
        }
    }
    return sum;
}

返回值是最小生成树的权重之和