使用邻接矩阵实现的图结构（添加深度优先搜索）

使用邻接矩阵实现的图结构（添加深度优先搜索）
这次我使用了深度优先搜索。以前的文章如下所示。这个算法困难啊，调试了我好一段时间。下面就是我扩充的深度优先搜索的内容。以前发布的程序有诸多不足，还有几个致命的错误，我就不解释了，这个是优化了的，比以前的好了些。我以前写的图结构：http://student.csdn.net/space.php?uid=999749&do=blog&id=51129

下面是我的JGraph.h代码：

/*----------------------------------------------------------------------------
蒋轶民制作：E-mail：[e-mail]
------------------------------------------------------------------------------
文件名：JGraph.h
------------------------------------------------------------------------------
作用：这是使用邻接矩阵制作的图状结构，基本实现了图的创建操作。
------------------------------------------------------------------------------
调用规范：无
/*--------------------------------------------------------------------------*/
//条件编译
#ifndef_JGRAPH_H_
#define_JGRAPH_H_
/*--------------------------------------------------------------------------*/
//头文件
#include<limits.h>

//定义的宏
#defineINFINITYINT_MAX
#defineMAX_VERTEX_NUM20

/*--------------------------------------------------------------------------*/
//定义一系列类型
enumGraphKind{DG,DN,UDG,UDN};//图的类型枚举
typedefunsignedintVRType;
typedefcharInfoType;
typedefstruct
{
VRTypeadj;//顶点关系类型
InfoType*info;//弧的信息
}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

//图的定义
template<typenameCustomType>
classJMatrixGraph
{
public:
JMatrixGraph():vexnum(0),arcnum(0){}//默认构造函数
voidCreateGraph(GraphKindinputKind);//创建图
voidDFSTraverse(bool(*Visit)(intv));//深度优先搜索遍历
private:
voidCreateDG(void);//创建有向图
voidCreateDN(void);//创建有向网
voidCreateUDG(void);//创建无向图
voidCreateUDN(void);//创建无向网
voidDepthFirstSearch(intv,bool(*Visit)(intv));//深度优先搜索
intFirstAdjVex(intv);//返回第v个顶点的第一个邻接点
intNextAdjVex(intv,intw);//返回第v个顶点的下一个邻接点
CustomTypevexs[MAX_VERTEX_NUM];//顶点向量
AdjMatrixarcs;//邻接矩阵
intvexnum,arcnum;//图的顶点数和弧数
GraphKindkind;//图的种类标志
boolvisited[MAX_VERTEX_NUM];//访问标志数组
};
/*--------------------------------------------------------------------------*/
//创建图
template<typenameCustomType>
voidJMatrixGraph<CustomType>::CreateGraph(GraphKindinputKind)
{
switch(inputKind)
{
caseDG:returnCreateDG();
caseDN:returnCreateDN();
caseUDG:returnCreateUDG();
caseUDN:returnCreateUDN();
}
}

template<typenameCustomType>//创建有向图
voidJMatrixGraph<CustomType>::CreateDG(void)
{
inti,j,k;
intv1,v2,incInfo;
cout<<"输入顶点个数：/n";
cin>>vexnum;
cout<<"输入弧的个数：/n";
cin>>arcnum;
if(arcnum>vexnum*(vexnum-1)*0.5f)
{
cout<<"输入错误！因为不满足n(n-1)/2的条件。/n";
return;
}
cout<<"输入弧的信息（0表示忽略）：/n";
cin>>incInfo;
for(i=0;i<vexnum;i++)
{
cout<<"请输入第"<<i+1<<"个顶点的内容：/n";
cin>>vexs[i];
}
for(i=0;i<vexnum;i++)
{
for(j=0;j<vexnum;j++)
{
arcs[i][j].adj=0;
arcs[i][j].info=NULL;
}
}
for(k=0;k<arcnum;k++)
{
cout<<"请输入第"<<k+1<<"边连接的两个顶点。/n";
cin>>v1>>v2;
arcs[v1-1][v2-1].adj=1;
if(incInfo!=0)
{
cout<<"输入弧的信息，以字符串的形式存储。/n";
cin>>arcs[v1-1][v2-1].info;
}
}//这里设置断点，下同
}

template<typenameCustomType>//创建有向网
voidJMatrixGraph<CustomType>::CreateDN(void)
{
inti,j,k;
intv1,v2,incInfo;
intw;
cout<<"输入顶点个数：/n";
cin>>vexnum;
cout<<"输入弧的个数：/n";
cin>>arcnum;
if(arcnum>vexnum*(vexnum-1)*0.5f)
{
cout<<"输入错误！因为不满足n(n-1)/2的条件。/n";
return;
}
cout<<"输入弧的信息（0表示忽略）：/n";
cin>>incInfo;
for(i=0;i<vexnum;i++)
{
cout<<"请输入第"<<i+1<<"个顶点的内容：/n";
cin>>vexs[i];
}
for(i=0;i<vexnum;i++)
{
for(j=0;j<vexnum;j++)
{
arcs[i][j].adj=INFINITY;
arcs[i][j].info=NULL;
}
}
for(k=0;k<arcnum;k++)
{
cout<<"请输入第"<<k+1<<"边连接的两个顶点和权值。/n";
cin>>v1>>v2>>w;
arcs[v1-1][v2-1].adj=w;
if(incInfo!=0)
{
cout<<"输入弧的信息，以字符串的形式存储。/n";
cin>>arcs[v1-1][v2-1].info;
}
}
}

