實驗名稱：最小代價生成樹
實驗章節：算法設計與分析第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 }
程序問題
7.(選作)若是使用克魯斯卡爾算法，課本第109頁圖6-10生成的最小子圖應該是什麼？
8.(選作)若是使用克魯斯卡爾算法，（圖1）生成的最小子圖應該是什麼？
