图论知识总结

朴素的Dijkstra算法

求点之间距离不相同的最短路算法

时间复杂度$O(n^2+m)$,n表示点数,m表示边数,模板题

int g[N][N];  // 存储图
int dist[N];  // 1号点到每个点的距离
int st[N];    // 是否已经确定为最小距离
int n,m;      // 点数 边数

int dijkstra(){
    // 初始化距离
    memset(dist,0x3f,sizeof(dist));
    dist[1] = 0;
    
    for(int i = 0; i < n - 1; i++){
        // 找到没有在集合st中,距离起点最近的点
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        // 更新距离
        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j],dist[t] + g[t][j]);
        // 将该点加入st中
        st[t] = true;
    }
    
    return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}

堆优化的Dijkstra算法

typedef pair<int,int> PII;
priority_queue< PII,vector<PII>,greater<PII> > heap;

const int N = 1e5 + 10;
vector<PII> g[N];
int dist[N];  // 1号点到每个点的距离
int st[N];    // 是否已经确定为最小距离
int n,m;      // 点数 边数

int dijkstra(){
    // 初始化距离
    memset(dist,0x3f,sizeof(dist));
    dist[1] = 0;

    heap.push({0, 1});
    
    for(int i = 1; i < n; i++){
        // 找到没有在集合st中,距离起点最近的点
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first;
        // 将该点加入st中
        if(st[ver]) continue;
        st[ver] = true;
        
        // 更新距离       
        for(auto to : g[ver]){
            int dis = to.first, tar = to.second;
            if(dist[tar] > dist[ver] + dis){
                dist[tar] = dist[ver] + dis;
                heap.push({dist[tar],tar});
            }
        }
    }
    return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}

int main(){
    cin >> n >> m;
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        // g[a][b] = min(g[a][b],c);
        // 先是距离,后是点
        g[a].push_back({c,b});
    }
    
    cout << dijkstra();
    return 0;
}

拓扑排序

DAG: 有向无环图

拓扑序形象理解: 一些敌人可以互相看到,你要暗杀所有人而不被发现

拓扑序形

模板题链接: https://acwing.com/problem/content/description/850/

伪代码:

把所有入度为零的点,扔到一个队列里:
while 队列非空:
  取队首点P
  访问P的所有相邻点O,将其入度减一
  若此时入度为0,Q入队
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 1e5+10;
int deg[N];
vector<int> v[N];
queue<int> q;
int n,m;

vector<int> topsort(){
    vector<int> ans;
    for(int i = 1; i <= n; i++)
        if(deg[i] == 0) q.push(i);
    
    while(q.size()){
        int now = q.front();
        ans.push_back(now);
        q.pop();
        for(auto to: v[now]){
            deg[to] -= 1;
            if(deg[to] == 0)
                q.push(to);
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin >> n >> m;
    
    while(m--){
        int x,y;
        cin >> x >> y;
        v[x].push_back(y);
        deg[y]++;
    }
    auto res = topsort();
    
    if(res.size() == n)  
        for(auto x: res) cout << x << " "; 
    else  
        cout << -1 << endl;
    return 0;
}

SPFA算法

求图中的带有负边的最短路算法

n表示点数,m表示边数 最好时间复杂度$O(m)$,最好时间复杂度$O(nm)$,模板题

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int n,m;

typedef pair<int,int> PII;
vector<PII> g[N];

int st[N];
int dist[N];

int spfa(){
    memset(dist,0x3f,sizeof dist);
    queue<int> q;
    q.push(1);
    st[1] = true;
    dist[1] = 0;
    
    while(q.size()){
        int front = q.front();
        q.pop();
        st[front] = false;
        
        for(auto to : g[front]){
            int t = to.first;
            int w = to.second;
            if(dist[t] > dist[front] + w){
                dist[t] = dist[front] + w;
                if( !st[t] ) {
                    st[t] = true;
                    q.push(t);
                }
            }
        }
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    ios::sync_with_stdio(0);
    cin >> n >> m;    
    
    while(m--){
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back({v,w});
    }
    
    int res = spfa();
    if(res == -1) cout << "impossible" << endl;
    else cout << res << endl;
    return 0;
}

朴素的Prim算法

求图中的最小生成树算法

时间复杂度$O(n^2+m)$,n表示点数,m表示边数,模板题

const int N = 550, INF = 0x3f3f3f3f;
int g[N][N], st[N], dist[N];
int n,m;

int prim(){
    // 初始化到集合的距离
    memset(dist,0x3f,sizeof dist);
    int res = 0;
    
    for(int i = 0; i < n; i++){
        // 寻找到集合最近的点
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        
        // 如果不是第一个点,并且距离为正无穷
        // 返回正无穷,也就是没有最小生成树
        if(i && dist[t] == INF) return INF;
        
        // 距离相加
        if(i) res += dist[t];
        st[t] = true;
        
        // 更新距离
        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j],g[t][j]);
    }
    return res;
}

tarjan算法

求图中的强联通分量


int dfn[N], low[N];   // 高低数组
int stk[N], top, ts;  // 模拟栈
bool in_stk[N];       // 是否在栈中

void tarjan(int now){
    // 0. 准备遍历now这个点
    dfn[now] = low[now] = ++ ts;
    stk[++top] = now, in_stk[now] = true;
    for(int to:v[now]){
        // 1. 看看下一个点是否能更新当前点的时间戳
        if(!dfn[to]){
            tarjan(to);
            low[now] = min(low[now],low[to]);
        }
        // 2. 下一个点在栈中,看看能否更新当前点的时间戳
        else if(in_stk[to]) low[now] = min(low[now],low[to]);
    }
    // 3. 将当前节点进行出栈
    if(dfn[now] == low[now]){
        int y,cnt = 0;
        do{
            y = stk[top --];
            in_stk[y] = false;
        }while(y != now);
    }
}