任务描述
设计一个算法，试基于深度优先搜索判断以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。
编程要求
输入
多组数据，每组m+3数据行。第一行有两个数字n和m，代表有n个顶点和m条边。第二行有n个字符，代表n个顶点的编号。第三行到第m+2行每行有两个字符h和k，代表边依附的两个顶点。第m+3行有两个字符vi和vj，代表需要判断的两个顶点。当n和m都等于0时，输入结束。
输出
每组数据输出一行。若存在路径输出“YES”，反之输出“NO”。
测试说明
平台会对你编写的代码进行测试：
测试输入：
3 2
abc
ab
bc
ac
4 2
bcsw
bs
sw
cs
0 0
预期输出：
YES
NO
#include<iostream>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MaxInt 32767 //表示极大值，即∞
#define MVNum 100 //最大顶点数
using namespace std;
typedef struct ArcNode
{//边结点
int adjvex; //邻接点域：该边所指向的顶点的位置
char data; //数据域：存储和边相关的信息
struct ArcNode* nextarc; //链域：指向下一条边的指针
}ArcNode;
typedef struct VNode
{//顶点信息
char data; //顶点结点的数据域
ArcNode *firstarc; //链域：指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum]; //AdjList表示邻接表类型
typedef struct
{//邻接表
AdjList vertices;
int vexnum,arcnum; //图的当前顶点数和边数
}ALGragh;
int Locate(char ch[],char h)
{//存在则返回h在数组中的下标，否则返回ERROR
int i;
for(i=0;ch[i]!='\0';i++)
{
if(ch[i]==h)
return i;
}
return ERROR;
}
bool visited[MVNum]; //访问标记数组，已访问顶点的值记为true,初始值为false
int CreateUDG(ALGragh &G,int vexnum,int arcnum,char ch[])
{//采用邻接表表示法，创建无向图G
G.vexnum=vexnum; //输入总顶点数
G.arcnum=arcnum; //输入总边数
if(G.vexnum>MVNum) return ERROR; //超出最大顶点数则结束函数
for(int i=0;i<G.vexnum;i++) //构造表头结点表
{
G.vertices[i].data=ch[i]; //输入顶点值
visited[i]=false;
G.vertices[i].firstarc=NULL; //初始化表头结点的指针域为NULL
}
for(int j=0;j<G.arcnum;j++) //输入各边，头插法构造邻接表
{
char h,p;
cin>>h>>p; //输入一条边依附的两个顶点h和p
ArcNode* p1=new ArcNode;
int pos2=Locate(ch,p);
p1->adjvex=pos2;
p1->data=p;
int pos1=Locate(ch,h);
p1->nextarc=G.vertices[pos1].firstarc;
G.vertices[pos1].firstarc=p1;
ArcNode* p2=new ArcNode;
p2->adjvex=pos1;
p2->data=h;
p2->nextarc=G.vertices[pos2].firstarc;
G.vertices[pos2].firstarc=p2;
}
return OK;
}
int level=1; //递归的层数
int PathDFS(ALGragh G,int i,int j)
{//基于深度优先搜索判断有向图G中顶点i到j是否有路径，是则返回1，否则返回0
/**************begin************/
/**************end************/
}
int main()
{
int n,m; //n个顶点，m条边和长度k
while(cin>>n>>m)
{
if(n==0&&m==0) break;
char ch[MVNum];
cin>>ch;
ALGragh G;
CreateUDG(G,n,m,ch); //创建无向图G
char vi,vj; //d和f代表需要判断的两个字符
cin>>vi>>vj;
int pi=Locate(ch,vi);
int pj=Locate(ch,vj);
if(PathDFS(G,pi,pj))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
