最小生成树问题中怎样回到初始位置（最小生成树问题建模）

最小生成树问题中怎样回到初始位置，最小生成树问题建模相信很多小伙伴还不知道,现在让我们一起来看看吧！

1、有Prim算法和Kruskal算法：（贪心）。

2、个人认为前者简洁。

3、代码如下：----------------------prim-------------------------------#include #include int mat[55][55],used[55],min[55];int p;int prim(){int i,j,k,q,ret = 0;for(i = 1;i <= p;i++)min[i] = 1000000000,used[i] = 0;min[1] = 0;for(i = 1;i <= p;i++){k = -1;for(j = 1;j <= p;j++)if(!used[j] && (k == -1 || min[j] < min[k]))k = j;used[k] = 1;ret += min[k];for(j = 1;j <= p;j++)if(!used[j] && mat[k][j] && mat[k][j] < min[j])min[j] = mat[k][j];}return ret;}int main(){int i,j,n,r,a,b,c;while(scanf("%d%d",&p,&r) != EOF && p != 0){memset(mat,0,sizeof(mat));for(i = 0;i < r;i++){scanf("%d%d%d",&a,&b,&c);if(!mat[a][b] || mat[a][b] > c)mat[a][b] = mat[b][a] = c;}printf("%d",prim());}return 0;}----------------------Kruskal--------------------------#include #include #include #include #include using namespace std; #define MAX 1000 int father[MAX], son[MAX]; int v, l; typedef struct Kruskal //存储边的信息 { int a; int b; int value; }; bool cmp(const Kruskal & a, const Kruskal & b) { return a.value < b.value; } int unionsearch(int x) //查找根结点+路径压缩 { return x == father[x] ? x : unionsearch(father[x]); } bool join(int x, int y) //合并 { int root1, root2; root1 = unionsearch(x); root2 = unionsearch(y); if(root1 == root2) //为环 return false; else if(son[root1] >= son[root2]) { father[root2] = root1; son[root1] += son[root2]; } else { father[root1] = root2; son[root2] += son[root1]; } return true; } int main() { int ncase, ltotal, sum, flag; Kruskal edge[MAX]; scanf("%d", &ncase); while(ncase--) { scanf("%d%d", &v, &l); ltotal = 0, sum = 0, flag = 0; for(int i = 1; i <= v; ++i) //初始化 { father[i] = i; son[i] = 1; } for(int i = 1; i <= l ; ++i) { scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].value); } sort(edge + 1, edge + 1 + l, cmp); //按权值由小到大排序 for(int i = 1; i <= l; ++i) { if(join(edge[i].a, edge[i].b)) { ltotal++; //边数加1 sum += edge[i].value; //记录权值之和 cout<"<

本文就为大家分享到这里，希望小伙伴们会喜欢。