圖
-
實驗目的
熟悉圖的兩種常用的存儲結構，以及在這兩種存儲結構上的兩種遍歷圖的方法，即深
度優先遍歷和廣度優先遍歷。進一步掌握遞歸算法的設計方法。
關于各種典型著名的復雜算法，在上機實習方面不做基本要求。更適合于安排大型課
程設計。
二.需求分析
本程序演示用C++編寫,完成有向圖的創建,用Prim算法實現最小生成樹,實現邊的插入和刪除.
輸入值的范圍:創建圖時要求輸入的結點個數不大于MaxVertices的值.在插入邊時要求原圖不存在起點和終點之間邊,并且插入的邊不是矩陣對角線上的邊.輸入的數據類型為整形.
輸出形式:以鄰接矩陣的形式輸出圖的數據項.如果操作非法則給出錯誤信息.
測試數據
A創建5個頂點4條邊的圖:輸入頂點分別為1,2,3,4,5;1和2之間,2和3之間,3和4 之間,4和5之間的權值分別為10,20,30,40.得到圖:
輸出頂點的信息（整型）：
1 2 3 4 5
輸出鄰接矩陣 ：
1: 0 10 1000 1000 1000
2: 1000 0 20 1000 1000
3: 1000 1000 0 30 1000
4: 1000 1000 1000 0 40
5: 1000 1000 1000 1000 0
B頂點4和3之間插入一條權值為50邊得
輸出頂點的信息（整型）：
1 2 3 4 5
輸出鄰接矩陣 ：
1: 0 10 1000 1000 1000
2: 1000 0 20 1000 1000
3: 1000 1000 0 30 1000
4: 1000 1000 50 0 40
5: 1000 1000 1000 1000 0
C刪除頂點4和3之間的邊得
輸出頂點的信息（整型）：
1 2 3 4 5
輸出鄰接矩陣 ：
1: 0 10 1000 1000 1000
2: 1000 0 20 1000 1000
3: 1000 1000 0 30 1000
4: 1000 1000 1000 0 40
5: 1000 1000 1000 1000 0
三.設計概要
(1)為了實現上述程序的功能,需要定義圖的抽象數據類型:
ADT Graph is{
數據對象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
基本操作:
CreatG()
操作結果:創建有向圖
InsertE()
初始條件:有向圖已經存在
操作結果:插入一條邊
DeleteE ()
初始條件: 有向圖已經存在
操作結果:刪除一條邊
}END ADT BiTree
(2) 本程序包含一個類和一個結構體類型
A無向圖類AdjMWGraph有7個函數
1主函數 main()
2.構造函數 AdjMWGraph()
3. 創建圖函數 CreatG(int n,int e)
4. 插入邊函數 InsertE()
5. 刪除邊函數 DeleteE()
6. 求最小生成樹Prim算法函數 Prim()
B結構體類型MinSpanTree
(3)本程序的兩個文件
1.頭文件 Graph.h
2.源文件 Graph.cpp
(4)函數之間的關系
四.詳細設計
1
//Graph.h
2#include "iostream"
3#include <iomanip>
4#include <stdlib.h>
5using namespace std;
6const int MaxVertices=10;
7const int MaxWeight=1000;
8struct MinSpanTree //帶權邊的三個參數
9
{
10
int begin,end; //邊的起點與終點
11 int length; //邊的權值
12
};
13
14class AdjMWGraph
15{
16private:
17 int Vertices[20]; //頂點信息的數組
18 int Edge[MaxVertices][MaxVertices]; //邊的權信息的矩陣
19 int numE; //當前的邊數
20 int numV; //當前的頂點數
21public:
22 AdjMWGraph(); //構造函數
23 void CreatG(int n,int e); //創建圖函數
24 void PrintOut(); //打印圖中數據項函數
25 void Prim() ; //求最小生成樹方法(Prim算法)
26 void InsertE(); //插入邊函數
27 void DeleteE(); //刪除邊函數
28};
29//Graph.cpp
30#include "Graph.h"
31
32//初始化矩陣
33AdjMWGraph::AdjMWGraph() //構造函數
34{
35 //初始化矩陣為
36 for ( int i = 0; i < MaxVertices; i++ ) //行
37 for ( int j = 0; j < MaxVertices; j++ ) //列
38
{
39 if( i==j )
40 Edge[i][j] = 0; //對角線置零
41 else
42 Edge[i][j] = MaxWeight; //無邊時權值置這無窮大
43
}
44 numE = 0; //當前邊個數初始為
45 numV = 0; //當前的頂點個數為
46}
47
48//創建圖
49void AdjMWGraph::CreatG(int n,int e)
50{
51 int vi,vj,w;
52 numE = e;
53 numV = n;
54 cout<<"\n 輸入頂點的信息（整型）：" ;
55
56 //頂點賦值
57 for (int i = 0; i < numV; i++ )
58 {
59 cout<<"\n "<<i+1<<": ";
60 cin >> Vertices[i];
61
62 }
63
64 //邊賦權值
65 for ( int i = 0; i < numE;)
66 {
67 cout<<"\n 輸入邊的信息（vi,vj,W）：";
68 cin >> vi >> vj >> w;
69
70//判斷起點和終點是否存在,是否是對角線上的點并且邊是否存在
71 if ((vi != vj )
72 && (vi>0 && vi<=numV)
73 && (vj>0 && vj<=numV)
74 && (Edge[vi-1][vj-1] == MaxWeight))
75 {
76 Edge[vi-1][vj-1] = w; //更改對應的行和列的權值
77 i++;
78 }
79 else
80 {
81 cout << "\t插入位置錯誤或邊已經存在!\n\t請正確輸入." <<endl;
82 }
83 }
84 }
85
86//打印圖中數據項
87void AdjMWGraph::PrintOut()
88{
89 cout << "\n 輸出頂點的信息（整型）：\n";
90 for ( int i = 0; i < numV; i++ )
91 cout << "\t" << Vertices[i] ;
92 cout << "\n 輸出鄰接矩陣：" <<endl;
93 for ( int i = 0; i < numV; i++ )
94 {
95 cout << "\n "<< i+1 <<": ";
96 for ( int j = 0; j < numV ; j++ )
97 cout << "\t" << Edge[i][j] ;
98 cout << endl;
99 }
100 }
101
102//Prim普里姆算法求最小生成樹
103void AdjMWGraph::Prim ()
104{
105 int n = numV,m,v; //頂點總數
106 MinSpanTree e, mintree[MaxVertices]; // mintree 生成樹數組
107
108 for (int j = 1; j < n; j++) //初始化tree[n-1]
109 {
110 mintree[j-1].begin = 1; //頂點并入U
111 mintree[j-1].end = j+1;
112 mintree[j-1].length = Edge[0][j]; // G.Edge[][]是連通網的帶權鄰接矩陣
113 }
114
115 for (int k = 0; k < n-1; k++) // 求第k+1條邊
116 {
117 int min = MaxWeight;
118
119 for (int j = k; j < n-1; j++)
120 if (mintree[j].length < min ) //求鄰接的最小的邊
121 {
122 min = mintree[j].length;
123 m = j;
124 } //for j
125
126 //交換方法置下個鄰接點為終點
127 e = mintree[m];
128 mintree[m] = mintree[k];
129 mintree[k] = e;
130 v = mintree[k].end; //V∈U
131
132 for (int j = k+1; j < n-1; j++) //在新的頂點v并入U之后更新tree[n-1]
133 {
134 int d = Edge[v-1][mintree[j].end-1];
135 if (d < mintree[j].length) //循環找到與當前點相鄰的最小權值的邊
136 {
137 mintree[j].length = d;
138 mintree[j].begin = v; //置當前點為起點
139 }
140 }// for k
141 }
142 for (int j = 0;j < n-1; j++)
143 cout<<"\n"<<"起點："<< mintree[j].begin <<" 終點："<<
144 mintree[j].end<<" 權值："<<mintree[j].length;
145 cout << endl;
146}
147
148//插入一條的算法
149void AdjMWGraph::InsertE()
150{
151 int i,j,w;
152 cout << "\n 請輸入插入邊的起點,終點和權值(vi,vj,W):";
153 cin >> i >> j >> w;
154 //判斷起點各終點是否存在并且不是對角線上的點
155 if ( ( i != j ) && (i>0 && i<=numV) && (j>0 && j<=numV))
156 {
157 if ( (Edge[i-1][j-1] != 0) && (Edge[i-1][j-1] == MaxWeight) )
158 {
159 Edge[i-1][j-1] = w; //更改對應的行和列的權值
160 }
161 else
162 {
163 cout << "\t邊已經存在!" << endl;
164 //exit (0);
165 }
166 }
167 else
168 {
169 cout << "\t插入位置錯誤!" <<endl;
170 //exit (0);
171 }
172
173}
174
175//刪除一條邊的算法
176void AdjMWGraph::DeleteE()
177{
178 int i,j;
179 cout << "\n 請輸入要刪除的邊的起點和終點(vi,vj):";
180 cin >> i >> j;
181 if ((i>0 && i<=numV) && (j>0 && j<=numV)) //判斷起點各終點是否存在
182 {
183//判斷是否是對角線上的點,判斷是否是邊已經存在
184 if(( i != j ) && (Edge[i-1][j-1] != MaxWeight) )
185 {
186 Edge[i-1][j-1] = MaxWeight; //對應的行和列權值置零
187
188 }
189 else
190 {
191 cout << "\t刪除的邊不存在!" << endl;
192 //exit (0);
193
194 }
195 }
196 else
197 {
198 cout << "\t刪除位置錯誤!" <<endl;
199 //exit (0);
200 }
201
202}
203
204int main(int argc, char* argv[])
205{
206 AdjMWGraph G ;
207 int n,e;
208 int k;
209
210 do
211 {
212 cout << "\n\t 1.創建圖" <<endl;
213 cout << "\n\t 2.插入一條邊" <<endl;
214 cout << "\n\t 3.刪除一條邊" <<endl;
215 cout << "\n\t 4.退出" <<endl;
216 cout << "\n\t ==========================" << endl;
217 cout<< "\n\t請輸入您的選擇(1,2,3,4):";
218 cin >> k;
219
220 switch(k)
221 {
222
223 case 1:
224 {
225 cout << "\n 請輸入圖的總頂點數和總邊數（n,e=?）：";
226 cin >> n >> e ;
227 G.CreatG(n,e);
228 G.PrintOut();
229 cout << "最小生成樹如下";
230 cout << "共有" << n-1 << "條邊" ;
231 G.Prim();
232 }break;
233
234 case 2:
235 {
236 G.InsertE();
237 G.PrintOut();
238 G.Prim();
239
240 }break;
241
242 case 3:
243 {
244 G.DeleteE();
245 G.PrintOut();
246 G.Prim();
247
248 }break;
249 case 4:
250 exit (0);
251 }
252 }while( k >0 && k <5 );
253 return 0;
254}
255
五.心得:
這次實驗我把無向圖改成有向圖后,對實驗中給出的生成最小生成樹的Prim算法感到費解這里只能說說在實現插入和刪除時的心得.在創建圖時我在程序中加入判斷語句,因為在給邊權時如果頂點不存在會造成鎖死,嚴重影響調試.在創建和插入中主要判斷的是:1,頂點是否越界.2邊是否已經存在.3插入位置是否是矩陣的對角線.在刪除中判斷1,頂點是否越界.2邊是否已經存在.對于Prim算法的求最小生成樹的思想能夠理解,但對于算法的實現不甚理解.希望老師在下次實驗時講解.
六.使用說明
程序名為No5.exe運行環境為DOS,執行后顯示:
在" 請輸入您的選擇(1,2,3,4):"后輸入數字選擇執行的功能.
測試結果:
- 選擇1.輸入如圖:
得
- 選擇2操作如圖:
再次操作
再次操作
3)選擇3操作如圖
再次操作
再次操作
4) 選擇4或輸入非"1,2,3"的數字
七.調試過程
本程序主要對插入邊操作功能進行調試..
- 將光標移置Graph.cpp文件的void AdjMWGraph::InsertE()的第一條語句處Ctrl+F10開始單步調試
- 選擇1.后創建圖
再選擇2.
-
這時Debugger仍停留在void AdjMWGraph::InsertE()的第一條語句上.在中輸入numV, I, j ,i!=j ,Edge[i-1][j-1]進行觀察.F10單步至cin >> i >> j >> w;語句.然后在DOS窗口輸入4,3,55回車.
這時Debugger仍停留在if ( ( i != j ) && (i>0 && i<=numV) && (j>0 && j<=numV))處.可以在監視1窗口中看到 i != j的值為true,即可以步入if()語句.
-
在監視窗口1中輸入: (Edge[i-1][j-1] == MaxWeight), (Edge[i-1][j-1] != 0)進行觀察,F10單步調試,這時Debugger停留在if ( (Edge[i-1][j-1] != 0) && (Edge[i-1][j-1] == MaxWeight) )語句處,同時在監視窗口1中可以看到(Edge[i-1][j-1] == MaxWeight), (Edge[i-1][j-1] != 0)都為真,即可以步入if()語句中.F10后可以看到Edge[i-1][j-1]值已經變為55
-
F10單步調試到結束可以在DOS窗口中看到矩陣中相應的位置已經改變
Shift+F5退出調試,完成調試演示.