Kruskal 算法 先将途中所有边的权值进行从小到大排序，按照顺序依次将边的两点加入最小生成树的子图中，若加入后产生圈，则舍弃这条边，直到所有点在图中为止
1).记Graph中有v个顶点，e个边 2).新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边 3).将原图Graph中所有e个边按权值从小到大排序 4).循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中 如果 这条边连接的两个节点于图Graphnew中不在同一个连通分量中就添加这条边到图Graphnew中 #include<iostream> #include<vector> #include<algorithm> #include<cstdlib> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<string> #include<cstring> #include<map> #include<set> using namespace std; #define N 100 #define INF 0x3f3f3f3f /*****************************************************/ struct node{ int u, v, cost; }; bool cmp(node a, node b){ return a.cost < b.cost; } node s[N]; int par[N]; int ranks[N]; int V, E; void init_union_find(int v); int find(int x); void unite(int a, int b); bool same(int a, int b); int Kruskal(); int main() { cin >> V >> E; //输入点、边数 init_union_find(V); //初始化并查集 for (int i = 0; i < E; i++){ cin >> s[i].u >> s[i].v >> s[i].cost; } cout<<Kruskal(); } int Kruskal(){ sort(s, s + E, cmp); //对边的权值进行排序 int res = 0; for (int i = 0; i < E; i++){ node e = s[i]; if (!same(e.u, e.v)){ //判断两点是否在一个通路 unite(e.u, e.v); //合并两个点 res += e.cost; } } return res; } void init_union_find(int v){ for (int i = 0; i <= V; i++) { par[i] = i; ranks[i] = 1; } } void unite(int a, int b){ a = find(a); b = find(b); if (a==b)return; if (ranks[a] < ranks[b]){ par[a] = b; } else{ if (ranks[a] == ranks[b]) { ranks[a]++; } par[b] = a; } } int find(int x){ if (par[x] == x)return x; return par[x] = find(par[x]); } bool same(int a, int b){ if (par[a] == par[b])return true; return false; }Prim算法 先建立一个最小生成树的子图。任取一点s最为子图的初始点，标记。然后再子图之外寻找与子图中所有点距离最小的点，将这个点加入子图的集合，并从这个点进行扩展求出相邻点到子图的最短距离
#define N 500+10 #define INF 0x3f3f3f3f #define mem(arr,num) memset(arr,num,sizeof(arr)) /**********************************************************/ int minCost[N]; //某一点到子图的最短距离 int cost[N][N]; int V, E; bool used[N]; int Prim(){ mem(used, 0); mem(minCost, 0x3f); int res = 0; minCost[1] = 0; while (1){ int v = -1; for (int i = 1; i <= V; i++){ if (!used[i] && (v == -1 || minCost[i] < minCost[v])) v = i; //找到到子图权值最小的点 } if (v == -1)break; used[v] = true; res += minCost[v]; for (int i = 1; i <= V; i++){ minCost[i] = min(minCost[i], cost[v][i]); //求出该点周围的点距离子图权值的最小值 } } return res; }