图论算法模板大全：最短路、最小生成树、拓扑排序，一次搞定

📊 核心数据

1. Dijkstra算法（单源最短路，无负权）

// 邻接表存图
vector<pair<int, int>> g[maxn];
int dist[maxn];
bool vis[maxn];

void dijkstra(int s) {
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[s] = 0;
    
    // 小顶堆，pair<距离, 节点>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        if (vis[u]) continue;
        vis[u] = true;
        
        for (auto &edge : g[u]) {
            int v = edge.first, w = edge.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

时间复杂度：O((n+m)log n)

适用场景：无负权边的单源最短路

2. Floyd算法（多源最短路）

int dist[maxn][maxn];

void floyd(int n) {
    // 初始化
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
    
    // 核心三重循环
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dist[i][j] > dist[i][k] + dist[k][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
}

时间复杂度：O(n³)

适用场景：n≤500的多源最短路

3. SPFA算法（有负权边）

int dist[maxn];
bool inq[maxn];
int cnt[maxn];  // 记录入队次数，判断负环

bool spfa(int s, int n) {
    memset(dist, 0x3f, sizeof(dist));
    memset(inq, false, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    inq[s] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        
        for (auto &edge : g[u]) {
            int v = edge.first, w = edge.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                    cnt[v]++;
                    if (cnt[v] > n) return false;  // 存在负环
                }
            }
        }
    }
    return true;
}

时间复杂度：O(km)，k为常数，最坏O(nm)

1. Kruskal算法（并查集）

struct Edge {
    int u, v, w;
    bool operator<(const Edge &other) const {
        return w < other.w;
    }
} edges[maxm];

int fa[maxn];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int kruskal(int n, int m) {
    for (int i = 1; i <= n; i++) fa[i] = i;
    sort(edges, edges + m);
    
    int ans = 0, cnt = 0;
    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            fa[fu] = fv;
            ans += w;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    return cnt == n - 1 ? ans : -1;  // -1表示不连通
}

时间复杂度：O(m log m)

vector<int> g[maxn];
int indeg[maxn];
vector<int> topo;

bool topologicalSort(int n) {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        
        for (int v : g[u]) {
            indeg[v]--;
            if (indeg[v] == 0) q.push(v);
        }
    }
    
    return topo.size() == n;  // 判断是否有环
}

时间复杂度：O(n+m)

📌 薛老师最后的话

图论算法，重在模板熟练。

把这些模板背熟，考试时直接套用，又快又准。