1、图

(1)、图是一种非线性结构；主要由顶点和边构成；

(2)、<> 代表有向图，( )代表无向图

(3)、无向图有N个顶点时，最多有N*(N-1)/2条边；有向图最多有N*(N-1)条边;

(4)、权：边上具有相关的数，带权图叫做网络;

(5)、邻接顶点: 与其接触边上的顶点；

(6)、度：与顶点V关联的边数；有向图中度 = 出度 + 入度；

(7)、简单路径：路径上各顶点互不重复，

(8)、回路/环：路径上第一个顶点与最后一个顶点重合；

(9)、连通图/强连通图：各顶点之间有边联系，有向图，双路径存在叫做强连通图；

(10)、生成树：是无向连通图的极小连通子图，若有N个顶点，则生成树由N-1条边构成！

2、图的邻接矩阵

(1)、邻接矩阵模型如下：

就是将图的多对多的非线性结构用矩阵的方式表示；

我们必须知道：

(1)、会由矩阵来恢复图；

(2)、第一个邻接顶点：从列开始处，第一个边

(3)、下一个邻接顶点：给2个参数，第一个参数表示是谁的下一个邻接顶点，第二个表示从当前顶点开始其后的第一条边；

(4)、其顶点存放在数组空间中；

(5)、顶点之间的关系通过矩阵来表示边；

存储结构：

intmaxVertices;//最大顶点数intcurVertices;//当前顶点数intcurEdges;//当前边数//用的是C++的继承Type*vertexList;//存放顶点的数组int**edge;//存放顶点关系的矩阵用边表示

存储模型如下：

3、图的实现方法

均用C++实现；并且父类给了接口，子类继承实现即可；方便对不同的存储结构的编写；

核心方法，删除顶点：

(1)、第一种方法实现：

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;}

以上存在数组的大量移动，效率太低;

(2)、第二种方法的实现：

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;}

第二种方法甚好，将要删除的顶点(连边一起删除),用最后一个元素(行/列)去覆盖删除的那个即可，之间的关系不变，但是就避免了大量移动，一次覆盖就好，效率极大！！！

模型如下：

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>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;//存放顶点关系的矩阵用边表示};#endif

(2)、测试代码：

#include"Graph.h"#defineVERTEX_SIZE4intmain(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();/*用矩阵关系直接初始化图，没啥意思intmtx[VERTEX_SIZE][VERTEX_SIZE]={{0,1,0,1},{1,0,1,0},{0,1,0,1},{1,0,1,0},};GraphMtx<int>gm(mtx,VERTEX_SIZE);gm.showGraph();*/return0;}

(3)测试结果：

测试的图：