template<typenameCustomType>//创建无向图
voidJMatrixGraph<CustomType>::CreateUDG(void)
{
inti,j,k;
intv1,v2,incInfo;
cout<<"输入顶点个数：/n";
cin>>vexnum;
cout<<"输入弧的个数：/n";
cin>>arcnum;
if(arcnum>vexnum*(vexnum-1)*0.5f)
{
cout<<"输入错误！因为不满足n(n-1)/2的条件。/n";
return;
}
cout<<"输入弧的信息（0表示忽略）：/n";
cin>>incInfo;
for(i=0;i<vexnum;i++)
{
cout<<"请输入第"<<i+1<<"个顶点的内容：/n";
cin>>vexs[i];
}
for(i=0;i<vexnum;i++)
{
for(j=0;j<vexnum;j++)
{
arcs[i][j].adj=0;
arcs[i][j].info=NULL;
}
}
for(k=0;k<arcnum;k++)
{
cout<<"请输入第"<<k+1<<"边连接的两个顶点。/n";
cin>>v1>>v2;
arcs[v1-1][v2-1].adj=1;
cout<<"该元素的值是："<<arcs[v1-1][v2-1].adj;
if(incInfo!=0)
{
cout<<"输入弧的信息，以字符串的形式存储。/n";
cin>>arcs[v1-1][v2-1].info;
}
arcs[v2-1][v1-1].adj=arcs[v1-1][v2-1].adj;
}
}

template<typenameCustomType>//创建无向网
voidJMatrixGraph<CustomType>::CreateUDN(void)
{
inti,j,k;
intv1,v2,incInfo;
intw;
cout<<"输入顶点个数：/n";
cin>>vexnum;
cout<<"输入弧的个数：/n";
cin>>arcnum;
if(arcnum>vexnum*(vexnum-1)*0.5f)
{
cout<<"输入错误！因为不满足n(n-1)/2的条件。/n";
return;
}
cout<<"输入弧的信息（0表示忽略）：/n";
cin>>incInfo;
for(i=0;i<vexnum;i++)
{
cout<<"请输入第"<<i+1<<"个顶点的内容：/n";
cin>>vexs[i];
}
for(i=0;i<vexnum;i++)
{
for(j=0;j<vexnum;j++)
{
arcs[i][j].adj=INFINITY;
arcs[i][j].info=NULL;
}
}
for(k=0;k<arcnum;k++)
{
cout<<"请输入第"<<k+1<<"边连接的两个顶点和权值。/n";
cin>>v1>>v2>>w;
arcs[v1-1][v2-1].adj=w;
if(incInfo!=0)
{
cout<<"输入弧的信息，以字符串的形式存储。/n";
cin>>arcs[v1-1][v2-1].info;
}
arcs[v2-1][v1-1].adj=arcs[v1-1][v2-1].adj;
}
}
/*--------------------------------------------------------------------------*/
//深度优先搜索遍历
template<typenameCustomType>
voidJMatrixGraph<CustomType>::DFSTraverse(bool(*Visit)(intv))
{
intv;
for(v=0;v<vexnum;v++)visited[v]=false;
for(v=0;v<vexnum;v++)
if(!visited[v])DepthFirstSearch(v,Visit);
}
/*--------------------------------------------------------------------------*/
//深度优先搜索
template<typenameCustomType>
voidJMatrixGraph<CustomType>::DepthFirstSearch(intv,bool(*Visit)(intv))
{
visited[v]=true;Visit(v);
intw;
for(w=FirstAdjVex(v);w>=0;w=NextAdjVex(v,w))
if(!visited[w])DepthFirstSearch(w,Visit);
}
/*--------------------------------------------------------------------------*/
//返回第v个顶点的第一个邻接点
template<typenameCustomType>
intJMatrixGraph<CustomType>::FirstAdjVex(intv)
{
inti;
for(i=0;i<vexnum;i++)
if(arcs[v][i].adj!=0)returni;//这里只对无向图进行计算
return-1;
}
/*--------------------------------------------------------------------------*/
//返回第v个顶点的下一个邻接点
template<typenameCustomType>
intJMatrixGraph<CustomType>::NextAdjVex(intv,intw)
{
inti;
for(i=w+1;i<vexnum;i++)
if(arcs[v][i].adj!=0)returni;//这里只对无向图进行计算
return-1;
}
#endif

下面是我对《数据结构（严蔚敏版）》168页的G4图进行深度优先搜索。MainFrame.h文件如图所示。

/*----------------------------------------------------------------------------
蒋轶民制作：E-mail：[e-mail]
------------------------------------------------------------------------------
文件名：MainFrame.h
------------------------------------------------------------------------------
作用：验证图结构是否创建成功。
/*--------------------------------------------------------------------------*/
//头文件
#include<iostream>
#include"JGraph.h"

usingnamespacestd;

boolVisitFunc(intv)
{
cout<<"-----------深度优先搜索------------/n";
cout<<"访问第"<<v+1<<"个顶点/n";
returntrue;
}

//程序的入口
intmain(intargc,char**argv)
{
JMatrixGraph<char>jmg;
jmg.CreateGraph(UDG);
jmg.DFSTraverse(VisitFunc);
return0;
}

程序的截图如图所示：

以后还会实现广度优先搜索和更多的功能的！