写一个图类
说到交通网路的模拟化表示，那就不得不用到数据结构中的图。想必这应该是最方便形象的表示方法了把。
图的概念
图是由顶点集合及顶点之间关系的集合组成的一种数据结构，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
pragma once
# include
using namespace std;
int DefaultMaxVertices = 500; //最大顶点数
auto memory_error = [](char * function, string aim) {
cerr << function << "申请" << aim.c_str() << "内存分配错误" << endl;
exit(1);
}; //内存申请错误的提示lamba表达式
struct Edge {
int dest; //标记关系节点
double weight;//权值
Edge * link;//指向边的指针
Edge(int num, double weight): dest(num), weight(weight), link(nullptr) {}
};
struct Vertex {
string data; //道路口的信息，暂时用string
Edge * adj; //指向边的指针
Vertex(string data = "点"): data(data), adj(nullptr) {}
};
class Graph_lnk {
friend ostream & operator << (ostream & in, Graph_lnk & G); //运算符重载，图的输出
public:
Graph_lnk(int sv = DefaultMaxVertices);
~Graph_lnk();
int NumberOfVertices() { return numVertices; } //返回当前顶点数
int NumberOfEdges() { return numEdges; } //返回当前边数
Vertex getVertex(return NodeTable[v]; } //返回该节点
string getValue(int v) {return NodeTable - > data;} //返回道路信息
bool insertEdge(int v1, int v2, double weight); //插入一条边
bool insertVertex(string data); //插入一个路口
protected: int numVertices; //当前顶点数
int numEdges; //当前边数
private: Vertex * NodeTable;
};
Graph_lnk::Graph_lnk(int sv) {
numVertices = sv;
numEdges = 0;
NodeTable = new Vertex[DefaultMaxVertices];
if (NodeTable == nullptr) {
memory_error(__func__, "NodeTable");
}
for (int i = 0; i };
bool Graph_lnk::insertEdge(int v1, int v2, double weight) {
if (v1 >= 0 && v1 = 0 && v2
Edge * q = nullptr, * p = nullptr;
if (NodeTable[v1].adj != nullptr) {
p = NodeTable[v1].adj;
q = p - > link;
while (q != nullptr) {
p = q;
q = p - > link;
}
q = new Edge(v2, weight);
p - > link = q;
} else {
NodeTable[v1].adj = new Edge(v2, weight);
}
if (NodeTable[v2].adj != nullptr) {
p = NodeTable[v2].adj;
q = p - > link;
while (q != nullptr) {
p = q;
q = p - > link;
}
q = new Edge(v1, weight);
p - > link = q;
} else {
NodeTable[v2].adj = new Edge(v1, weight);
}
numEdges++;
}
return 0;
}
bool Graph_lnk::insertVertex(string data) {
if (numVertices == DefaultMaxVertices) return false;
else {
NodeTable[numVertices].data = data;
NodeTable[numVertices].adj = nullptr;
numVertices++;
}
return true;
}
Graph_lnk::~Graph_lnk() {
delete[] NodeTable;
};
分析与理由
在交通道路网络图的构建中，一定需要的两个函数insertEdge();和insertVertex(); 我使用两个主要的数据结构，Edge（表示边），Vertex（表示点）。用它们的集合来表示整个图，这样做可以有效的利用空间？（但是还是申请了VerTex（500））
缺陷与不足
不管你构建含多少个点的图，都需要申请固定的空间，只有当点小于而且越接近于500时空间利用率才最高。
插入边时，需要在两个点做增加，但是好像对于实际情况这样做并没有好处？
。。。。
问题与思考
作为交通网络图，是否还需要拓展一些别的功能？
在储存的过程中，是否用bit矩阵来存储数据？
能不能在插入的过程中只新增一个点上的边？
或者直接以边为基本研究单位，来构建图类？
心得与感悟
本来以为写一个图类，会是一件比较容易的事，没想到却也花了这么久，是考虑的太多？还是基础不牢？
刚开始想用模板类来表示，这样在后期数据类型拓展时比较方便，没想到却是发现一堆错误，还解决不了，最后要重新来过。
基础还是要牢固才可以，现在写的东西自己都感觉境界不够，没有别人那种精妙绝伦的感觉。
平常有时间多沉下心来学习，切记好高骛远，绕了一圈最后发现自己什么都不行…
版权声明: （https://www.thinkmoon.cn/post/519）
本文首发于指尖魔法屋-写一个图类
转载或引用必须申明原指尖魔法屋来源及源地址！