有向图的路径问题

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

1.

问题描述

对于有向图G=(V,E),任意Vi，Vj∈V（Vi≠Vj），判断从顶点Vi到顶点Vj是否存在路径。

2.

基本要求

（1） 设计图的存储结构 （2） 设计算法完成问题求解

（3） 设计存储从Vi到Vj路径的存储结构

（4） 输入：图可以初始化方式获取、从键盘读入或从文件读入

3.

存储结构

struct ArcNode //定义边表结点

{

int adjvex; //其代表邻接点域，即是结点数组下标 ArcNode *next; }

struct VertexNode //定义顶点表结点 {

T vertex;

ArcNode *firstedge; };

核心函数初始化函数

ALGraph::ALGraph(T a[],int n,int e) {

vertexNum=n; arcNum=e;

for(int i=0;i

for(i=0;i

adjlist[i].vertex=a[i]; adjlist[i].firstedge=NULL; }

for(int k=0;k

int i,j;

cout<<\请输入两组数字：\ cin>>i>>j; ArcNode *s;

s=new ArcNode;

s->adjvex=j; //输入依附的两个顶点的序号 s->next=adjlist[i].firstedge;

adjlist[i].firstedge=s; //头插法 } }

判断两点是否存在路径

int ALGraph::DFS1(int i,int j) {

int stack[MaxSize]; int top; int yes;

int visited3[MaxSize];

for(int k=0;k

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) {

int t;

t=p->adjvex;

//cout<

else if(visited3[t]==0) {

visited3[t]=1; stack[++top]=t; }

else p=p->next; }

//if(!p) top--; //注意这里的p值代表的是顶点表的firstedge,其始终在，这行代码将使程序陷入是循环，无法得出正确的结果

}

return yes;

}

4. 源程序

#include //#include const int MaxSize=10; //template

struct ArcNode //定义边表结点 {

int adjvex; //其代表邻接点域，即是结点数组下标 ArcNode *next; };

template

struct VertexNode //定义顶点表结点 {

T vertex;

ArcNode *firstedge; };

template class ALGraph {

public:

ALGraph(T a[],int n,int e);

//~ALGraph(); //析构函数可以由系统自己调用，如果定义了，没有写出其算，就容易出错，thiscall----

void DFSTraverse(int v); void BFSTraverse(int v); void DFS(int v); int DFS1(int i,int j); private: VertexNode adjlist[MaxSize]; //定义结点数组，存放顶点,注意vertexNode后面的不要忘记了，c++模板机制

int vertexNum,arcNum; int visited[MaxSize]; };

template

ALGraph::ALGraph(T a[],int n,int e) {

vertexNum=n; arcNum=e;

for(int i=0;i

for(i=0;i

adjlist[i].vertex=a[i]; adjlist[i].firstedge=NULL; }

for(int k=0;k

int i,j;

cout<<\请输入两组数字：\ cin>>i>>j; ArcNode *s; s=new ArcNode;

s->adjvex=j; //输入依附的两个顶点的序号 s->next=adjlist[i].firstedge;

adjlist[i].firstedge=s; //头插法 } }

template

void ALGraph::DFSTraverse(int v) { int j;

cout<

ArcNode *p; p=adjlist[v].firstedge; while(p) {

j=p->adjvex; if(visited[j]==0) DFSTraverse(j); p=p->next; } }

template

void ALGraph::BFSTraverse(int v) {

int visited1[MaxSize];

int q[MaxSize]; //存放的是邻接点域 int front,rear;

for(int i=0;i

cout<

q[++rear]=v; //模拟入队操作 while(front!=rear)

{

v=q[++front]; //模拟进队操作 ArcNode *p;

p=adjlist[v].firstedge; while(p) { int j;

j=p->adjvex; if(visited1[j]==0) {

cout<

p=p->next; } } }

template

void ALGraph::DFS(int v) //深度优先非递归算法 {

int i,visited2[MaxSize],s[MaxSize],top=-1; ArcNode *p;

for(i=0;i

cout<=-1) {

v=s[top]; top--;

p=adjlist[v].firstedge;

while(p!=NULL&&visited2[p->adjvex]==1) p=p->next; if(p==NULL) top--; else {

v=p->adjvex;

cout<