1、图的父类

是一个抽象类，不能实类化对象，应具有的是抽象方法，提供一个接口，在由子类继承，实现自己的方法，

应提供的共有抽象方法和保护的数据：

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;//当前边数

2、子类继承、实现自己的方法

C++实现，继承的体现，是为了实现多态

(1)Graph.h

#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>classGraphMtx:publicGraph<Type>{//邻接矩阵继承父类矩阵#definemaxVerticesGraph<Type>::maxVertices//因为是模板，所以用父类的数据或方法都得加上作用域限定符#definecurVerticesGraph<Type>::curVertices#definecurEdgesGraph<Type>::curEdgespublic:GraphMtx(intvertexSize=VERTEX_DEFAULT_SIZE){//初始化邻接矩阵maxVertices=vertexSize>VERTEX_DEFAULT_SIZE?vertexSize:VERTEX_DEFAULT_SIZE;vertexList=newType[maxVertices];//申请顶点空间for(inti=0;i<maxVertices;i++){//都初始化为0vertexList[i]=0;}edge=newint*[maxVertices];//申请边的行for(i=0;i<maxVertices;i++){//申请列空间edge[i]=newint[maxVertices];}for(i=0;i<maxVertices;i++){//赋初值为0for(intj=0;j<maxVertices;j++){edge[i][j]=0;}}curVertices=curEdges=0;//当前顶点和当前边数}GraphMtx(Type(*mt)[4],intsz){//通过已有矩阵的初始化inte=0;//统计边数maxVertices=sz>VERTEX_DEFAULT_SIZE?sz:VERTEX_DEFAULT_SIZE;vertexList=newType[maxVertices];//申请顶点空间for(inti=0;i<maxVertices;i++){//都初始化为0vertexList[i]=0;}edge=newint*[maxVertices];//申请边的行for(i=0;i<maxVertices;i++){//申请列空间edge[i]=newType[maxVertices];}for(i=0;i<maxVertices;i++){//赋初值为矩阵当中的值for(intj=0;j<maxVertices;j++){edge[i][j]=mt[i][j];if(edge[i][j]!=0){e++;//统计列的边数}}}curVertices=sz;curEdges=e/2;}~GraphMtx(){}public:boolinsertVertex(constType&v){if(curVertices>=maxVertices){returnfalse;}vertexList[curVertices++]=v;returntrue;}boolinsertEdge(constType&v1,constType&v2){intmaxEdges=curVertices*(curVertices-1)/2;if(curEdges>=maxEdges){returnfalse;}intv=getVertexIndex(v1);intw=getVertexIndex(v2);if(v==-1||w==-1){cout<<"edgenoexit"<<endl;//要插入的顶点不存在，无法插入returnfalse;}if(edge[v][w]!=0){//当前边已经存在，不能进行插入returnfalse;}edge[v][w]=edge[w][v]=1;//因为是无向图，对称的，存在边赋为1；returntrue;}//删除顶点的高效方法boolremoveVertex(constType&v){inti=getVertexIndex(v);if(i==-1){returnfalse;}vertexList[i]=vertexList[curVertices-1];intedgeCount=0;for(intk=0;k<curVertices;k++){if(edge[i][k]!=0){//统计删除该行的边数edgeCount++;}}//删除行for(intj=0;j<curVertices;j++){edge[i][j]=edge[curVertices-1][j];}//删除列for(j=0;j<curVertices;j++){edge[j][i]=edge[j][curVertices-1];}curVertices--;curEdges-=edgeCount;returntrue;}/*//删除顶点用的是数组一个一个移动的方法，效率太低。boolremoveVertex(constType&v){inti=getVertexIndex(v);if(i==-1){returnfalse;}for(intk=i;k<curVertices-1;++k){vertexList[k]=vertexList[k+1];}intedgeCount=0;for(intj=0;j<curVertices;++j){if(edge[i][j]!=0)edgeCount++;}for(intk=i;k<curVertices-1;++k){for(intj=0;j<curVertices;++j){edge[k][j]=edge[k+1][j];}}for(intk=i;k<curVertices-1;++k){for(intj=0;j<curVertices;++j){edge[j][k]=edge[j][k+1];}}curVertices--;curEdges-=edgeCount;returntrue;}*/boolremoveEdge(constType&v1,constType&v2){intv=getVertexIndex(v1);intw=getVertexIndex(v2);if(v==-1||w==-1){//判断要删除的边是否在当前顶点内returnfalse;//顶点不存在}if(edge[v][w]==0){//这个边根本不存在，没有必要删returnfalse;}edge[v][w]=edge[w][v]=0;//删除这个边赋值为0，代表不存在；curEdges--;returntrue;}intgetFirstNeighbor(constType&v){inti=getVertexIndex(v);if(i==-1){return-1;}for(intcol=0;col<curVertices;col++){if(edge[i][col]!=0){returncol;}}return-1;}intgetNextNeighbor(constType&v,constType&w){inti=getVertexIndex(v);intj=getVertexIndex(w);if(i==-1||j==-1){return-1;}for(intcol=j+1;col<curVertices;col++){if(edge[i][col]!=0){returncol;}}return-1;}public:voidshowGraph()const{if(curVertices==0){cout<<"NulGraph"<<endl;return;}for(inti=0;i<curVertices;i++){cout<<vertexList[i]<<"";}cout<<endl;for(i=0;i<curVertices;i++){for(intj=0;j<curVertices;j++){cout<<edge[i][j]<<"";}cout<<vertexList[i]<<endl;}}intgetVertexIndex(constType&v)const{for(inti=0;i<curVertices;i++){if(vertexList[i]==v){returni;}}return-1;}private:Type*vertexList;//存放顶点的数组int**edge;//存放顶点关系的矩阵用边表示};///////////////////////////////////////////////////////////////下面是邻接表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)、Graph.cpp

#include"Graph.h"intmain(void){GraphMtx<char>gm;//邻接矩阵gm.insertVertex('A');//插入顶点gm.insertVertex('B');gm.insertVertex('C');gm.insertVertex('D');gm.insertEdge('A','B');//插入边gm.insertEdge('A','D');gm.insertEdge('B','C');gm.insertEdge('C','D');cout<<gm.getFirstNeighbor('A')<<endl;//Bcout<<gm.getNextNeighbor('A','B')<<endl;//Dgm.showGraph();gm.removeEdge('A','B');gm.removeVertex('B');cout<<"-----------------------------------------------------------------"<<endl;gm.showGraph();///////////////////////////////////////////////////////////////////////////////////////////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、邻接多重表

是一个十字交叉链的形式；在很大程度上节省了空间，还是要对链表的操作很熟悉；