六讲贯通C++图的应用之一基本储存方法

　　图的应用恐怕是C++所有数据结构中最宽泛的了，但这也注定了在讲“数据结构的图”的时候没什么好讲的——关于图的最重要的是算法，而且相当的一部分都是很专业的，一般的人几乎不会接触到;相对而言，结构就显得分量很轻。你可以看到关于图中元素的操作很少，远没有单链表那里列出的一大堆“接口”。——一个结构如果复杂，那么能确切定义的操作就很有限。

成都做网站、网站制作,成都做网站公司-创新互联已向近1000家企业提供了,网站设计,网站制作,网络营销等服务!设计与技术结合,多年网站推广经验,合理的价格为您打造企业品质网站。

　　笔者从基本储存方法、DFS和BFS、无向图、最小生成树、最短路径以及活动网络(AOV、AOE)六个方面详细介绍图的应用。本文是这次系列文章的***篇，主要介绍图的基本存储方法。

　　基本储存方法

　　不管怎么说，还是先得把图存起来。不要看书上列出了好多方法，根本只有一个——邻接矩阵。如果矩阵是稀疏的，那就可以用十字链表来储存矩阵(见C++数据结构学习之稀疏矩阵)。如果我们只关系行的关系，那么就是邻接表(出边表);反之，只关心列的关系，就是逆邻接表(入边表)。

　　下面给出两种储存方法的实现。

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

　　这个实现是很简陋的，但应该能满足后面的讲解了。现在这个还什么都不能做，不要急，在下篇将讲述图的DFS和BFS。

【编辑推荐】

  1. 经典四讲贯通C++排序之一 插入排序
  2. c++编程常用工具
  3. 给C++初学者的50个忠告
  4. c++最基础的20条规则
  5. 程序员必看 c++笔试题汇总

网站名称：六讲贯通C++图的应用之一基本储存方法
文章网址：http://www.csdahua.cn/qtweb/news5/62705.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

外贸建站知识

行业网站建设

东电技改　　 　重庆服务器托管　　 　成都网站建设　　 　买友情链接　　 　成都服务器托管　　 　蜀锦在线　　 　江安网站建设　　 　移动服务器托管　　 　金融行业网站建设方案　　 　ssl证书申请　　 　成都劢可为　　 　广西弘博建站　　 　成都定制网站建设　　 　四川成都托管服务器　　 　php空间　　 　成都网站建设　　 　腾讯云虚拟主机　　 　不锈钢防护栏　　 　网站维护　　 　亚克力背部发光字