有向图的路径问题

《有向图的路径问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验五——有向图的路径问题1.问题描述对于有向图G=(V,E),任意Vi，Vj∈V（Vi≠Vj），判断从顶点Vi到顶点Vj是否存在路径。2.基本要求（1）设计图的存储结构（2）设计算法完成问题求解（3）设计存储从Vi到Vj路径的存储结构（4）输入：图可以初始化方式获取、从键盘读入或从文件读入3.存储结构structArcNode//定义边表结点{intadjvex;//其代表邻接点域，即是结点数组下标ArcNode*next;}structVertexNode//定义顶点表结点{Tvertex;Ar

2、cNode*firstedge;};核心函数初始化函数ALGraph::ALGraph(Ta[],intn,inte){vertexNum=n;arcNum=e;for(inti=0;i

3、"<>i>>j;ArcNode*s;s=newArcNode;s->adjvex=j;//输入依附的两个顶点的序号s->next=adjlist[i].firstedge;adjlist[i].firstedge=s;//头插法}}判断两点是否存在路径intALGraph::DFS1(inti,intj){intstack[MaxSize];inttop;intyes;intvisited3[MaxSize];for(intk=0;k

4、ed3[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<

5、sep=p->next;}//if(!p)top--;//注意这里的p值代表的是顶点表的firstedge,其始终在，这行代码将使程序陷入是循环，无法得出正确的结果}returnyes;}1.源程序#include//#includeconstintMaxSize=10;//templatestructArcNode//定义边表结点{intadjvex;//其代表邻接点域，即是结点数组下标ArcNode*next;};template

6、assT>structVertexNode//定义顶点表结点{Tvertex;ArcNode*firstedge;};templateclassALGraph{public:ALGraph(Ta[],intn,inte);//~ALGraph();//析构函数可以由系统自己调用，如果定义了，没有写出其算，就容易出错，thiscall----voidDFSTraverse(intv);voidBFSTraverse(intv);voidDFS(intv);intDFS1(inti,in

7、tj);private:VertexNodeadjlist[MaxSize];//定义结点数组，存放顶点,注意vertexNode后面的不要忘记了，c++模板机制intvertexNum,arcNum;intvisited[MaxSize];};templateALGraph::ALGraph(Ta[],intn,inte){vertexNum=n;arcNum=e;for(inti=0;i

8、rtexNum;i++)//初始化顶点表{adjlist[i].vertex=a[i];adjlist[i].firstedge=NULL;}for(intk=0;k>i>>j;ArcNode*s;s=newArcNode;s->adjvex=j;//输入依附的两个顶点的序号s->next=adjlist[i].firstedge;adjlist[i].firstedge=s