有向图的路径问题.doc

实验五——有向图的路径问题

问题描述
对于有向图G=(V,E),任意Vi，Vj∈V（Vi≠Vj），判断从顶点Vi到顶点Vj是否存在路径。
基本要求
设计图的存储结构
设计算法完成问题求解
设计存储从Vi到Vj路径的存储结构
输入：图可以初始化方式获取、从键盘读入或从文件读入
存储结构
structArcNode//定义边表结点
{
intadjvex;//其代表邻接点域，即是结点数组下标
ArcNode*next;
}
structVertexNode//定义顶点表结点
{
Tvertex;
ArcNode*firstedge;
};
核心函数初始化函数
ALGraph<T>::ALGraph(Ta[],intn,inte)
{
vertexNum=n;
arcNum=e;
for(inti=0;i<MaxSize;i++)
visited[i]=0;
for(i=0;i<vertexNum;i++)//初始化顶点表
{
adjlist[i].vertex=a[i];
adjlist[i].firstedge=NULL;
}
for(intk=0;k<arcNum;k++)
{
inti,j;
cout<<"请输入两组数字："<<endl;
cin>>i>>j;
ArcNode*s;
s=newArcNode;
s->adjvex=j;//输入依附的两个顶点的序号
s->next=adjlist[i].firstedge;
adjlist[i].firstedge=s;//头插法
}
}

判断两点是否存在路径
intALGraph<T>::DFS1(inti,intj)
{
intstack[MaxSize];
inttop;
intyes;
intvisited3[MaxSize];
for(intk=0;k<vertexNum;k++)
visited3[k]=0;
top=-1;
visited[i]=1;yes=0;
stack[++top]=i;
while(top!=-1&&yes==0)
{
i=stack[top];
ArcNode*p;
p=adjlist[i].firstedge;
while(p&&yes==0)
{
intt;
t=p->adjvex;
//cout<<adjlist[t].vertex<<"";
if(t==j)
yes=1;
elseif(visited3[t]==0)
{
visited3[t]=1;
stack[++top]=t;
}
elsep=p->next;

}
//if(!p)top--;//注意这里的p值代表的是顶点表的firstedge,其始终在，这行代码将使程序陷入是循环，无法得出正确的结果
}
returnyes;
}
源程序
#include<iostream.h>
//#include<string.h>
constintMaxSize=10;
//template<classT>
structArcNode//定义边表结点
{
intadjvex;//其代表邻接点域，即是结点数组下标
ArcNode*next;
};
template<classT>
structVertexNode//定义顶点表结点
{
Tvertex;
ArcNode*firstedge;
};
template<classT>
classALGraph
{
public:
ALGraph(Ta[],intn,inte);
//~ALGraph();//析构函数可以由系统自己调用，如果定义了，没有写出其算，就容易出错，thiscall----
voidDFSTraverse(intv);
voidBFSTraverse(intv);
voidDFS(intv);
intDFS1(inti,intj);
private:
VertexNode<T>adjlist[MaxSize];//定义结点数组，存放顶点,注意vertexNode后面的<T>不要忘记了，c++模板机制
intvertexNum,arcNum;
intvisited[MaxSize];
};
template<classT>
ALGraph<T>::ALGraph(Ta[],intn,inte)
{
vertexNum=n;
arcNum=e;
for(inti=0;i<MaxSize;i++)
visited[i]=0;
for(i=0;i<vertexNum;i++)//初始化顶点表
{
adjlist[i].vertex=a[i];
adjlist[i].firstedge=NULL;
}
for(intk=0;k<arcNum;k++)
{
inti,j;
cout<<"请输入两组数字："<<en