说到交通网路的模拟化表示,那就不得不用到数据结构中的图。想必这应该是最方便形象的表示方法了把。

图的概念

图是由顶点集合及顶点之间关系的集合组成的一种数据结构,Graph = (V,E)。其中顶点集合V = { x | x ∈ 某个数据对象集}是个有穷非空集合。E = {< x , y > | x , y ∈ V && Path( x , y )}

,即边集。

我所知的图的存储结构

邻接矩阵表示

邻接矩阵的表示,首先将所有的顶点信息组成一个表。然后利用一个矩阵来表示各顶点之间的相邻关系,称之为邻接矩阵。

邻接表表示

在第i行的单链表中,各节点(或称边节点)分别存放与同一个顶点Vi关联的各条边。各个节点配有其标识(及对应的顶点)和权值(若为有权图)以及指向另一个边节点的指针。

邻接多重表表示

邻接多重表的表示,主要一处理图的边为主(为什么会有这个需求?在什么情况会用到?),要求每条边处理一次的实际应用中特别有用(比如?)。它的主要思想是把多重表结构引入到图的邻接表中,就有点像把边作为研究的基本单位,用一个多重表节点来表示一条边。

十字链表表示

此为百度词条:十字链表(Orthogonal List)是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图,可以达到高效的存取效果。同时,代码的可读性也会得到提升。


我该选什么存储结构

首先,交通道路网络是双向的,所以我们可以将其视为无向图; 其次在一座城市的交通网络下,道路E 与路口 n的关系是 E << n^2,而且道路是会出现两点之间多条路的情况(即多重图)所以我舍弃第一种方法; 后面两种表示方式其实我也是一知半解,我有种感觉,如果在交通道路的分层模型下,可能第三种方式要更具优势,但是目前还想不了那么远。所以我暂时选用第二种方式,用邻接表表示。

我的实现代码

Graph_lnk.h // V1.0.1

  1. # pragma once

  2. # include < iostream >

  3. using namespace std;

  4. const int DefaultMaxVertices = 500; //最大顶点数

  5. auto memory_error = {

  6. cerr << function << 申请 << aim.c_str() << 内存分配错误 << endl;

  7. exit(1);

  8. }; //内存申请错误的提示lamba表达式

  9. struct Edge {

  10. int dest; //标记关系节点

  11. double weight; //权值

  12. Edge link; //指向边的指针

  13. Edge(int num, double weight): dest(num), weight(weight), link(nullptr) {}

  14. };

  15. struct Vertex {

  16. string data; //道路口的信息,暂时用string

  17. Edge adj; //指向边的指针

  18. Vertex(string data = ): data(data), adj(nullptr) {}

  19. };

  20. class Graph_lnk {

  21. friend ostream & operator << (ostream & in , Graph_lnk & G); //运算符重载,图的输出

  22. public: Graph_lnk(int sv = DefaultMaxVertices);

  23. ~Graph_lnk();

  24. int NumberOfVertices() {

  25. return numVertices;

  26. } //返回当前顶点数

  27. int NumberOfEdges() {

  28. return numEdges;

  29. } //返回当前边数

  30. Vertex getVertex(int v) {

  31. return NodeTable[v];

  32. } //返回该节点

  33. string getValue(int v) {

  34. return NodeTable - > data;

  35. } //返回道路信息

  36. bool insertEdge(int v1, int v2, double weight); //插入一条边

  37. bool insertVertex(string data); //插入一个路口

  38. protected: int numVertices; //当前顶点数

  39. int numEdges; //当前边数

  40. private: Vertex NodeTable;

  41. };

  42. ostream & operator << (ostream & out, Graph_lnk & G) {

  43. out << “——————————————–” << endl;

  44. out << 当前顶点数 << G.NumberOfVertices() << “,边数 << G.NumberOfEdges() << endl;

  45. Edge p = nullptr;

  46. for (int i = 0; i < G.NumberOfVertices(); i++) {

  47. Vertex v = G.getVertex(i);

  48. out << v.data.c_str() << “ “;

  49. p = v.adj;

  50. while (p != nullptr) {

  51. out << “->{“ << p - > dest << “:” << p - > weight << “}”;

  52. p = p - > link;

  53. }

  54. out << endl;

  55. }

  56. out << “——————————————–” << endl;

  57. return out;

  58. };

  59. Graph_lnk::Graph_lnk(int sv) {

  60. numVertices = sv;

  61. numEdges = 0;

  62. NodeTable = new Vertex[DefaultMaxVertices];

  63. if (NodeTable == nullptr) {

  64. memory_error(func, “NodeTable”);

  65. }

  66. for (int i = 0; i < sv; i++) NodeTable[i].adj = nullptr;

  67. };

  68. bool Graph_lnk::insertEdge(int v1, int v2, double weight) {

  69. if (v1 >= 0 && v1 < numVertices && v2 >= 0 && v2 < numVertices && v1 != v2) {

  70. Edge q = nullptr, p = nullptr;

  71. if (NodeTable[v1].adj != nullptr) {

  72. p = NodeTable[v1].adj;

  73. q = p - > link;

  74. while (q != nullptr) {

  75. p = q;

  76. q = p - > link;

  77. }

  78. q = new Edge(v2, weight);

  79. p - > link = q;

  80. } else {

  81. NodeTable[v1].adj = new Edge(v2, weight);

  82. }

  83. if (NodeTable[v2].adj != nullptr) {

  84. p = NodeTable[v2].adj;

  85. q = p - > link;

  86. while (q != nullptr) {

  87. p = q;

  88. q = p - > link;

  89. }

  90. q = new Edge(v1, weight);

  91. p - > link = q;

  92. } else {

  93. NodeTable[v2].adj = new Edge(v1, weight);

  94. }

  95. numEdges++;

  96. }

  97. return 0;

  98. }

  99. bool Graph_lnk::insertVertex(string data) {

  100. if (numVertices == DefaultMaxVertices) return false;

  101. else {

  102. NodeTable[numVertices].data = data;

  103. NodeTable[numVertices].adj = nullptr;

  104. numVertices++;

  105. }

  106. return true;

  107. }


  108. Graph_lnk::~Graph_lnk() {

  109. delete[] NodeTable;

  110. };

分析与理由

在交通道路网络图的构建中,一定需要的两个函数insertEdge();和insertVertex(); 我使用两个主要的数据结构,Edge(表示边),Vertex(表示点)。用它们的集合来表示整个图,这样做可以有效的利用空间?(但是还是申请了VerTex(500))


缺陷与不足

  1. 不管你构建含多少个点的图,都需要申请固定的空间,只有当点小于而且越接近于500时空间利用率才最高。
  2. 插入边时,需要在两个点做增加,但是好像对于实际情况这样做并没有好处?
  3. 。。。。


问题与思考

  1. 作为交通网络图,是否还需要拓展一些别的功能?
  2. 在储存的过程中,是否用bit矩阵来存储数据?
  3. 能不能在插入的过程中只新增一个点上的边?
  4. 或者直接以边为基本研究单位,来构建图类?

心得与感悟

  • 本来以为写一个图类,会是一件比较容易的事,没想到却也花了这么久,是考虑的太多?还是基础不牢?
  • 刚开始想用模板类来表示,这样在后期数据类型拓展时比较方便,没想到却是发现一堆错误,还解决不了,最后要重新来过。
  • 基础还是要牢固才可以,现在写的东西自己都感觉境界不够,没有别人那种精妙绝伦的感觉。
  • 平常有时间多沉下心来学习,切记好高骛远,绕了一圈最后发现自己什么都不行
  • 。。。。。