C++數據結構之圖——鄰接矩陣實現

一、圖的鄰接矩陣實現

1.實現了以頂點數組、鄰接矩陣為存儲結構的圖；

2.實現了圖的創建（包含有向/無向圖、有向/無向網）、頂點/邊的增刪操作、深度/廣度優先遍歷的算法；

3.採用頂點對象列表、邊（弧）對象列表的方式，對圖的創建進行初始化；引用 "ObjArrayList.h"頭文件，頭文件可參看之前博文“數據結構之順序列表（支持對象元素）”代碼；

4.採用將頂點數組空位的下標索引入隊列的方式，解決頂點在數組（靜態）中因增刪操作造成的不連續存儲的問題；引用 “LinkQueue.h”頭文件，頭文件可參看之前博文“數據結構之隊列（循環隊列、鏈隊列的類模板實現）”代碼；

5.深度優先遍歷採用遞歸算法；廣度優先遍歷採用隊列方式實現；

6.測試代碼中以有向網的所有帶權邊作為邊的初始化數據，選擇圖類型（DG, UDG, DN, UDN）可創建成不同類型的圖。二、測試代碼中的圖結構圖

深度優先遍歷序列（從 v1 頂點開始）：

1.無向圖/網：v1-v2-v3-v5-v4-v6-v7

2.有向圖/網：v1-v2-v5-v3-v4-v6-v7

廣度優先遍歷序列（從 v2 頂點開始）：

1.無向圖/網：v2-v1-v3-v5-v4-v6-v7

2.有向圖/網：v2-v5 後序無法遍歷

注：有向圖的遍歷 是遵循出度方向遍歷的，若無出度方向，則遍歷終止。

三、代碼

1. 
   
