当前位置: 代码迷 >> 综合 >> 最小生成树Prim算法,Kruskal算法
  详细解决方案

最小生成树Prim算法,Kruskal算法

热度:35   发布时间:2024-01-16 20:15:04.0

Prim算法

/**  Prim求MST*  耗费矩阵cost[][],初始化为INF,标号从0开始,0 ~ n-1*  返回最小生成树的权值,返回-1表示原图不连通*/const int INF = 0x3f3f3f3f;
const int MAXN = 110;
bool vis[MAXN];
int lowc[MAXN];
int cost[MAXN][MAXN];//  修正cost(添加边)
void updata(int x, int y, int v)
{cost[x - 1][y - 1] = v;cost[y - 1][x - 1] = v;return ;
}int Prim(int cost[][MAXN], int n)   //  0 ~ n - 1
{int ans = 0;memset(vis, false, sizeof(vis));vis[0] = true;for (int i = 1; i < n; i++){lowc[i] = cost[0][i];}for (int i = 1; i < n; i++){int minc = INF;int p = -1;for (int j = 0; j < n; j++){if (!vis[j] && minc > lowc[j]){minc = lowc[j];p = j;}}if (minc == INF){return -1;  //  原图不连通}ans += minc;vis[p] = true;for (int j = 0; j < n; j++){if (!vis[j] && lowc[j] > cost[p][j]){lowc[j] = cost[p][j];}}}return ans;
}

Kruskal算法

/**  Kruskal算法求MST*  对边操作,并排序*  切记:初始化赋值问题(tol)*/const int MAXN = 110;   //  最大点数
const int MAXM = 10000; //  最大边数int F[MAXN];    //  并查集使用struct Edge
{int u;      //  起点int v;      //  终点int w;      //  权值
} edge[MAXM];   //  存储边的信息int tol;        //  边数,加边前赋值为0void addEdge(int u, int v, int w)
{edge[tol].u = u;edge[tol].v = v;edge[tol++].w = w;return ;
}bool cmp(Edge a, Edge b)
{//  排序函数,将边按照权值从小到大排序return a.w < b.w;
}int find(int x)
{if (F[x] == x){return x;}else{return F[x] = find(F[x]);}
}int Kruskal(int n)  //  传入点数,返回最小生成树的权值,如果不连通则返回-1
{for (int i = 0; i <= n; i++){F[i] = i;}sort(edge, edge + tol, cmp);int cnt = 0;    //  计算加入的边数int ans = 0;for (int i = 0; i < tol; i++){int u = edge[i].u;int v = edge[i].v;int w = edge[i].w;int tOne = find(u);int tTwo = find(v);if (tOne != tTwo){ans += w;F[tOne] = tTwo;cnt++;}if (cnt == n - 1){break;}}if (cnt < n - 1){return -1;  //  不连通}else{return ans;}
}

MST

/* *  Minimal Steiner Tree*  G(V, E), A是V的一个子集, 求至少包含A中所有点的最小子树. *  时间复杂度:O(N^3+N*2^A*(2^A+N))*  INIT: d[][]距离矩阵; id[]置为集合A中点的标号;*  CALL: steiner(int n, int a);*  给4个点对(a1,b1)...(a4,b4),*  求min(sigma(dist[ai][bi])),其中重复的路段只能算一次.*  这题要找出一个Steiner森林, 最后要对森林中树的个数进行枚举*/
#define typec int               //  type of cost
const typec inf = 0x3f3f3f3f;   //  max of cost
const typec V = 10010;
const typec A = 10;int vis[V], id[A];              //  id[]:       A中点的标号
typec d[V][V], dp[1 << A][V];   //  dp[i][v]:   点v到点集i的最短距离void steiner(int n, int a)
{int i, j, k, mx, mk = 0, top = (1 << a);for (k = 0; k < n; k++){for (i = 0; i < n; i++){for (j = 0; j < n; j++){if (d[i][j] > d[i][k] + d[k][j]){d[i][j] = d[i][k] + d[k][j];}}}}for (i = 0; i < a; i++){//  vertex: 0 ~ n-1for (j = 0; j < n; j++){dp[1 << i][j] = d[j][id[i]];}}for (i = 1; i < top; i++){if (0 == (i & (i - 1))){continue;}memset(vis, 0, sizeof(vis));for (k = 0; k < n; k++) //  init{for (dp[i][k] = inf, j = 1; j < i; j++){if ((i | j) == i && dp[i][k] > dp[j][k] + dp[i - j][k]){dp[i][k] = dp[j][k] + dp[i - j][k];}}}for (j = 0; mx = inf, j < n; j++){//  updatefor (k = 0; k < n; k++){if (dp[i][k] <= mx && 0 == vis[k]){mx = dp[i][mk = k];}}for (k = 0, vis[mk] = 1; k < n; k++){if (dp[i][mk] > dp[i][k] + d[k][mk]){dp[i][mk] = dp[i][k] + d[k][mk];}}}}return ;
}int main(int argc, const char * argv[])
{int n, a = 8;int b, z, i, j, k, x = 0, y;// TODO: read data;steiner(n, a);// enum to find the resultfor (i = 0, b = inf; z = 0, i < 256; b > z ? b = z : b, i++){for (j = 0; y = 0, j < 4; z += !!y * dp[y][x], j++){for (k = 0; k < 8; k += 2){if ((i >> k & 3) == j){y += 3 << k, x = id[k];}}}}// TODO: cout << b << endl;return 0;
}