1、稀疏矩阵

有一个稀疏因子，这是节省空间的一种存储方式。

2、邻接表

以邻接矩阵存储图结构的话，当实际边数远远小于图的最大边数时，将会存储很多0，势必造成存储空间的巨大浪费；这时，就必须将邻接矩阵该用为邻接表；将邻接矩阵各行组织为一个单链表，类哈希的存储结构。

存储结构(控制头)：

intmaxVertices;//最大顶点数intcurVertices;//当前顶点数intcurEdges;//当前边数template<typenameType>classEdge{//边的存储结构public:Edge(intnum):dest(num),link(NULL){}public:intdest;//是另一个顶点的下标Edge*link;};template<typenameType>classVertex{//顶点的存储结构public:Typedata;//存放的顶点Edge<Type>*adj;};Vertex<Type>*vertexTable;//指向顶点的指针，是申请数组用的

存储模型：

3、核心方法

均由C++实现，无向图的邻接表；

(1)、删除边(是链表的删除操作，相对简单)：

boolremoveEdge(constType&v1,constType&v2){//删除边inti=getVertexIndex(v1);intj=getVertexIndex(v2);if(i==-1||j==-1){//保证顶点的保存在returnfalse;}//v1-->v2Edge<Type>*p=vertexTable[i].adj;if(p==NULL){//判断有没有边returnfalse;}if(p->link==NULL&&p->dest==j){//删除的是第一个边，其后没有边了；vertexTable[i].adj=NULL;deletep;}elseif(p->dest==j){//删除的是第一个边,并且其后还有边vertexTable[i].adj=p->link;deletep;}else{while(p->link!=NULL){if(p->link->dest==j){Edge<Type>*q=p->link;p->link=q->link;deleteq;}p=p->link;}}//v2-->v1Edge<Type>*s=vertexTable[j].adj;if(s==NULL){//判断有没有边returnfalse;}if(s->link==NULL&&s->dest==i){//删除的是第一个边，其后没有边了；vertexTable[j].adj=NULL;deletes;curEdges--;returnfalse;}elseif(s->dest==i){//删除的是第一个边,并且其后还有边vertexTable[j].adj=s->link;deletes;curEdges--;returntrue;}else{while(s->link!=NULL){if(s->link->dest==i){Edge<Type>*q=s->link;s->link=q->link;deleteq;curEdges--;returntrue;}s=s->link;}}returntrue;}

(2)、删除顶点：

这个算法相对复杂，但是思路比较清晰：

i>、首先找到要删除的顶点，将其后上的边所对应的边和这个边都得删除；

ii>、将最后一个顶点的data和adj都覆盖到这个地方；

iii>、找到其后边上的dest,更改为当下位置的下标；

大致模型如下：

boolremoveVertex(constType&v){//删除顶点inti=getVertexIndex(v);if(i==-1){returnfalse;}Edge<Type>*p=vertexTable[i].adj;//先删除边上的dest和此边while(p!=NULL){vertexTable[i].adj=p->link;intk=p->dest;Edge<Type>*q=vertexTable[k].adj;if(q->dest==i){vertexTable[k].adj=q->link;deleteq;}else{while(q->link!=NULL&&q->link->dest!=i){q=q->link;}Edge<Type>*t=q->link;q->link=t->link;deletet;}deletep;p=vertexTable[i].adj;curEdges--;}curVertices--;//下面实行覆盖，指针和最后的那个顶点的adj相等;vertexTable[i].data=vertexTable[curVertices].data;vertexTable[i].adj=vertexTable[curVertices].adj;vertexTable[curVertices].adj=NULL;intk=curVertices;p=vertexTable[i].adj;while(p!=NULL){//修改其它顶点的dest.Edge<Type>*s=vertexTable[p->dest].adj;while(s!=NULL){if(s->dest==k){s->dest=i;break;}s=s->link;}p=p->link;}returntrue;}

4、邻接表完整代码、测试代码、测试结果

(1)完整代码(用的是继承，方便写其它的存储结构代码)：

#ifndef_GRAPH_H_#define_GRAPH_H_#include<iostream>usingnamespacestd;#defineVERTEX_DEFAULT_SIZE10template<typenameType>classGraph{public:boolisEmpty()const{returncurVertices==0;}boolisFull()const{if(curVertices>=maxVertices||curEdges>=curVertices*(curVertices-1)/2)returntrue;//图满有2种情况：(1)、当前顶点数超过了最大顶点数，存放顶点的空间已满returnfalse;//(2)、当前顶点数并没有满，但是当前顶点所能达到的边数已满}intgetCurVertex()const{returncurVertices;}intgetCurEdge()const{returncurEdges;}public:virtualboolinsertVertex(constType&v)=0;//插入顶点virtualboolinsertEdge(constType&v1,constType&v2)=0;//插入边virtualboolremoveVertex(constType&v)=0;//删除顶点virtualboolremoveEdge(constType&v1,constType&v2)=0;//删除边virtualintgetFirstNeighbor(constType&v)=0;//得到第一个相邻顶点virtualintgetNextNeighbor(constType&v,constType&w)=0;//得到下一个相邻顶点public:virtualintgetVertexIndex(constType&v)const=0;//得到顶点下标virtualvoidshowGraph()const=0;//显示图protected:intmaxVertices;//最大顶点数intcurVertices;//当前顶点数intcurEdges;//当前边数};template<typenameType>classEdge{//边的存储结构public:Edge(intnum):dest(num),link(NULL){}public:intdest;Edge*link;};template<typenameType>classVertex{//顶点的存储结构public:Typedata;Edge<Type>*adj;};template<typenameType>classGraphLnk:publicGraph<Type>{#definemaxVerticesGraph<Type>::maxVertices//因为是模板，所以用父类的数据或方法都得加上作用域限定符#definecurVerticesGraph<Type>::curVertices#definecurEdgesGraph<Type>::curEdgespublic:GraphLnk(intsz=VERTEX_DEFAULT_SIZE){maxVertices=sz>VERTEX_DEFAULT_SIZE?sz:VERTEX_DEFAULT_SIZE;vertexTable=newVertex<Type>[maxVertices];for(inti=0;i<maxVertices;i++){vertexTable[i].data=0;vertexTable[i].adj=NULL;}curVertices=curEdges=0;}public:boolinsertVertex(constType&v){if(curVertices>=maxVertices){returnfalse;}vertexTable[curVertices++].data=v;returntrue;}boolinsertEdge(constType&v1,constType&v2){intv=getVertexIndex(v1);intw=getVertexIndex(v2);if(v==-1||w==-1){returnfalse;}Edge<Type>*p=vertexTable[v].adj;while(p!=NULL){//这里主要判断边是否已经存在if(p->dest==w){//无向图，判断一边即可;returnfalse;}p=p->link;}//v1-->v2//采用头插Edge<Type>*s=newEdge<Type>(w);s->link=vertexTable[v].adj;vertexTable[v].adj=s;//v2-->v1//采用头插Edge<Type>*q=newEdge<Type>(v);q->link=vertexTable[w].adj;vertexTable[w].adj=q;curEdges++;returntrue;}boolremoveVertex(constType&v){inti=getVertexIndex(v);if(i==-1){returnfalse;}Edge<Type>*p=vertexTable[i].adj;while(p!=NULL){vertexTable[i].adj=p->link;intk=p->dest;Edge<Type>*q=vertexTable[k].adj;if(q->dest==i){vertexTable[k].adj=q->link;deleteq;}else{while(q->link!=NULL&&q->link->dest!=i){q=q->link;}Edge<Type>*t=q->link;q->link=t->link;deletet;}deletep;p=vertexTable[i].adj;curEdges--;}curVertices--;//下面实行覆盖vertexTable[i].data=vertexTable[curVertices].data;vertexTable[i].adj=vertexTable[curVertices].adj;vertexTable[curVertices].adj=NULL;intk=curVertices;p=vertexTable[i].adj;while(p!=NULL){Edge<Type>*s=vertexTable[p->dest].adj;while(s!=NULL){if(s->dest==k){s->dest=i;break;}s=s->link;}p=p->link;}returntrue;}boolremoveEdge(constType&v1,constType&v2){inti=getVertexIndex(v1);intj=getVertexIndex(v2);if(i==-1||j==-1){//保证顶点的保存在returnfalse;}//v1-->v2Edge<Type>*p=vertexTable[i].adj;if(p==NULL){//判断有没有边returnfalse;}if(p->link==NULL&&p->dest==j){//删除的是第一个边，其后没有边了；vertexTable[i].adj=NULL;deletep;}elseif(p->dest==j){//删除的是第一个边,并且其后还有边vertexTable[i].adj=p->link;deletep;}else{while(p->link!=NULL){if(p->link->dest==j){Edge<Type>*q=p->link;p->link=q->link;deleteq;}p=p->link;}}//v2-->v1Edge<Type>*s=vertexTable[j].adj;if(s==NULL){//判断有没有边returnfalse;}if(s->link==NULL&&s->dest==i){//删除的是第一个边，其后没有边了；vertexTable[j].adj=NULL;deletes;curEdges--;returnfalse;}elseif(s->dest==i){//删除的是第一个边,并且其后还有边vertexTable[j].adj=s->link;deletes;curEdges--;returntrue;}else{while(s->link!=NULL){if(s->link->dest==i){Edge<Type>*q=s->link;s->link=q->link;deleteq;curEdges--;returntrue;}s=s->link;}}returntrue;}intgetFirstNeighbor(constType&v){inti=getVertexIndex(v);if(i!=-1){Edge<Type>*p=vertexTable[i].adj;if(p!=NULL){returnp->dest;}}return-1;}intgetNextNeighbor(constType&v,constType&w){inti=getVertexIndex(v);intj=getVertexIndex(w);if(i==-1||j==-1){return-1;}Edge<Type>*p=vertexTable[i].adj;while(p!=NULL){if(p->dest==j&&p->link!=NULL){returnp->link->dest;}p=p->link;}return-1;}public:intgetVertexIndex(constType&v)const{for(inti=0;i<curVertices;i++){if(vertexTable[i].data==v){returni;}}return-1;}voidshowGraph()const{for(inti=0;i<curVertices;i++){cout<<vertexTable[i].data<<":-->";Edge<Type>*p=vertexTable[i].adj;while(p!=NULL){cout<<p->dest<<"-->";p=p->link;}cout<<"Nul."<<endl;}}private:Vertex<Type>*vertexTable;//指向顶点的指针，是申请数组用的};#endif

(2)、测试代码：

#include"Graph.h"intmain(void){GraphLnk<char>gl;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<<gl.getFirstNeighbor('A')<<endl;cout<<gl.getNextNeighbor('A','B')<<endl;gl.removeEdge('B','C');cout<<"---------------------"<<endl;gl.removeVertex('B');gl.showGraph();return0;}

(3)、测试结果：

测试的图：