首先，我们先看一下什么是图，图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G(V，E)，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

一、相关术语

顶点(Vertex)：在图中的数据元素。 边：图中，任意两顶点之间都可能有关系，顶点之间的逻辑关系用边来表示。 无向边(Edge)：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对(Vi,Vj)来表示。 无向边：若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称为弧(Arc)。记作<Vi,Vj>，比如连接顶点A到D的有向边就是弧，A是弧尾，D是弧头，<A,D>表示弧，因为他是有方向的，所以不能写成<D,A>。 无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。 有向完全图：在有向图中，如果任意两个顶点之间都存在方向上互为相反的两条弧，则称该图为有向完全图。 有很少条边或弧的图称为稀疏图，反之称为稠密图。 权(Weight)：与图的边或弧相关的数叫做权。 网(Network)：带权的图通常称为网。 连通图：在无向图中，如果从一个顶点到另外一个顶点有路径，则称两个顶点之间是连通的。如果对于图中任意两个顶点之间哦都是连通的，则称图为连通图。

二、图的基本实现

ADT Graph Data 顶点的有穷非空集合和边的集合 Operation CreateGraph(*G,V,VR):按照顶点集V和边弧VR的定义构造图G。 DestoryGraph(*G):图G若存在则销毁。 LocateVex(G,char u):图中存在顶点u，则返回图中的位置。 GetVex(G,int v):返回图中顶点v的值。 PutVex(G,int v,char value):将图中顶点v赋值value。 FirstAdjVex(G,char v):返回顶点v的一个邻接顶点，若顶点在图中无邻接顶点，返回空。 NextAdjVex(G,char v,char w):返回顶点v相对于顶点w的下一个邻接顶点，若w是v的最有一个邻接点，则返回“空”。 InsertVex(G,char v):在图中增加新顶点v。 DeleteVex(G,char v):删除图中顶点v以及相关的弧。 InsertArc(G,char v,char w):在图中增加弧<v,w>，若图为无向图，还需要增添对称弧<w,v>。 DeleteArc(G,char v,char w):在图中删除弧<v,w>,若图为无向图，还要删除对称弧<w,v>。 DFSTraverse(G):对图中进行深度优先遍历，在遍历过程中对每个顶点调用。 BFSTraverse(G):对图中进行广度优先遍历，在遍历过程中对每个顶点调用。 endADT

三、代码实现

接下来就以无向图以及邻接矩阵为例，进行图的相关代码的实现。

1、数据的相关定义以及初始化的过程

#include<iostream> #include<queue> using namespace std; #define Maxvex 100 //记录图里面的最大顶点数 #define Infinity 65535 //用65535来表示 ∞ typedef struct { char Vexs[Maxvex]; //VExs数组记录顶点，为顶点表 int arc[Maxvex][Maxvex]; //邻接矩阵，记录顶点之间的边 int Vertexes,Edges; //Vertexes记录顶点数，Edges记录边的数量 }MGraph; MGraph g; //定义图的全局变量

这里我们的MGraph是一个全局变量，所以在后面的函数中就省略了形参里面G的定义。

2、图的创建

void CreateGraph() //创建图,建立无向表，由于已经定义了全局变量，所以就不需要写形参。 { int i,j,k,w; cin>>g.Vertexes>>g.Edges; //首先输入顶点数和边数 for(i=0;i<g.Vertexes;i++) cin>>g.Vexs[i]; for(i=0;i<g.Vertexes;i++) for(j=0;j<g.Vertexes;j++) g.arc[i][j]=Infinity; //初始化 for(k=0;k<g.Edges;k++) { cin>>i>>j>>w; g.arc[i][j]=w; //w表示权重 g.arc[j][i]=w; //无向图，矩阵对称 }

3、图的顶点以及弧的相关操作

由于这些操作比较简单，这里就直接给出代码。

