首页 > 代码库 > 最小代价生成树
最小代价生成树
#include<iostream> using namespace std; const int Max = 100; int p[Max][Max]; const int maxCost = 99; int lowcost[Max]; int nearest[Max]; bool mark[Max]; void Prime(int k,int n) { memset(lowcost, 99, sizeof(lowcost)); memset(nearest, -1, sizeof(nearest)); memset(mark, false, sizeof(mark)); nearest[k] = k; lowcost[k] = 0; mark[k] = true; //k is the the point you have added the set for (int i = 0; i < n; i++) { //update lowcost and nearest for (int j = 0; j < n; j++) { if (p[k][j] != 0 && !mark[j] && lowcost[j] > p[k][j]) { lowcost[j] = p[k][j]; nearest[j] = k; } } //find the min lowcost int min = maxCost; for (int j = 0; j < n; j++) { if (!mark[j] && min > lowcost[j]) { min = lowcost[j]; k = j; } } mark[k] = true; } } int main() { freopen("sample_input.txt","r",stdin); int vertex, edge; cin >> edge >> vertex; int u, v, cost; for (int i = 0; i < vertex; i++) { cin >> u >> v >> cost; p[u][v] = cost; p[v][u] = cost; } Prime(0, edge); return 0; }
最小代价生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。