图的存储之邻接表-创新互联
1、稀疏矩阵
10年积累的做网站、成都网站建设经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站制作后付款的网站建设流程,更有罗定免费网站建设让你可以放心的选择与我们合作。有一个稀疏因子,这是节省空间的一种存储方式。
2、邻接表
以邻接矩阵存储图结构的话,当实际边数远远小于图的大边数时,将会存储很多0,势必造成存储空间的巨大浪费;这时,就必须将邻接矩阵该用为邻接表;将邻接矩阵各行组织为一个单链表,类哈希的存储结构。
存储结构(控制头):
int maxVertices; //大顶点数 int curVertices; //当前顶点数 int curEdges; //当前边数 templateclass Edge{ //边的存储结构 public: Edge(int num) : dest(num), link(NULL){} public: int dest; //是另一个顶点的下标 Edge *link; }; template class Vertex{ //顶点的存储结构 public: Type data; //存放的顶点 Edge *adj; }; Vertex *vertexTable; //指向顶点的指针,是申请数组用的
存储模型:
3、核心方法
均由C++实现,无向图的邻接表;
(1)、删除边(是链表的删除操作,相对简单):
bool removeEdge(const Type &v1, const Type &v2){ //删除边 int i = getVertexIndex(v1); int j = getVertexIndex(v2); if(i==-1 || j==-1){ //保证顶点的保存在 return false; } //v1-->v2 Edge*p = vertexTable[i].adj; if(p == NULL){ //判断有没有边 return false; } if(p->link == NULL && p->dest == j){ //删除的是第一个边,其后没有边了; vertexTable[i].adj = NULL; delete p; }else if(p->dest == j){ //删除的是第一个边,并且其后还有边 vertexTable[i].adj = p->link; delete p; }else{ while(p->link != NULL){ if(p->link->dest == j){ Edge *q = p->link; p->link = q->link; delete q; } p = p->link; } } //v2-->v1 Edge *s = vertexTable[j].adj; if(s == NULL){ //判断有没有边 return false; } if(s->link == NULL && s->dest == i){ //删除的是第一个边,其后没有边了; vertexTable[j].adj = NULL; delete s; curEdges--; return false; }else if(s->dest == i){ //删除的是第一个边,并且其后还有边 vertexTable[j].adj = s->link; delete s; curEdges--; return true; }else{ while(s->link != NULL){ if(s->link->dest == i){ Edge *q = s->link; s->link = q->link; delete q; curEdges--; return true; } s = s->link; } } return true; }
(2)、删除顶点:
这个算法相对复杂,但是思路比较清晰:
i>、首先找到要删除的顶点,将其后上的边所对应的边和这个边都得删除;
ii>、将最后一个顶点的data和adj都覆盖到这个地方;
iii>、找到其后边上的dest,更改为当下位置的下标;
大致模型如下:
bool removeVertex(const Type &v){ //删除顶点 int i = getVertexIndex(v); if(i == -1){ return false; } Edge*p = vertexTable[i].adj; //先删除边上的dest和此边 while(p != NULL){ vertexTable[i].adj = p->link; int k = p->dest; Edge *q = vertexTable[k].adj; if(q->dest == i){ vertexTable[k].adj = q->link; delete q; }else{ while(q->link != NULL && q->link->dest != i){ q = q->link; } Edge *t = q->link; q->link = t->link; delete t; } delete p; p = vertexTable[i].adj; curEdges--; } curVertices--; //下面实行覆盖,指针和最后的那个顶点的adj相等; vertexTable[i].data = vertexTable[curVertices].data; vertexTable[i].adj = vertexTable[curVertices].adj; vertexTable[curVertices].adj = NULL; int k = curVertices; p = vertexTable[i].adj; while(p != NULL){ //修改其它顶点的dest. Edge *s = vertexTable[p->dest].adj; while(s != NULL){ if(s->dest == k){ s->dest = i; break; } s = s->link; } p = p->link; } return true; }
4、邻接表完整代码、测试代码、测试结果
(1)完整代码(用的是继承,方便写其它的存储结构代码):
#ifndef _GRAPH_H_ #define _GRAPH_H_ #includeusing namespace std; #define VERTEX_DEFAULT_SIZE 10 template class Graph{ public: bool isEmpty()const{ return curVertices == 0; } bool isFull()const{ if(curVertices >= maxVertices || curEdges >= curVertices*(curVertices-1)/2) return true; //图满有2种情况:(1)、当前顶点数超过了大顶点数,存放顶点的空间已满 return false; //(2)、当前顶点数并没有满,但是当前顶点所能达到的边数已满 } int getCurVertex()const{ return curVertices; } int getCurEdge()const{ return curEdges; } public: virtual bool insertVertex(const Type &v) = 0; //插入顶点 virtual bool insertEdge(const Type &v1, const Type &v2) = 0; //插入边 virtual bool removeVertex(const Type &v) = 0; //删除顶点 virtual bool removeEdge(const Type &v1, const Type &v2) = 0; //删除边 virtual int getFirstNeighbor(const Type &v) = 0; //得到第一个相邻顶点 virtual int getNextNeighbor(const Type &v, const Type &w) = 0; //得到下一个相邻顶点 public: virtual int getVertexIndex(const Type &v)const = 0; //得到顶点下标 virtual void showGraph()const = 0; //显示图 protected: int maxVertices; //大顶点数 int curVertices; //当前顶点数 int curEdges; //当前边数 }; template class Edge{ //边的存储结构 public: Edge(int num) : dest(num), link(NULL){} public: int dest; Edge *link; }; template class Vertex{ //顶点的存储结构 public: Type data; Edge *adj; }; template class GraphLnk : public Graph { #define maxVertices Graph ::maxVertices //因为是模板,所以用父类的数据或方法都得加上作用域限定符 #define curVertices Graph ::curVertices #define curEdges Graph ::curEdges public: GraphLnk(int sz = VERTEX_DEFAULT_SIZE){ maxVertices = sz > VERTEX_DEFAULT_SIZE ? sz : VERTEX_DEFAULT_SIZE; vertexTable = new Vertex [maxVertices]; for(int i = 0; i < maxVertices; i++){ vertexTable[i].data = 0; vertexTable[i].adj = NULL; } curVertices = curEdges = 0; } public: bool insertVertex(const Type &v){ if(curVertices >= maxVertices){ return false; } vertexTable[curVertices++].data = v; return true; } bool insertEdge(const Type &v1, const Type &v2){ int v = getVertexIndex(v1); int w = getVertexIndex(v2); if(v==-1 || w==-1){ return false; } Edge *p = vertexTable[v].adj; while(p != NULL){ //这里主要判断边是否已经存在 if(p->dest == w){ //无向图,判断一边即可; return false; } p = p->link; } //v1-->v2 //采用头插 Edge *s = new Edge (w); s->link = vertexTable[v].adj; vertexTable[v].adj = s; //v2-->v1 //采用头插 Edge *q = new Edge (v); q->link = vertexTable[w].adj; vertexTable[w].adj = q; curEdges++; return true; } bool removeVertex(const Type &v){ int i = getVertexIndex(v); if(i == -1){ return false; } Edge *p = vertexTable[i].adj; while(p != NULL){ vertexTable[i].adj = p->link; int k = p->dest; Edge *q = vertexTable[k].adj; if(q->dest == i){ vertexTable[k].adj = q->link; delete q; }else{ while(q->link != NULL && q->link->dest != i){ q = q->link; } Edge *t = q->link; q->link = t->link; delete t; } delete p; p = vertexTable[i].adj; curEdges--; } curVertices--; //下面实行覆盖 vertexTable[i].data = vertexTable[curVertices].data; vertexTable[i].adj = vertexTable[curVertices].adj; vertexTable[curVertices].adj = NULL; int k = curVertices; p = vertexTable[i].adj; while(p != NULL){ Edge *s = vertexTable[p->dest].adj; while(s != NULL){ if(s->dest == k){ s->dest = i; break; } s = s->link; } p = p->link; } return true; } bool removeEdge(const Type &v1, const Type &v2){ int i = getVertexIndex(v1); int j = getVertexIndex(v2); if(i==-1 || j==-1){ //保证顶点的保存在 return false; } //v1-->v2 Edge *p = vertexTable[i].adj; if(p == NULL){ //判断有没有边 return false; } if(p->link == NULL && p->dest == j){ //删除的是第一个边,其后没有边了; vertexTable[i].adj = NULL; delete p; }else if(p->dest == j){ //删除的是第一个边,并且其后还有边 vertexTable[i].adj = p->link; delete p; }else{ while(p->link != NULL){ if(p->link->dest == j){ Edge *q = p->link; p->link = q->link; delete q; } p = p->link; } } //v2-->v1 Edge *s = vertexTable[j].adj; if(s == NULL){ //判断有没有边 return false; } if(s->link == NULL && s->dest == i){ //删除的是第一个边,其后没有边了; vertexTable[j].adj = NULL; delete s; curEdges--; return false; }else if(s->dest == i){ //删除的是第一个边,并且其后还有边 vertexTable[j].adj = s->link; delete s; curEdges--; return true; }else{ while(s->link != NULL){ if(s->link->dest == i){ Edge *q = s->link; s->link = q->link; delete q; curEdges--; return true; } s = s->link; } } return true; } int getFirstNeighbor(const Type &v){ int i = getVertexIndex(v); if(i != -1){ Edge *p = vertexTable[i].adj; if(p != NULL){ return p->dest; } } return -1; } int getNextNeighbor(const Type &v, const Type &w){ int i = getVertexIndex(v); int j = getVertexIndex(w); if(i==-1 || j==-1){ return -1; } Edge *p = vertexTable[i].adj; while(p != NULL){ if(p->dest == j && p->link != NULL){ return p->link->dest; } p = p->link; } return -1; } public: int getVertexIndex(const Type &v)const{ for(int i = 0; i < curVertices; i++){ if(vertexTable[i].data == v){ return i; } } return -1; } void showGraph()const{ for(int i = 0; i < curVertices; i++){ cout< "; Edge *p = vertexTable[i].adj; while(p != NULL){ cout< dest<<"-->"; p = p->link; } cout<<"Nul. "< *vertexTable; //指向顶点的指针,是申请数组用的 }; #endif
(2)、测试代码:
#include"Graph.h" int main(void){ GraphLnkgl; gl.insertVertex('A'); gl.insertVertex('B'); gl.insertVertex('C'); gl.insertVertex('D'); gl.insertEdge('A','B'); gl.insertEdge('A','D'); gl.insertEdge('B','C'); gl.insertEdge('C','D'); gl.showGraph(); cout< (3)、测试结果:
测试的图:
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
当前名称:图的存储之邻接表-创新互联
标题网址:http://pwwzsj.com/article/dgdieo.html