图进阶：最小生成树与最短路径

说实话，图这块内容，是很多同学学数据结构时的分水岭。前面链表、栈、队列还算好理解，到了图这里，概念多、算法也多，容易懵。但我跟你说，搞懂了图，你才算真正入了数据结构的门。

今天咱们聊两个核心问题：最小生成树和最短路径。前者解决“怎么用最少的线把所有点连起来”，后者解决“从A到B怎么走最近”。听起来像一回事？其实完全不同。我当年刚学的时候也混淆过，后来在项目中踩了坑才彻底分清楚。

一、最小生成树

什么叫生成树？就是从一个连通图中，选出 n-1 条边（n是顶点数），构成一棵树，这棵树包含了原图的所有顶点。最小生成树，就是所有生成树里，边的权值总和最小的那棵。

我做过一个物联网项目，需要在厂区部署传感器节点。每个节点之间拉网线的成本不同，老板要求总成本最低。这不就是典型的最小生成树问题吗？当时我用了Prim算法，半小时搞定方案。

1.1 Prim算法

Prim算法的思路很朴素：从一个顶点开始，每次找一条连接“已选顶点集合”和“未选顶点集合”的最短边，把这个边和对应的顶点加进来，直到所有顶点都选完。

说白了，就是“贪心地长树”。

// Prim算法核心代码（邻接矩阵实现）
#define INF 0x3f3f3f3f
#define MAXV 100

int prim(int graph[MAXV][MAXV], int n) {
    int lowcost[MAXV];  // 记录顶点到当前树的最小距离
    int visited[MAXV] = {0};
    int total = 0;
    
    visited[0] = 1;
    for (int i = 0; i < n; i++) {
        lowcost[i] = graph[0][i];
    }
    
    for (int i = 1; i < n; i++) {
        // 找最小边
        int min = INF;
        int minIdx = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && lowcost[j] < min) {
                min = lowcost[j];
                minIdx = j;
            }
        }
        
        if (minIdx == -1) return -1;  // 图不连通
        
        total += min;
        visited[minIdx] = 1;
        
        // 更新lowcost
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[minIdx][j] < lowcost[j]) {
                lowcost[j] = graph[minIdx][j];
            }
        }
    }
    return total;
}

时间复杂度：O(n²)，n是顶点数。用堆优化可以降到O(m log n)，m是边数。

1.2 Kruskal算法

Kruskal的思路完全不同——它不看顶点，只看边。把所有边按权值从小到大排序，然后一条一条地选，只要这条边不会形成环，就把它加入生成树。

怎么判断会不会形成环？用并查集。我当年第一次写Kruskal时，并查集写错了，结果选出来的边总是多一条，调试了半天才发现是路径压缩没写好。

// Kruskal算法核心代码
typedef struct {
    int u, v, w;  // 起点、终点、权值
} Edge;

int cmp(const void* a, const void* b) {
    return ((Edge*)a)->w - ((Edge*)b)->w;
}

int find(int parent[], int x) {
    if (parent[x] != x)
        parent[x] = find(parent, parent[x]);  // 路径压缩
    return parent[x];
}

int kruskal(Edge edges[], int n, int m) {
    qsort(edges, m, sizeof(Edge), cmp);
    
    int parent[MAXV];
    for (int i = 0; i < n; i++) parent[i] = i;
    
    int total = 0, count = 0;
    for (int i = 0; i < m && count < n-1; i++) {
        int ru = find(parent, edges[i].u);
        int rv = find(parent, edges[i].v);
        if (ru != rv) {
            parent[ru] = rv;
            total += edges[i].w;
            count++;
        }
    }
    return total;
}

时间复杂度：O(m log m)，主要是排序的开销。适合稀疏图。

算法	适用场景	时间复杂度	核心思想
Prim	稠密图	O(n²)	从顶点出发，逐步扩展
Kruskal	稀疏图	O(m log m)	从边出发，贪心选边

二、最短路径

最小生成树是“连起来就行”，最短路径是“怎么走最近”。这两个问题在实际中经常混在一起，但你要记住：MST不保证任意两点之间的路径最短。

举个例子：你修路连接所有村庄，用MST最省钱。但你要从A村到B村送货，走MST上的路不一定最快，可能绕远了。

2.1 Dijkstra算法

Dijkstra解决的是单源最短路径问题——从一个源点出发，到其他所有点的最短路径。它要求图中不能有负权边。

为什么不能有负权？因为Dijkstra是贪心的，它每次选当前距离最小的顶点，认为这个顶点的最短路径已经确定了。如果有负权边，后面可能出现更短的路径，贪心就失效了。

// Dijkstra算法核心代码
#define INF 0x3f3f3f3f

void dijkstra(int graph[MAXV][MAXV], int n, int src) {
    int dist[MAXV];      // 距离数组
    int visited[MAXV] = {0};
    
    for (int i = 0; i < n; i++) dist[i] = INF;
    dist[src] = 0;
    
    for (int i = 0; i < n; i++) {
        // 找未访问中距离最小的顶点
        int min = INF, u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        if (u == -1) break;
        visited[u] = 1;
        
        // 更新邻居距离
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != INF 
                && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
}

时间复杂度：O(n²)，用堆优化可以降到O((n+m) log n)。

2.2 Floyd算法

Floyd算法解决的是多源最短路径问题——任意两点之间的最短路径。它的思路很暴力：对于每一对顶点，尝试把其他顶点作为中间点，看看能不能让路径更短。

说白了，就是三层循环：for k for i for j，如果 dist[i][k] + dist[k][j] < dist[i][j]，就更新。

// Floyd算法核心代码
void floyd(int graph[MAXV][MAXV], int n) {
    int dist[MAXV][MAXV];
    
    // 初始化
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dist[i][j] = graph[i][j];
    
    // 核心三重循环
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

Floyd还有一个好处：它可以处理负权边（只要没有负权环）。这一点Dijkstra做不到。

算法	解决的问题	时间复杂度	限制
Dijkstra	单源最短路径	O(n²) / O((n+m)log n)	不能有负权边
Floyd	多源最短路径	O(n³)	不能有负权环

三、总结与避坑

这四个算法，我建议你按这个顺序学：Prim → Kruskal → Dijkstra → Floyd。前两个是MST，后两个是最短路径，逻辑上分开学不容易混。

最后分享几个我踩过的坑：

• Prim和Dijkstra代码很像，但含义不同。Prim的dist记录的是到当前树的最小距离，Dijkstra的dist记录的是到源点的最短距离。我见过有人把Prim的更新条件写成 dist[u] + graph[u][v]，那就不对了。
• Kruskal一定要用并查集。别想着用visited数组判断环，那是错的。一个顶点可以多次出现在不同边里，visited解决不了环的问题。
• Floyd的k循环在最外层。这个顺序不能错。如果把k放在最内层，结果就不对了。为什么？因为k作为中间点，必须保证在更新i→j时，i→k和k→j的路径已经考虑了之前的中间点。
• 图不连通怎么办？Prim和Kruskal如果图不连通，返回-1或者一个特殊值。Dijkstra跑完后，dist中还有INF的顶点就是不可达的。