void DestoryGraph(MGraph g) //销毁图，若有图g，则销毁。 { bool flag=false; for(int i=0;i<g.Vertexes;i++) for(int j=0;j<g.Vertexes;j++) if(g.arc[i][j]!=Infinity) { g.arc[i][j]=Infinity; flag=true; } if(flag) //如果邻接矩阵有边，则说明这是一个图，就需要把他的顶点全部删除。如果邻接矩阵没有边，则不需要删除顶点。 for(int i=0;i<g.Vertexes;i++) g.Vexs[i]=0; } int LocateVex(char u) //若图中存在顶点u，则返回图中的位置 { bool flag=false; int i; for(i=0;i<g.Vertexes;i++) if(g.Vexs[i]==u) { flag=true; break; } if(flag) return i; else return 0 ; } char GetVex(int v) //返回图中顶点v的值 { return g.Vexs[v]; } void PutVex(int v,char value) //将图中顶点v赋值value { g.Vexs[v]=value; } char FirstAdjVex(char v) //返回顶点v的一个邻接顶点，若顶点在图中无邻接顶点，返回空 { int i,j; bool flag=false; for(i=0;i<g.Vertexes;i++) if(g.Vexs[i]==v) break; for(j=0;j<g.Vertexes;j++) if(g.arc[i][j]!=Infinity) { flag=true; break; } if(flag) return g.Vexs[j]; else return 0; } char NextAdjVex(char v,char w) //返回顶点v相对于顶点w的下一个邻接顶点，若w是v的最有一个邻接点，则返回“空”。 { int j,i,k; bool flag=false; for(i=0;i<g.Vertexes;i++) if(g.Vexs[i]==v) break; for(j=0;j<g.Vertexes;j++) if(g.Vexs[j]==w) break; for(k=0;k<g.Vertexes;k++) if(g.arc[i][k]!=Infinity&&k!=j) { return k; break; } } void InsertVex(char v) //在图中增加新顶点v { g.Vexs[g.Vertexes]=v; for(int i=0;i<g.Vertexes;i++) g.arc[g.Vertexes][i]=g.arc[i][g.Vertexes]=Infinity; g.Vertexes++; } void DeleteVex(char v) //删除图中顶点v以及相关的弧 { int i; for(i=0;i<g.Vertexes;i++) if(g.Vexs[i]==v) break; for(int j=0;j<g.Vertexes;j++) g.arc[j][i]=g.arc[i][j]=Infinity; for(int j=i;j<g.Vertexes-1;j++) g.Vexs[j]=g.Vexs[j+1]; g.Vertexes--; } void InsertArc(char v,char w) //在图中增加弧<v,w>，若图为无向图，还需要增添对称弧<w,v> { int i,j; for(i=0;i<g.Vertexes;i++) if(g.Vexs[i]==v) break; for(j=0;j<g.Vertexes;j++) if(g.Vexs[j]==w) break; g.arc[i][j]=g.arc[j][i]=1; } void DeleteArc(char v,char w) //在图中删除弧<v,w>,若图为无向图，还要删除对称弧<w,v> { int i,j; for(i=0;i<g.Vertexes;i++) if(g.Vexs[i]==v) break; for(j=0;j<g.Vertexes;j++) if(g.Vexs[j]==w) break; g.arc[i][j]=g.arc[j][i]=Infinity; }

4、图的深搜遍历

