写一个图类

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

图的概念

图是由顶点集合及顶点之间关系的集合组成的一种数据结构,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)
本文首发于指尖魔法屋-写一个图类
转载或引用必须申明原指尖魔法屋来源及源地址!