1、连通图和非连通图

连通图：任意的一个顶点到任意的另外一个顶点都有着相应的路径所能够到达。

非连通图：只要找出了有一个顶点不能够到达另外一个顶点。

2、遍历

对于连通图来说，通过DFS或BFS就可以完成遍历；

对于非连通图来说，就得从每个顶点出发进行搜索，每一次的从一个新的顶点出发访问，每个顶点都要开始搜索一遍。

3、非连通图的遍历算法

(1)、不可取的算法：没有必要将非连通图生成森林，在由森林生成我们的遍历树，然后再进行树形结构的访问。

(2)、比较好的算法：直接调动我们之前编写好的DFS()函数；只要没有访问的顶点，我们就由该顶点出发进行深度优先遍历，这样就最终把整个非连通图就遍历完成。

(3)强连通图：针对有向图，有A-->B的边，一定也有B-->A的边。

(4)、遍历算法：

voidcomponents(){//非连通图的遍历intn=Graph<Type>::getCurVertex();bool*visit=newbool[n];for(inti=0;i<n;i++){visit[i]=false;}for(i=0;i<n;i++){//对每个顶点都看一下，是否访问过。4if(!visit[i]){DFS(getValue(i),visit);}}delete[]visit;}

4、完整代码、测试代码、测试结果

(1)、完整代码

#ifndef_GRAPH_H_#define_GRAPH_H_#include<iostream>#include<queue>usingnamespacestd;#defineVERTEX_DEFAULT_SIZE20template<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;//显示图virtualTypegetValue(intindex)const=0;public:virtualvoidDFS(constType&v)=0;//深度优先virtualvoidBFS(constType&v)=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;}public:TypegetValue(intindex)const{returnvertexList[index];}voidDFS(constType&v){intn=Graph<Type>::getCurVertex();bool*visit=newbool[n];for(inti=0;i<n;i++){visit[i]=false;}DFS(v,visit);delete[]visit;}voidBFS(constType&v){intn=Graph<Type>::getCurVertex();bool*visit=newbool[n];for(inti=0;i<n;i++){visit[i]=false;}cout<<v<<"-->";intindex=getVertexIndex(v);visit[index]=true;queue<int>q;//队列中存放的是顶点下标;q.push(index);intw;while(!q.empty()){index=q.front();q.pop();w=getFirstNeighbor(getValue(index));while(w!=-1){if(!visit[w]){cout<<getValue(w)<<"-->";visit[w]=true;q.push(w);}w=getNextNeighbor(getValue(index),getValue(w));}}delete[]visit;}voidcomponents(){//非连通图的遍历intn=Graph<Type>::getCurVertex();bool*visit=newbool[n];for(inti=0;i<n;i++){visit[i]=false;}for(i=0;i<n;i++){if(!visit[i]){DFS(getValue(i),visit);}}delete[]visit;}protected:voidDFS(constType&v,bool*visit){cout<<v<<"-->";intindex=getVertexIndex(v);visit[index]=true;intw=getFirstNeighbor(v);while(w!=-1){if(!visit[w]){DFS(getValue(w),visit);}w=getNextNeighbor(v,getValue(w));}}private:Type*vertexList;//存放顶点的数组int**edge;//存放边关系的矩阵};#endif

(2)、测试代码

#include"Graph3.h"intmain(void){GraphMtx<char>gm;gm.insertVertex('A');gm.insertVertex('B');gm.insertVertex('C');//B的第一个邻接顶点是C，gm.insertVertex('D');gm.insertVertex('E');gm.insertVertex('F');gm.insertVertex('G');gm.insertVertex('H');gm.insertVertex('I');gm.insertVertex('J');gm.insertVertex('K');gm.insertVertex('L');gm.insertVertex('M');gm.insertEdge('A','B');gm.insertEdge('A','C');gm.insertEdge('A','F');gm.insertEdge('A','L');gm.insertEdge('B','M');gm.insertEdge('L','J');gm.insertEdge('L','M');gm.insertEdge('J','M');gm.insertEdge('D','E');gm.insertEdge('G','H');gm.insertEdge('G','I');gm.insertEdge('G','K');gm.insertEdge('H','K');gm.showGraph();cout<<"------------------------------------------------"<<endl;gm.DFS('A');cout<<"Nul."<<endl;gm.BFS('A');cout<<"Nul."<<endl;gm.components();cout<<"Nul."<<endl;return0;}

(3)、测试结果

测试图的模型：