实验六 16 王娜

宁夏师范学院数学与计算机科学学院

《算法设计与分析》实验报告

实验序号： 学 号 实验地321 点 16 姓 名 指导教师 马 涛 时间 王娜

实验项目名称：贪心算法应用 专业、班 10级计本班 2013-5-16 一、实验目的与要求 (1)、熟悉多机调度问题的算法； (2)、体会贪心算法最优子结构性质； (3)、能灵活运用贪心算法解决实际问题； (4)、熟悉贪心算法的基本原理与适用范围； 二、实验设备（环境）及要求 1、环境要求： 硬件：PC（PII以上，128M以上内存）、因特网接入； 软件：Windows XP操作系统、Office2003、多媒体播放软件。 三、实验内容与步骤 任选一种贪心算法（Prim或Kruskal），求解最小生成树。对算法进行描述和复杂性分析。 编程实现，并给出测试实例 #include #include #define M 20 #define MAX 20 typedef struct { int begin; int end; int weight; }edge; typedef struct { int adj; int weight; }AdjMatrix[MAX][MAX]; typedef struct { AdjMatrix arc; int vexnum, arcnum; }MGraph; void CreatGraph(MGraph *);//函数申明 void sort(edge* ,MGraph *); void MiniSpanTree(MGraph *); int Find(int *, int ); void Swapn(edge *, int, int); void CreatGraph(MGraph *G)//构件图 { int i, j,n, m; printf(\请输入边数和顶点数:\scanf(\ for (i = 1; i <= G->vexnum; i++)//初始化图 { for ( j = 1; j <= G->vexnum; j++) { G->arc[i][j].adj = G->arc[j][i].adj = 0; } } for ( i = 1; i <= G->arcnum; i++)//输入边和权值 { printf(\请输入有边的2个顶点\scanf(\while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) { printf(\输入的数字不符合要求 请重新输入:\scanf(\} G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar(); printf(\请输入%d与%d之间的权值:\scanf(\} printf(\邻接矩阵为:\\n\for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { printf(\} printf(\} } void sort(edge edges[],MGraph *G)//对权值进行排序 { int i, j; for ( i = 1; i < G->arcnum; i++) { for ( j = i + 1; j <= G->arcnum; j++) { if (edges[i].weight > edges[j].weight) { Swapn(edges, i, j); } } } printf(\权排序之后的为:\\n\for (i = 1; i < G->arcnum; i++) { printf(\ %d\\n\} } void Swapn(edge *edges,int i, int j)//交换权值 以及头和尾 { int temp; temp = edges[i].begin; edges[i].begin = edges[j].begin; edges[j].begin = temp; temp = edges[i].end; edges[i].end = edges[j].end; edges[j].end = temp; temp = edges[i].weight; edges[i].weight = edges[j].weight; edges[j].weight = temp; } void MiniSpanTree(MGraph *G)//生成最小生成树 { int i, j, n, m; int k = 1; int parent[M]; edge edges[M]; for ( i = 1; i < G->vexnum; i++) { for (j = i + 1; j <= G->vexnum; j++) { if (G->arc[i][j].adj == 1) { edges[k].begin = i; edges[k].end = j; edges[k].weight = G->arc[i][j].weight; k++; } } } sort(edges, G); for (i = 1; i <= G->arcnum; i++) { parent[i] = 0; } printf(\最小生成树为:\\n\for (i = 1; i <= G->arcnum; i++)//核心部分 { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) { parent[n] = m; printf(\ %d\\n\} } } int Find(int *parent, int f)//找尾 { while ( parent[f] > 0) { f = parent[f]; } return f; } int main(void)//主函数 { MGraph *G; G = (MGraph*)malloc(sizeof(MGraph)); if (G == NULL) { printf(\exit(1); } CreatGraph(G); MiniSpanTree(G); system(\return 0; } 四、实验结果与数据处理 五、分析与讨论 六、教师评语 。 成绩 签名： 日期： 年 月 日