实验九 最小生成树实验报告.docVIP

一、实验目的 1．使学生熟悉最小生成树的意义和相应算法 2．掌握带权图的存储结构 二、实验环境 1、硬件：每个学生需配备计算机一台 2、软件： windows操作系统 + Turbo C 三、实验要求 1、能够独立完成带权图的存储和最小生成树的生成 四、代码 #include stdio.h #include stdlib.h #define MAX 100 #define MAXCOST 0x7fffffff int graph_hcy[MAX][MAX]; int Prim_hcy(int graph_hcy[][MAX], int n) { /* lowcost_hcy[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */ int lowcost_hcy[MAX]; /* mst_hcy[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */ int mst_hcy[MAX]; int i, j, min, minid, sum = 0; /* 默认选择1号节点加入生成树，从2号节点开始初始化 */ for (i = 2; i = n; i++) { /* 最短距离初始化为其他节点到1号节点的距离 */ lowcost_hcy[i] = graph_hcy[1][i]; /* 标记所有节点的起点皆为默认的1号节点 */ mst_hcy[i] = 1; } /* 标记1号节点加入生成树 */ mst_hcy[1] = 0; /* n个节点至少需要n-1条边构成最小生成树 */ for (i = 2; i = n; i++) { min = MAXCOST; minid = 0; /* 找满足条件的最小权值边的节点minid */ for (j = 2; j = n; j++) { /* 边权值较小且不在生成树中 */ if (lowcost_hcy[j] min lowcost_hcy[j] != 0) { min = lowcost_hcy[j]; minid = j; } } /* 输出生成树边的信息:起点，终点，权值 */ printf(%c - %c : %d\n, mst_hcy[minid] + A - 1, minid + A - 1, min); /* 累加权值 */ sum += min; /* 标记节点minid加入生成树 */ lowcost_hcy[minid] = 0; /* 更新当前节点minid到其他节点的权值 */ for (j = 2; j = n; j++) { /* 发现更小的权值 */ if (graph_hcy[minid][j] lowcost_hcy[j]) { /* 更新权值信息 */ lowcost_hcy[j] = graph_hcy[minid][j]; /* 更新最小权值边的起点 */ mst_hcy[j] = minid; } } } /* 返回最小权值和 */ return sum; } int main() { int i, j, k, m, n; int x, y, cost; char chx, chy; /* 读取节点和边的数目 */ scanf(%d%d, m, n); getchar(); /* 初始化图，所有节点间距离为无穷大 */ for (i = 1; i = m; i++) { for (j = 1; j = m; j++) {graph_hcy[i][j] = MAXCOST; } } /* 读取边信息 */ for (k = 0; k n; k++) { scanf(%c %c %d, chx, chy, cost); getchar(); i = chx - A + 1; j = chy - A + 1; graph_hcy[i][j] = cost; graph_hcy[j][i] = cost; } /* 求解最小生成树 */ cost = Prim_hcy(graph_hcy, m); /* 输出最小权值和 */ printf(Total:%d\n, cost); //system(pause); return 0; }