/*采用深度优先遍历来判断。*/
#include "Stdio.h"
#include "Conio.h"
#define Max 20
/*一个大于顶点数的常量*/
#include
#define MAX_VERTEX_NUM 20
typedef struct ArcNode
{
int adjvex; /*该弧所指向的顶点的位置*/
struct ArcNode *nextarc; /*指向下一条弧的指针*/
}ArcNode;
typedef struct VNode
{
char data; /*顶点信息*/
ArcNode *firstarc; /*指向第一条依附该顶点的弧的指针，相当于该行的头结点*/
}VNode;
typedef struct
{
VNode AdjList[MAX_VERTEX_NUM]; /*存放结点的数组*/
int vexnum,arcnum; /*图的当前顶点数和弧数*/
int kind; /*图的种类标志*/
}ALGraph;
int visited[Max];
ALGraph *Ceart_Graph()
{
ALGraph *G;
int i,n;
ArcNode *p,*s;
printf("please input the number of vertex and arc eg(4,4):n");
scanf("%d,%d",&(G->vexnum),&(G->arcnum));
getchar();
for(i=0;ivexnum;i++)
{n=0;
/* printf("i=%d,vexnum=%dn",i,G->vexnum);
getch(); */
G->AdjList[i].firstarc=(ArcNode *)malloc(sizeof(ArcNode));
G->AdjList[i].firstarc=NULL;
printf("please input the vertex:n");
scanf("%c",&(G->AdjList[i].data)); /*输入结点的值*/
getchar();
/* printf("%c",G->AdjList[i].data);
getch(); */
p=(ArcNode *)malloc(sizeof(ArcNode));
s=(ArcNode *)malloc(sizeof(ArcNode));
printf("please input the location of next vertex:n");
scanf("%d",&(s->adjvex));
getchar(); /*建立后续访问的结点次序*/
while(s->adjvex!=-1)
{
n++;
if(n==1) G->AdjList[i].firstarc=s;
else p->nextarc=s;
p=s;
s=(ArcNode *)malloc(sizeof(ArcNode));
printf("please input the another location of next vertex:n");
scanf("%d",&(s->adjvex));
getchar();
}
p->nextarc=NULL;
}
return G;
}
int n=0;
void dfs(ALGraph *g,int v,int j,int *suc,int k)
{
ArcNode *p;
visited[v]=1;
n++;
/* printf("n=%d,k=%d,v=%d,j=%dn",n,k,v,j);
getch(); */
if(n==k+1&&v==j) (*suc)=1;
if(nAdjList[v]).firstarc;
/* printf("g=%c,p=%dn",g->AdjList[v].data,p->adjvex); */
/* if(p==NULL) printf("***");getch(); */
while(p!=NULL&&(*suc)==0)
{/*printf("vist=%d,%d",visited[p->adjvex],p->adjvex); getch(); */
if(visited[p->adjvex]==0)
{
dfs(g,p->adjvex,j,suc,k); /*递归调用*/
n--;
}
p=p->nextarc;
}
}
}
int exist(ALGraph *g,int vi,int vj,int k)
{
int i,*suc; /*n用于记录经过的顶点数，当n=k+1时表示路径的长度为k，suc记录是否成功*/
for(i=0;ivexnum;i++)
visited[i]=0;
*suc=0;
n=0;
dfs(g,vi,vj,suc,k);
return *suc;
}
int main(void)
{
/* 此处添加你自己的代码 */
ALGraph *G;
int k,vi,vj;
G=Ceart_Graph();
printf("please input the vex where you want to start(vi) to end(vj):n");
scanf("%d,%d",&vi,&vj);
printf("please input the length from vi to vj:n");
scanf("%d",&k);
if(exist(G,vi,vj,k))
printf("there is exist the way!");
else
printf("no!n");
getch();
return 0;
}