2. //文件名："GraphAdjMat.h"
3. #pragma once
4. #ifndef GRAPHADJMAT_H_
5. #define GRAPHADJMAT_H_
7. #include
8. #include
9. #include "ObjArrayList.h"
10. #include "LinkQueue.h"
11. using namespace std;
13. /*
14. .圖（鄰接矩陣實現） Graph Adjacency Matrix
15. .相關術語：
16. .頂點 Vertex ； 邊 Arc ；權 Weight ；
17. .有向圖 Digraph ；無向圖 Undigraph ；
18. .有向網 Directed Network ；無向網 Undirected Network ；
19. */
21. class GraphAdjMat
22. {
23. /*
24. .邊（弧） 單元，注：鄰接矩陣單元
25. */
26. struct ArcCell
27. {
28. int adj;//鄰接頂點關係。圖：0|不相鄰 1|相鄰 ；網：無窮（INT_MAX）|不相鄰 權值（W）|相鄰
29. char * info;//邊（弧）信息
30. };
32. public:
33. /*
34. .圖 種類
35. */
36. enum GraphType
37. {
38. DG,//有向圖，默認 0
39. UDG,//無向圖，默認 1
40. DN,//有向網，默認 2
41. UDN//無向網，默認 3
42. };
43. /*
44. .邊（弧）數據，注：供外部初始化邊數據使用
45. */
46. struct ArcData
47. {
48. string Tail;//弧尾
49. string Head;//弧頭
50. int Weight;//權重
51. };
53. private:
54. const int _INFINITY = INT_MAX;//無窮大 注：包含於頭文件
55. static const int _MAX_VERTEX_NUM = 10;//支持最大頂點數
57. //靜態存儲結構
58. string vexs[_MAX_VERTEX_NUM];//頂點表
59. ArcCell arcs[_MAX_VERTEX_NUM][_MAX_VERTEX_NUM];//邊（弧）矩陣
60. int vexNum;//頂點數
61. int arcNum;//邊數
62. int type;//圖種類
63. int nonAdjInt;//不相鄰 int 值：0|無權 無窮|有權
65. LinkQueue *vexs_null_index_queue = new LinkQueue();//頂點數組中空頂點位置索引隊列 （需要銷燬）
66. bool vexs_visited[_MAX_VERTEX_NUM];//頂點訪問標記數組：0|未訪問 1|已訪問
68. void _CreateDG(ObjArrayList * arcsList);//創建有向圖
69. void _CreateUDG(ObjArrayList * arcsList);//創建無向圖
70. void _CreateDN(ObjArrayList * arcsList);//創建有向網
71. void _CreateUDN(ObjArrayList * arcsList);//創建無向網
73. int _Locate(string vertex);//定位頂點元素位置
74. void _DFS_R(int index);//深度優先遍歷 遞歸
76. public:
77. GraphAdjMat(int type);//構造函數：初始化圖類型
78. ~GraphAdjMat();//析構函數：銷燬圖存儲空間
79. void Init(ObjArrayList * vexs, ObjArrayList * arcsList);//初始化頂點、邊數據為 圖|網
80. void Display();//顯示 圖|網
81. void InsertVertex(string *vertex);//插入一個新頂點
82. void DeleteVertex(string *vertex);//刪除一個頂點
83. void InsertArc(ArcData *arc);//插入一條新邊（弧）
84. void DeleteArc(ArcData *arc);//刪除一條邊（弧）
85. void Display_DFS(string *vertex);//從指定頂點開始，深度優先遍歷
86. void Display_BFS(string *vertex);//從指定頂點開始，廣度優先遍歷
87. };
89. GraphAdjMat::GraphAdjMat(int type)
90. {
91. /*
92. .構造函數：初始化圖類型
93. */
94. this->type = type;
95. this->vexNum = 0;
96. this->arcNum = 0;
97. if (this->type == DG || this->type == UDG)
98. {
99. //圖的不相鄰 int 值 0
100. this->nonAdjInt = 0;
101. }
102. else
103. {
104. //網的不相鄰 int 值 無窮大
105. this->nonAdjInt = this->_INFINITY;
106. }
107. }
109. GraphAdjMat::~GraphAdjMat()
110. {
111. /*
112. .析構函數：銷燬圖
113. */
114. //1.釋放頂點空位置索引隊列
115. int * e;
116. while (vexs_null_index_queue->GetHead() != NULL)
117. {
118. e = vexs_null_index_queue->DeQueue();
119. delete e;
120. }
121. delete vexs_null_index_queue;
123. }
125. void GraphAdjMat::Init(ObjArrayList * vexs, ObjArrayList * arcsList)
126. {
127. /*
128. .初始化頂點、邊數據，並構建 圖|網
129. .入參：
130. .vexs: 頂點 列表
131. .arcsList: 邊數據 列表
132. */
133. //1.初始化頂點數據
134. if (vexs->Length() > this->_MAX_VERTEX_NUM)
135. {
136. return;
137. }
138. for (int i = 0; i < vexs->Length(); i++)
139. {
140. this->vexs[i] = *vexs->Get(i);
141. }
142. this->vexNum = vexs->Length();
143. //1.1.初始化頂點數組空頂點位置索引隊列
144. for (int i = vexs->Length(); i < _MAX_VERTEX_NUM; i++)
145. {
146. vexs_null_index_queue->EnQueue(new int(i));
147. }
148. //2.根據初始化的圖類型，創建指定的圖
149. switch (this->type)
150. {
151. case DG:
152. _CreateDG(arcsList); break;
153. case UDG:
154. _CreateUDG(arcsList); break;
155. case DN:
156. _CreateDN(arcsList); break;
157. case UDN:
158. _CreateUDN(arcsList); break;
159. default:
160. break;
161. }
162. }
164. void GraphAdjMat::_CreateDG(ObjArrayList * arcsList)
165. {
166. /*
167. .創建有向圖
168. .頂點相鄰關係：0|不相鄰 1|相鄰
169. .鄰接矩陣為 非對稱矩陣
170. */
171. //初始化臨時 邊對象
172. ArcData * arcData = NULL;
173. //初始化 矩陣二維座標
174. int m = 0, n = 0;
175. //初始化邊的鄰接矩陣
176. for (int i = 0; i < _MAX_VERTEX_NUM; i++)
177. {
178. for (int j = 0; j < _MAX_VERTEX_NUM; j++)
179. {
180. this->arcs[i][j].adj = 0;
181. this->arcs[i][j].info = NULL;
182. }
183. }
184. //遍歷邊數據列表
185. for (int i = 0; i < arcsList->Length(); i++)
186. {
187. //按序獲取邊（弧）
188. arcData = arcsList->Get(i);
189. //定位（或設置）邊的兩端頂點位置
190. m = _Locate(arcData->Tail);
191. n = _Locate(arcData->Head);
192. //設置頂點相鄰 為 1 （無向）
193. if (this->arcs[m][n].adj == 1)
194. {
195. //去除重複邊
196. continue;
197. }
198. this->arcs[m][n].adj = 1;
199. //邊 計數
200. this->arcNum++;
201. }
202. }
204. void GraphAdjMat::_CreateUDG(ObjArrayList * arcsList)
205. {
206. /*
207. .創建無向圖
208. .頂點相鄰關係：0|不相鄰 1|相鄰
209. .鄰接矩陣為 對稱矩陣
210. */
211. //初始化臨時 邊對象
212. ArcData * arcData = NULL;
213. //初始化 矩陣二維座標
214. int m = 0, n = 0;
215. //初始化邊的鄰接矩陣
216. for (int i = 0; i < _MAX_VERTEX_NUM; i++)
217. {
218. for (int j = 0; j < _MAX_VERTEX_NUM; j++)
219. {
220. this->arcs[i][j].adj = 0;
221. this->arcs[i][j].info = NULL;
222. }
223. }
224. //遍歷邊數據列表
225. for (int i = 0; i < arcsList->Length(); i++)
226. {
227. //按序獲取邊（弧）
228. arcData = arcsList->Get(i);
229. //定位（或設置）邊的兩端頂點位置
230. m = _Locate(arcData->Tail);
231. n = _Locate(arcData->Head);
232. //設置頂點相鄰 為 1 （有向）
233. if (this->arcs[m][n].adj == 1 || this->arcs[n][m].adj == 1)
234. {
235. //去除重複邊
236. continue;
237. }
238. this->arcs[m][n].adj = 1;
239. this->arcs[n][m].adj = 1;
240. //邊 計數
241. this->arcNum++;
242. }
243. }
245. void GraphAdjMat::_CreateDN(ObjArrayList * arcsList)
246. {
247. /*
248. .創建有向網
249. .頂點相鄰關係：infinity|不相鄰 w|相鄰
250. .鄰接矩陣為 非對稱矩陣
251. */
252. //初始化臨時 邊對象
253. ArcData * arcData = NULL;
254. //初始化 矩陣二維座標
255. int m = 0, n = 0;
256. //初始化邊的鄰接矩陣
257. for (int i = 0; i < _MAX_VERTEX_NUM; i++)
258. {
259. for (int j = 0; j < _MAX_VERTEX_NUM; j++)
260. {
261. this->arcs[i][j].adj = this->_INFINITY;//無窮大
262. this->arcs[i][j].info = NULL;
263. }
264. }
265. //遍歷邊數據列表
266. for (int i = 0; i < arcsList->Length(); i++)
267. {
268. //按序獲取邊（弧）
269. arcData = arcsList->Get(i);
270. //定位（或設置）邊的兩端頂點位置
271. m = _Locate(arcData->Tail);
272. n = _Locate(arcData->Head);
273. //設置頂點相鄰 為 weight 權重
274. if (this->arcs[m][n].adj != this->_INFINITY)
275. {
276. //去除重複邊
277. continue;
278. }
279. this->arcs[m][n].adj = arcData->Weight;
280. //邊 計數
281. this->arcNum++;
282. }
283. }
285. void GraphAdjMat::_CreateUDN(ObjArrayList * arcsList)
286. {
287. /*
288. .創建無向網
289. .頂點相鄰關係：infinity|不相鄰 w|相鄰
290. .鄰接矩陣為 對稱矩陣
291. */
292. //初始化臨時 邊對象
293. ArcData * arcData = NULL;
294. //初始化 矩陣二維座標
295. int m = 0, n = 0;
296. //初始化邊的鄰接矩陣
297. for (int i = 0; i < _MAX_VERTEX_NUM; i++)
298. {
299. for (int j = 0; j < _MAX_VERTEX_NUM; j++)
300. {
301. this->arcs[i][j].adj = this->_INFINITY;//無窮大
302. this->arcs[i][j].info = NULL;
303. }
304. }
305. //遍歷邊數據列表
306. for (int i = 0; i < arcsList->Length(); i++)
307. {
308. //按序獲取邊（弧）
309. arcData = arcsList->Get(i);
310. //定位（或設置）邊的兩端頂點位置
311. m = _Locate(arcData->Tail);
312. n = _Locate(arcData->Head);
313. //設置頂點相鄰 為 weight 權重
314. if (this->arcs[m][n].adj != this->_INFINITY || this->arcs[n][m].adj != this->_INFINITY)
315. {
316. //去除重複邊
317. continue;
318. }
319. if (arcData->Weight == this->_INFINITY)
320. {
321. //去除權重為 無窮 的邊
322. continue;
323. }
324. this->arcs[m][n].adj = arcData->Weight;
325. this->arcs[n][m].adj = arcData->Weight;
326. //邊 計數
327. this->arcNum++;
328. }
329. }
331. int GraphAdjMat::_Locate(string vertex)
332. {
333. /*
334. .定位頂點元素位置
335. .後期可改成【字典樹】，頂點數超過100個後定位頂點位置可更快
336. */
337. //遍歷定位頂點位置
338. for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
339. {
340. if (vertex == this->vexs[i])
341. {
342. return i;
343. }
344. }
345. cout << endl << "頂點[" << vertex << "]不存在。" << endl;
346. return -1;
347. }
349. void GraphAdjMat::Display()
350. {
351. /*
352. .顯示 圖|網 （輸出頂點數組、鄰接矩陣）
353. */
354. //顯示頂點數組
355. //注：當刪除某個中間序號頂點後，頂點數組就不是連續的
356. cout << endl << "頂點數組：" << endl;
357. for (int i = 0, num = 0; i < this->_MAX_VERTEX_NUM && num < this->vexNum; i++)
358. {
359. if (this->vexs[i] != "")
360. {
361. cout << " (" << i << ")" << this->vexs[i];
362. num++;
363. }
364. }
365. //顯示邊（鄰接矩陣）
366. cout << endl << "邊（鄰接矩陣）：" << endl;
367. cout << " ";
368. for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
369. {
370. cout << "[" << i << "]";
371. }
372. cout << endl;
373. for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
374. {
375. cout << "[" << i << "] ";
376. for (int j = 0; j < this->_MAX_VERTEX_NUM; j++)
377. {
378. if (this->arcs[i][j].adj == this->_INFINITY)
379. cout << " + ";
380. else
381. cout << " " << this->arcs[i][j].adj << " ";
382. }
383. cout << endl;
384. }
385. }
387. void GraphAdjMat::InsertVertex(string *vertex)
388. {
389. /*
390. .插入一個新頂點
391. */
392. //1.判斷頂點是否已存在
393. if (_Locate(*vertex) > -1)
394. {
395. cout << endl << "該頂點已存在。" << endl;
396. return;
397. }
398. //2.判斷頂點數是否達到上限
399. if (this->vexNum >= this->_MAX_VERTEX_NUM)
400. {
401. cout << endl << "頂點數已達上限。" << endl;
402. return;
403. }
404. //3.插入新頂點，並自增頂點總數
405. int * index = vexs_null_index_queue->DeQueue();//從空位置索引隊列中取
406. this->vexs[*index] = *vertex;
407. this->vexNum++;
408. //4.新增的頂點在鄰接矩陣中不需要作任何操作（已初始化）
410. }
412. void GraphAdjMat::DeleteVertex(string *vertex)
413. {
414. /*
415. .刪除一個頂點
416. */
417. //1.判斷頂點是否已存在
418. int index = _Locate(*vertex);
419. if (index == -1)
420. {
421. cout << endl << "該頂點不存在。" << endl;
422. return;
423. }
424. //2.刪除該頂點，並自減頂點總數
425. this->vexs[index] = "";
426. this->vexNum--;
427. //3.清除鄰接矩陣 index 行列的數據，即將此行列 恢復初始化狀態
428. if (this->type == DG || this->type == UDG)
429. {
430. //圖
431. for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
432. {
433. this->arcs[i][index].adj = 0;
434. this->arcs[index][i].adj = 0;
435. }
436. }
437. else
438. {
439. //網
440. for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
441. {
442. this->arcs[i][index].adj = this->_INFINITY;
443. this->arcs[index][i].adj = this->_INFINITY;
444. }
445. }
446. }
449. void GraphAdjMat::InsertArc(ArcData *arc)
450. {
451. /*
452. .插入一條新邊（弧）
453. .若已存在，將對其更新
454. */
455. //1.定位頂點位置
456. int i = _Locate(arc->Tail);
457. int j = _Locate(arc->Head);
458. //2.判斷頂點是否存在
459. if (i == -1 || j == -1)
460. {
461. cout << endl << "該邊頂點不存在。" << endl;
462. return;
463. }
464. //3.插入/更新一條邊
465. if (this->type == DG)
466. {
467. //有向無權圖
468. this->arcs[i][j].adj = 1;
469. }
470. else if (this->type == UDG)
471. {
472. //無向無權圖
473. this->arcs[i][j].adj = 1;
474. this->arcs[j][i].adj = 1;
475. }
476. else if (this->type == DN)
477. {
478. //有向有權網
479. this->arcs[i][j].adj = arc->Weight;
480. }
481. else
482. {
483. //無向有權網
484. this->arcs[i][j].adj = arc->Weight;
485. this->arcs[j][i].adj = arc->Weight;
486. }
487. }
489. void GraphAdjMat::DeleteArc(ArcData *arc)
490. {
491. /*
492. .刪除一條邊（弧）
493. */
494. //1.定位頂點位置
495. int i = _Locate(arc->Tail);
496. int j = _Locate(arc->Head);
497. //2.判斷頂點是否存在
498. if (i == -1 || j == -1)
499. {
500. cout << endl << "該邊頂點不存在。" << endl;
501. return;
502. }
503. //3.刪除一條邊，即 恢復初始化狀態
504. if (this->type == DG)
505. {
506. //有向無權圖
507. this->arcs[i][j].adj = 0;
508. }
509. else if (this->type == UDG)
510. {
511. //無向無權圖
512. this->arcs[i][j].adj = 0;
513. this->arcs[j][i].adj = 0;
514. }
515. else if (this->type == DN)
516. {
517. //有向有權網
518. this->arcs[i][j].adj = this->_INFINITY;
519. }
520. else
521. {
522. //無向有權網
523. this->arcs[i][j].adj = this->_INFINITY;
524. this->arcs[j][i].adj = this->_INFINITY;
525. }
526. }
528. void GraphAdjMat::Display_DFS(string *vertex)
529. {
530. /*
531. .深度優先遍歷顯示，從指定頂點開始
532. */
533. //1.判斷頂點是否存在
534. int index = _Locate(*vertex);
535. if (index == -1)
536. return;
537. //2.初始化頂點訪問數組
538. for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
539. {
540. this->vexs_visited[i] = 0;
541. }
542. //3.深度優先遍歷 遞歸
543. cout << "深度優先遍歷：（從頂點" << *vertex << "開始）" << endl;
544. _DFS_R(index);
545. }
547. void GraphAdjMat::_DFS_R(int index)
548. {
549. /*
550. .深度優先遍歷 遞歸
551. .有向/無向算法是一樣的
552. .有向圖|網，以當前頂點的出度方向遍歷
553. .無向圖|網，以當前頂點的相鄰結點方向遍歷（可理解為“出度”，但不是出度）
554. */
555. //1.訪問頂點，並標記已訪問
556. cout << this->vexs[index] << " ";
557. this->vexs_visited[index] = 1;
558. //2.訪問其相鄰頂點
559. for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
560. {
561. //當邊值 不是 不相鄰int值（0|無權 無窮|有權），且未被訪問過時，可訪問
562. if (this->arcs[index][i].adj != this->nonAdjInt && this->vexs_visited[i] != 1)
563. {
564. _DFS_R(i);
565. }
566. }
567. }
569. void GraphAdjMat::Display_BFS(string *vertex)
570. {
571. /*
572. .廣度優先遍歷顯示，從指定頂點開始
573. .類似於樹的層次遍歷算法
574. */
575. //1.判斷頂點是否存在
576. int index = _Locate(*vertex);
577. if (index == -1)
578. return;
579. //2.初始化頂點訪問數組
580. for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
581. {
582. this->vexs_visited[i] = 0;
583. }
584. //3.廣度優先遍歷
585. cout << "廣度優先遍歷：（從頂點" << *vertex << "開始）" << endl;
586. //3.1.初始化隊列
587. LinkQueue * vexQ = new LinkQueue();
588. //3.2.訪問開始頂點，並標記訪問、入隊
589. cout << this->vexs[index] << " ";
590. this->vexs_visited[index] = 1;
591. vexQ->EnQueue(new int(index));
592. //3.3.出隊，並遍歷鄰接頂點（下一層次），訪問後入隊
593. while (vexQ->GetHead() != NULL)
594. {
595. index = * vexQ->DeQueue();
596. for (int j = 0; j < _MAX_VERTEX_NUM; j++)
597. {
598. //未訪問過的鄰接頂點
599. if (this->arcs[index][j].adj != this->nonAdjInt && this->vexs_visited[j] != 1)
600. {
601. //訪問頂點，並標記訪問、入隊
602. cout << this->vexs[j] << " ";
603. this->vexs_visited[j] = 1;
604. vexQ->EnQueue(new int(j));
605. }
606. }
607. }
609. //4.釋放隊列
610. int * e;
611. while (vexQ->GetHead() != NULL)
612. {
613. e = vexQ->DeQueue();
614. delete e;
615. }
616. delete vexQ;
617. }
619. #endif // !GRAPHADJMAT_H_
620. //文件名："GraphAdjMat_Test.cpp"
621. #include "stdafx.h"
622. #include
623. #include "GraphAdjMat.h"
624. #include "ObjArrayList.h"
625. using namespace std;
627. int main()
628. {
629. //初始化頂點數據
630. string * v1 = new string("v1");
631. string * v2 = new string("v2");
632. string * v3 = new string("v3");
633. string * v4 = new string("v4");
634. string * v5 = new string("v5");
635. string * v6 = new string("v6");
636. string * v7 = new string("v7");
637. ObjArrayList * vexs = new ObjArrayList();
638. vexs->Add(v1);
639. vexs->Add(v2);
640. vexs->Add(v3);
641. vexs->Add(v4);
642. vexs->Add(v5);
643. vexs->Add(v6);
644. vexs->Add(v7);
646. //初始化邊（弧）數據
647. GraphAdjMat::ArcData * arc1 = new GraphAdjMat::ArcData{ "v1", "v2", 2 };
648. GraphAdjMat::ArcData * arc2 = new GraphAdjMat::ArcData{ "v1", "v3", 3 };
649. GraphAdjMat::ArcData * arc3 = new GraphAdjMat::ArcData{ "v1", "v4", 4 };
650. GraphAdjMat::ArcData * arc4 = new GraphAdjMat::ArcData{ "v3", "v1", 5 };
651. GraphAdjMat::ArcData * arc5 = new GraphAdjMat::ArcData{ "v3", "v2", 6 };
652. GraphAdjMat::ArcData * arc6 = new GraphAdjMat::ArcData{ "v3", "v5", 7 };
653. GraphAdjMat::ArcData * arc7 = new GraphAdjMat::ArcData{ "v2", "v5", 8 };
654. GraphAdjMat::ArcData * arc8 = new GraphAdjMat::ArcData{ "v4", "v6", 9 };
655. GraphAdjMat::ArcData * arc9 = new GraphAdjMat::ArcData{ "v4", "v7", 9 };
656. GraphAdjMat::ArcData * arc10 = new GraphAdjMat::ArcData{ "v6", "v7", 9 };
657. ObjArrayList<:arcdata> * arcsList = new ObjArrayList<:arcdata>();
658. arcsList->Add(arc1);
659. arcsList->Add(arc2);
660. arcsList->Add(arc3);
661. arcsList->Add(arc4);
662. arcsList->Add(arc5);
663. arcsList->Add(arc6);
664. arcsList->Add(arc7);
665. arcsList->Add(arc8);
666. arcsList->Add(arc9);
667. arcsList->Add(arc10);
669. //測試1：無向圖
670. cout << endl << "無向圖初始化：" << endl;
671. GraphAdjMat * udg = new GraphAdjMat(GraphAdjMat::UDG);
672. udg->Init(vexs, arcsList);
673. udg->Display();
674. //1.1.深度優先遍歷
675. cout << endl << "無向圖深度優先遍歷序列：" << endl;
676. udg->Display_DFS(v1);
677. //1.2.廣度優先遍歷
678. cout << endl << "無向圖廣度優先遍歷序列：" << endl;
679. udg->Display_BFS(v2);
680. //1.3.插入新頂點、新邊
681. cout << endl << "無向圖插入新頂點、新邊：" << endl;
682. udg->InsertVertex(new string("v8"));
683. udg->InsertArc(new GraphAdjMat::ArcData{ "v8", "v1", 8 });
684. udg->Display();
685. //1.4.刪除頂點、邊
686. cout << endl << "無向圖刪除頂點v1、邊arc9：" << endl;
687. udg->DeleteVertex(v1);
688. udg->DeleteArc(arc9);
689. udg->Display();
691. //測試2：有向圖
692. cout << endl << "有向圖：" << endl;
693. GraphAdjMat * dg = new GraphAdjMat(GraphAdjMat::DG);
694. dg->Init(vexs, arcsList);
695. dg->Display();
696. //2.1.深度優先遍歷
697. cout << endl << "有向圖深度優先遍歷序列：" << endl;
698. dg->Display_DFS(v1);
699. //2.2.廣度優先遍歷
700. cout << endl << "有向圖廣度優先遍歷序列：" << endl;
701. dg->Display_BFS(v2);
703. //測試：無向網
704. cout << endl << "無向網：" << endl;
705. GraphAdjMat * udn = new GraphAdjMat(GraphAdjMat::UDN);
706. udn->Init(vexs, arcsList);
707. udn->Display();
709. //測試：有向網
710. cout << endl << "有向網：" << endl;
711. GraphAdjMat * dn = new GraphAdjMat(GraphAdjMat::DN);
712. dn->Init(vexs, arcsList);
713. dn->Display();
715. return 0;
716. }

閱讀更多 編程學習 的文章

關鍵字: 鄰接矩陣 數據結構 頂點