《算法设计与分析》课程实验报告
专 业：计算机科学与技术
班 级：
学 号：
姓 名：
日期：2014 年 10月18 日
第二篇：算法实验报告一
12级网络工程 严坤 22xxxxxxxxxxxx 作业一：利用贪心算法解决最小生成树问题
问题描述： 在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得 w(T) 最小，则此 T 为 G 的最小生成树，以下采用prim算法解决；
代码设计：
#include "stdafx.h"
#include<stdio.h>
#include<iostream>
#define maxint 6
#define max 100
using namespace std;
void prim(int n ,int c[6][6]){
int lowcost[maxint]; int closest[maxint]; bool s[maxint]; s[1] = true; for(int i = 1; i < n; i++){ lowcost[i] closest[i] s[i] = false; = c[0][i]; = 0;
12级网络工程 严坤 22xxxxxxxxxxxx
} } for(i = 1; i < n; i++){ } system("pause"); int min = max; int j = 0; for(int k = 0; k < n; k++) if((lowcost[k] < min) && (!s[k])){ } cout << closest[j] + 1 << ' ' << j + 1 << endl; s[j] = true; for(k = 1; k < n; k++) min = lowcost[k]; j = k; if((c[j][k] < lowcost[k]) && (!s[k])){ } lowcost[k] = c[j][k]; closest[k] = j;
void main(){
int c[6][6]={{0,6,1,5,max,max},{6,0,5,max,3,max},{1,5,0,5,6,4},{5,max,5,0,max,2},{max,3,6,m
12级网络工程 严坤 22xxxxxxxxxxxx ax,0,6},{max,max,4,2,6,0}};
}
prim(6,c);
运行结果结果：
