首页 > 代码库 > 实验六 最小代价生成树
实验六 最小代价生成树
实验名称：最小代价生成树
实验章节：算法设计与分析第6章
实验目的： 掌握贪心算法解决问题的思想和一般过程，
学会使用普里姆算法解决实际问题。
提交形式： 所有作业的原程序和可执行程序（即cpp文件和exe文件）
纸质实验报告（格式和内容请参阅末页）
实验内容
完善下列程序，并回答问题。
1 #include<iostream.h> 2 3 #define G_NODE_NUM 6 //结点个数 4 5 #define INFTY 65535 6 7 template<class T> 8 9 struct ENode 10 11 {//带权图的边结点 12 13 int adjVex; 14 15 T w; 16 17 ENode* nextArc; 18 19 }; 20 21 template <class T> 22 23 class Graph 24 25 { 26 27 public: 28 29 Graph (int mSize){ 30 31 n = mSize; 32 33 a = new ENode<T> *[mSize]; 34 35 for(int i = 0; i< n ;i++){ 36 37 a[i] = NULL; 38 39 } 40 41 } 42 43 void Prim(int s); 44 45 void putin(T X[G_NODE_NUM][G_NODE_NUM]); 46 47 void putout(); 48 49 protected: 50 51 void Prim(int k, int* nearest, T* lowcost); 52 53 ENode<T>** a; 54 55 int n; 56 57 }; 58 59 60 61 template<class T> 62 63 void Graph<T>::putin(T X[G_NODE_NUM][G_NODE_NUM]){ 64 65 ENode<T> *e; 66 67 for(int i = 0; i < n; i++){ 68 69 for(int j = 0; j < n; j++){ 70 71 if(X[i][j]>0){ 72 73 e = new ENode<T>(); 74 75 e->adjVex = j; 76 77 e->w = X[i][j]; 78 79 e->nextArc = a[i]; 80 81 a[i] = e; 82 83 } 84 85 } 86 87 } 88 89 } 90 91 template<class T> 92 93 void Graph<T>::putout(){ 94 95 ENode<T> *e; 96 97 cout<<"---图输出---"<<endl; 98 99 for(int i=0; i<n; i++){100 101 e = a[i];102 103 cout<<endl<<"第"<<i<<"个节点：";104 105 while(e!=NULL){106 107 cout<<" "<<e->adjVex<<"("<<e->w<<")";108 109 e=e->nextArc;110 111 }112 113 }114 115 cout<<endl;116 117 }118 119 120 121 template<class T>122 123 void Graph<T>::Prim(int s)124 125 { 126 127 学生书写部分128 129 };130 131 132 133 template<class T>134 135 void Graph<T>::Prim(int k, int* nearest, T* lowcost)136 137 {138 139 学生书写部分140 141 }142 143 144 145 void main(){146 147 Graph<int> *G;148 149 int data[G_NODE_NUM][G_NODE_NUM]={ {0,6,1,5,0,0},150 151 {6,0,5,0,3,0},152 153 {1,5,0,5,6,4},154 155 {5,0,5,0,0,2},156 157 {0,3,6,0,0,6},158 159 {0,0,4,2,6,0}};160 161 int n = G_NODE_NUM;162 163 G = new Graph<int>(n);164 165 G->putin(data);166 167 G->putout();168 169 G->Prim(0);170 171 }
程序问题
- 分析算法，说明算法中涉及到的变量k、nearest、lawcast、mark，分别表示的语义是什么。
- 画出Prim算法的流程图。
- 运行课本第109页图6-10的普里姆算法，生成的子树是什么? （程序自带输入部分）
- 在程序的适当位置，增加“cout<<"第"<<k<<"个节点加入生成树\n";”语句，输出加入节点的次序。
- 试着推理，或者在程序中增加输出语句，说明从第1个节点开始，每一次循环三元组<nearest[i], i, lowcost[i]>的变化。
- 若是8个节点的图，如下所示，设计相应的输入邻接矩阵，通过普里姆算法得出的最小生成子树是什么？
7.(选作)若是使用克鲁斯卡尔算法，课本第109页图6-10生成的最小子图应该是什么？
8.(选作)若是使用克鲁斯卡尔算法，（图1）生成的最小子图应该是什么？
实验六 最小代价生成树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。