实验6 最小代价生成树

实验六最小代价生成树

实验名称：最小代价生成树

实验章节：算法设计与分析第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个节点的图，如下所示，设计相应的输入邻接矩阵，通过普里姆算法得出的最小生成子树是什么？

实验6 最小代价生成树

7.(选作)若是使用克鲁斯卡尔算法，课本第109页图6-10生成的最小子图应该是什么？

8.(选作)若是使用克鲁斯卡尔算法，（图1）生成的最小子图应该是什么？

相关推荐