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. }

閱讀更多 編程學習 的文章

關鍵字: 数据结构 技术 数组