首页 > 代码库 > 普里姆算法求最小生成树
普里姆算法求最小生成树
#include "iostream" using namespace std; const int num = 9; //节点个数 #define Infinity 65535; //本例中以节点0作为生成树的起始节点 void MinSpanTree_Prime(int graphic[num][num]){ int lowcost[num]; //记录从节点num到生成树的最短距离,如果为0则表示该节点已在生成树中 int adjvex[num]; //记录相关节点,如:adjvex[1] = 5表示最小生成树中节点1和5有路径相连 int sum = 0; // 记录最小生成树边权重之和 memset(adjvex, 0, sizeof(adjvex)); //选取0节点作为生成树的起点 for (int i = 0; i < num; i++) lowcost[i] = graphic[0][i]; for (int i = 1; i < num; i++){ int min = Infinity; int index; for (int j = 1; j < num; j++){ if (lowcost[j] != 0 && lowcost[j] < min){ index = j; min = lowcost[j]; } } sum += min; lowcost[index] = 0; //将当前节点放入生成树中 cout << adjvex[index] << " -> " << index << endl; //修正其他节点到生成树的最短距离 for (int j = 1; j < num; j++){ if (lowcost[j] != 0 && graphic[index][j] < lowcost[j]){ lowcost[j] = graphic[index][j]; adjvex[j] = index; } } } cout << "sum = " << sum << endl; } int main(){ int graphic[num][num]; for (int i = 0; i < num; i++) for (int j = 0; j < num; j++){ if (i == j) graphic[i][j] = 0; else graphic[i][j] = Infinity; } graphic[0][1] = 1; graphic[0][2] = 5; graphic[1][0] = 1; graphic[1][2] = 3; graphic[1][3] = 7; graphic[1][4] = 5; graphic[2][0] = 5; graphic[2][1] = 3; graphic[2][4] = 1; graphic[2][5] = 7; graphic[3][1] = 7; graphic[3][4] = 2; graphic[3][6] = 3; graphic[4][1] = 5; graphic[4][2] = 1; graphic[4][3] = 2; graphic[4][5] = 3; graphic[4][6] = 6; graphic[4][7] = 9; graphic[5][2] = 7; graphic[5][4] = 3; graphic[5][7] = 5; graphic[6][3] = 3; graphic[6][4] = 6; graphic[6][7] = 2; graphic[6][8] = 7; graphic[7][4] = 9; graphic[7][5] = 5; graphic[7][6] = 2; graphic[7][8] = 4; graphic[8][6] = 7; graphic[8][7] = 4; MinSpanTree_Prime(graphic); return 0; }
普里姆算法求最小生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。