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

一、实验目的

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; }