程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 六講貫通C++圖的應用之一 基本儲存方法

六講貫通C++圖的應用之一 基本儲存方法

編輯:C++入門知識

圖的應用恐怕是C++所有數據結構中最寬泛的了,但這也注定了在講“數據結構的圖”的時候沒什麼好講的——關於圖的最重要的是算法,而且相當的一部分都是很專業的,一般的人幾乎不會接觸到;相對而言,結構就顯得分量很輕。你可以看到關於圖中元素的操作很少,遠沒有單鏈表那裡列出的一大堆“接口”。——一個結構如果復雜,那麼能確切定義的操作就很有限。

筆者從基本儲存方法DFS和BFS無向圖最小生成樹最短路徑以及活動網絡(AOV、AOE)六個方面詳細介紹圖的應用。本文是這次系列文章的第一篇,主要介紹圖的基本存儲方法。

基本儲存方法

不管怎麼說,還是先得把圖存起來。不要看書上列出了好多方法,根本只有一個——鄰接矩陣。如果矩陣是稀疏的,那就可以用十字鏈表來儲存矩陣(見C++數據結構學習之稀疏矩陣)。如果我們只關系行的關系,那麼就是鄰接表(出邊表);反之,只關心列的關系,就是逆鄰接表(入邊表)。

下面給出兩種儲存方法的實現。

  1. #ifndef Graphmem_H  
  2. #define Graphmem_H  
  3.  
  4. #include   
  5. #include   
  6. using namespace std;  
  7.  
  8. template <class name, class dist, class mem> class Network;  
  9.  
  10. const int maxV = 20;//最大節點數  
  11. template <class name, class dist>  
  12. class AdjMatrix  
  13. {  
  14. friend class Network >;  
  15. public:  
  16. AdjMatrix() : vNum(0), eNum(0)  
  17. {  
  18. vertex = new name[maxV]; edge = new dist*[maxV];  
  19. for (int i = 0; i < maxV; i++) edge[i] = new dist[maxV];  
  20. }  
  21. ~AdjMatrix()  
  22. {  
  23. for (int i = 0; i < maxV; i++) delete []edge[i];  
  24. delete []edge; delete []vertex;  
  25. }  
  26. bool insertV(name v)  
  27. {  
  28. if (find(v)) return false;  
  29. vertex[vNum] = v;  
  30. for (int i = 0; i < maxV; i++) edge[vNum][i] = NoEdge;  
  31. vNum++; return true;  
  32. }  
  33. bool insertE(name v1, name v2, dist cost)  
  34. {  
  35. int i, j;  
  36. if (v1 == v2 || !find(v1, i) || !find(v2, j)) return false;  
  37. if (edge[i][j] != NoEdge) return false;  
  38. edge[i][j] = cost; eNum++; return true;  
  39. }  
  40. name& getV(int n) { return vertex[n]; } //沒有越界檢查  
  41. int nextV(int m, int n)//返回m號頂點的第n號頂點後第一個鄰接頂點號,無返回-1  
  42. {  
  43. for (int i = n + 1; i < vNum; i++) if (edge[m][i] != NoEdge) return i;  
  44. return -1;  
  45. }  
  46. private:  
  47. int vNum, eNum;  
  48. dist NoEdge, **edge; name *vertex;  
  49. bool find(const name& v)  
  50. {  
  51. for (int i = 0; i < vNum; i++) if (v == vertex[i]) return true;  
  52. return false;  
  53. }  
  54. bool find(const name& v, int& i)  
  55. {  
  56. for (i = 0; i < vNum; i++) if (v == vertex[i]) return true;  
  57. return false;  
  58. }  
  59. };  
  60.  
  61. template <class name, class dist>  
  62. class LinkedList  
  63. {  
  64. friend class Network >;  
  65. public:  
  66. LinkedList() : vNum(0), eNum(0) {}  
  67. ~LinkedList()  
  68. {  
  69. for (int i = 0; i < vNum; i++) delete vertices[i].e;  
  70. }  
  71. bool insertV(name v)  
  72. {  
  73. if (find(v)) return false;  
  74. vertices.push_back(vertex(v, new list));  
  75. vNum++; return true;  
  76. }  
  77. bool insertE(const name& v1, const name& v2, const dist& cost)  
  78. {  
  79. int i, j;  
  80. if (v1 == v2 || !find(v1, i) || !find(v2, j)) return false;  
  81. for (list::iterator iter = vertices[i].e->begin();  
  82. iter != vertices[i].e->end() && iter->vID < j; iter++);  
  83. if (iter == vertices[i].e->end())  
  84. {  
  85. vertices[i].e->push_back(edge(j, cost)); eNum++; return true;  
  86. }  
  87. if (iter->vID == j) return false;  
  88. vertices[i].e->insert(iter, edge(j, cost)); eNum++; return true;  
  89. }  
  90. name& getV(int n) { return vertices[n].v; } //沒有越界檢查  
  91. int nextV(int m, int n)//返回m號頂點的第n號頂點後第一個鄰接頂點號,無返回-1  
  92. {  
  93. for (list::iterator iter = vertices[m].e->begin();  
  94. iter != vertices[m].e->end(); iter++) if (iter->vID > n) return iter->vID;  
  95. return -1;  
  96. }  
  97.  
  98. private:  
  99. bool find(const name& v)  
  100. {  
  101. for (int i = 0; i < vNum; i++) if (v == vertices[i].v) return true;  
  102. return false;  
  103. }  
  104. bool find(const name& v, int& i)  
  105. {  
  106. for (i = 0; i < vNum; i++) if (v == vertices[i].v) return true;  
  107. return false;  
  108. }  
  109. struct edge  
  110. {  
  111. edge() {}  
  112. edge(int vID, dist cost) : vID(vID), cost(cost) {}  
  113. int vID;  
  114. dist cost;  
  115. };  
  116. struct vertex  
  117. {  
  118. vertex() {}  
  119. vertex(name v, list* e) : v(v), e(e) {}  
  120. name v;  
  121. list* e;  
  122. };  
  123. int vNum, eNum;  
  124. vector vertices;  
  125. };  
  126.  
  127. #endif 

這個實現是很簡陋的,但應該能滿足後面的講解了。現在這個還什麼都不能做,不要急,在下篇將講述圖的DFS和BFS。

  1. 經典四講貫通C++排序之一 插入排序
  2. c++編程常用工具
  3. 給C++初學者的50個忠告
  4. c++最基礎的20條規則
  5. 程序員必看 c++筆試題匯總

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved