图---图的应用（最小生成树）

图的应用最小生成树「Prim Kruskal」概念 原理 完整 C 代码 逐行解析考试直接背前置知识点最小生成树 (MST)含图全部 n个顶点、仅 n−1条边、权值和最小、无环连通子图适用连通无向带权图两大算法Prim点贪心稠密图、邻接矩阵Kruskal边贪心稀疏图配合并查集判环一、Prim 算法朴素版・邻接矩阵核心思想维护数组 lowcost[]记录「生成树集合」到每个顶点的最短边权每次选lowcost 最小且未加入树的顶点入树加入后更新剩余点的 lowcost循环 n−1次得到 MST完整代码 详解#include stdio.h #include string.h #define INF 0x3f3f3f3f #define MAXN 105 // 邻接矩阵存图 int G[MAXN][MAXN]; // lowcost[i]树集合到i的最短边 // vis[i]顶点i是否已加入生成树 int lowcost[MAXN], vis[MAXN]; int n; // 顶点数 // Prim起点为0返回最小生成树权值和 int Prim(int start) { int sum 0; // 1.初始化 memset(vis, 0, sizeof(vis)); for(int i 0; i n; i) lowcost[i] G[start][i]; vis[start] 1; // 起点加入树 // 选 n-1 条边 for(int cnt 1; cnt n - 1; cnt) { // 2.找距离树最近的点 int min INF, u; for(int i 0; i n; i) { if(!vis[i] lowcost[i] min) { min lowcost[i]; u i; } } // 3.加入生成树累加权值 vis[u] 1; sum min; // 4.更新lowcost新点u到其他点的更短边 for(int v 0; v n; v) { if(!vis[v] G[u][v] lowcost[v]) lowcost[v] G[u][v]; } } return sum; } int main() { int m; // m条边 scanf(%d%d, n, m); // 矩阵初始化为无穷 for(int i 0; i n; i) for(int j 0; j n; j) G[i][j] INF; // 自身到自身为0 for(int i 0; i n; i) G[i][i] 0; // 建图 无向图 for(int i 0; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); G[u][v] w; G[v][u] w; } int mst_sum Prim(0); printf(最小生成树总权值%d\n, mst_sum); return 0; }复杂度 适用时间O(n 2 )适合稠密图二、Kruskal 算法并查集 边集数组核心思想把所有边按权值升序排序依次选最短边用并查集判断两点是否连通不连通选这条边合并集合、累加权选够 n−1条边停止完整代码 详解#include stdio.h #include stdlib.h #define MAXE 1005 // 边结构体 typedef struct{ int u, v, w; }Edge; Edge edge[MAXE]; int parent[MAXE]; // 并查集父数组 int n, m; // 并查集-查找 路径压缩 int find(int x) { if(parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } // 并查集-合并 void unite(int x, int y) { x find(x); y find(y); if(x ! y) parent[y] x; } // 边按权值升序排序 回调函数 int cmp(const void *a, const void *b) { return ((Edge*)a)-w - ((Edge*)b)-w; } // Kruskal int Kruskal() { int sum 0, cnt 0; // 1.初始化并查集 每个点自成集合 for(int i 0; i n; i) parent[i] i; // 2.边从小到大排序 qsort(edge, m, sizeof(Edge), cmp); // 3.遍历所有边 for(int i 0; i m; i) { int u edge[i].u; int v edge[i).v; int w edge[i].w; // 不在同一集合→选这条边无环 if(find(u) ! find(v)) { unite(u, v); sum w; cnt; if(cnt n - 1) break; // 凑够n-1条边 } } return sum; } int main() { scanf(%d%d, n, m); for(int i 0; i m; i) { scanf(%d%d%d, edge[i].u, edge[i].v, edge[i].w); } int mst_sum Kruskal(); printf(最小生成树总权值%d\n, mst_sum); return 0; }复杂度 适用时间O(eloge)主要消耗在排序适合稀疏图