图的存储之邻接表
1、稀疏矩阵
成都创新互联公司是专业的嘉善网站建设公司,嘉善接单;提供成都网站设计、成都网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行嘉善网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
有一个稀疏因子,这是节省空间的一种存储方式。
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)、测试结果:
测试的图:
文章标题:图的存储之邻接表
转载来源:http://pwwzsj.com/article/popjid.html