要对图进行深度优先搜索，首先要先知道，深度优先搜索是什么，那深度优先搜素是什么呢？ 如图所示，假设你需要完成一个任务假设，要求你在如图这样的一个迷宫中，从顶点A开始要走遍所有的图顶点并作上标记，注意不是简单地看着这样的平面图走哦，而是如同现实般地在只有高墙和通道的迷宫中去完成任务。 很显然我们是需要策略的，否则在这四通八达的通道中乱窜，要想完成任务那就只能是碰运气。如果你学过深度优先遍历，这个任务就不难完成了。 首先我们从顶点A开始，做上表示走过的记号后，面前有两条路，通向B和F，我们给自己定一个原则，在没有碰到重复顶点的情况下，始终是向右手边走，于是走到了B顶点。整个行路过程，可参看右图。此时发现有三条分支，分别通向顶点C、I、G，右手通行原则，使得我们走到了C顶点。就这样，我们一直顺着右手通道走，一直走到F顶点。当我们依然选择右手通道走过去后，发现走回到顶点A了，因为在这里做了记号表示已经走过。此时我们退回到顶点F，走向从右数的第二条通道，到了G顶点，它有三条通道，发现B和D都已经是走过的，于是走到H，当我们面对通向H的两条通道D和E时，会发现都已经走过了。 此时我们是否已经遍历了所有顶点呢？没有。可能还有很多分支的顶点我们没有走到，所以我们按原路返回。在顶点H处，再无通道没走过，返回到G，也无未走过通道，返回到F，没有通道，返回到E，有一条通道通往H的通道，验证后也是走过的，再返回到顶点D，此时还有三条道未走过，一条条来，H走过了，G走过了，I，哦，这是一个新顶点，没有标记，赶快记下来。继续返回，直到返回顶点A，确认你已经完成遍历任务，找到了所有的9个顶点。 反应快的同学一定会感觉到，深度优先遍历其实就是一个递归的过程，如果再敏感一些，会发现其实转换成如右图后，就像是一棵树的前序遍历，没错，它就是。它从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。事实上，我们这里讲到的是连通图，对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

void DFS(int i) { isvisited[i]=true; cout<<g.Vexs[i]<<endl; for(int j=0;j<g.Vertexes;j++) if(g.arc[i][j]!=Infinity&&!isvisited[j]) DFS(j); } void DFSTraverse() //对图中进行深度优先遍历，在遍历过程中对每个顶点调用 { cout<<"DFS:"<<endl; for(int i=0;i<g.Vertexes;i++) isvisited[i]=false; for(int i=0;i<g.Vertexes;i++) if(!isvisited[i]) DFS(i); }

5、广度优先遍历

那什么又是广度优先遍历呢？ 如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。我们将图7-5-3的第一幅图稍微变形，变形原则是顶点A放置在最上第一层，让与它有边的顶点B、F为第二层，再让与B和F有边的顶点C、I、G、E为第三层，再将这四个顶点有边的D、H放在第四层，如第二幅图所示。此时在视觉上感觉图的形状发生了变化，其实顶点和边的关系还是完全相同的。 那么话不多说，已经理解了原理以后我们就可以将代码写出来。

void BFSTraverse() //对图中进行广度优先遍历，在遍历过程中对每个顶点调用 { queue<int>q; bool visited[g.Vertexes]; cout<<endl<<endl<<"BFS:"<<endl; for(int i=0;i<g.Vertexes;i++) visited[i]=false; for(int i=0;i<g.Vertexes;i++) { if(!visited[i]) { visited[i]=true; cout<<g.Vexs[i]<<endl; q.push(i); while(q.empty()==false) { i=q.front(); q.pop(); for(int j=0;j<g.Vertexes;j++) { if(g.arc[i][j]!=Infinity&&!visited[j]) { visited[j]=true; cout<<g.Vexs[j]<<endl; q.push(j); } } } } } }

以上是我们关于无向图的内容的整理，其中也用到了数学上的邻接矩阵。 还有下面的一组数据，用做测试。 9 15 ABCDEFGHI 0 1 1 1 2 1 2 3 1 3 4 1 4 5 1 5 8 1 8 7 1 7 3 1 7 4 1 3 6 1 2 6 1 1 6 1 0 5 1 3 8 1 1 8 1

由于是第一次写博客，多有缺陷以及不足，请多多包含。希望各位大佬给我这个菜菜的码农一点包容，有什么问题也请大家指正。