采用连接表存储有向图-设计算法判断任意两个顶点间是否存在路径

十一、采用连接表存储有向图，设计算法判断任意两个顶点间是否存在路径#includestdio.h#includestdlib.h#includemalloc.h#definemax100//顶点的最大个数#defineNULL0typedefstructst1{//定义邻接表中结点类型intadjvex;//邻接点的位置structst1*nextarc;//指向下一个结点charinfo;//边的信息}Arcnode;typedefstruct{//定义邻接表中头结点类型charvexdata;//顶点信息Arcnode*firstarc;//指向第一个邻接结点}AdjList;typedefstruct{//定义邻接表表头AdjListvextices[max];//存放表头结点信息intvexnum,arcnum;//有向图的顶点数和边数}AlGraph;intvisited[max];//定义深度优先搜索遍历数组，0表示未被访问过，1表示已被访问过intflag=0;//定义全局标志变量，用来确定两点间是否为通路，1表示存在，0表示不存在/////////////////////////////////////////////////////////////////////建立邻接表AlGraph*create_AdjListGraph(){intn,e,i,j,k;Arcnode*p;AlGraph*al;al=(AlGraph*)malloc(sizeof(AlGraph));printf(请输入结点数：);scanf(%d,&n);for(i=1;i=n;i++){//初始化表头结点数组al-vextices[i].vexdata=(char)i;//数据域存放顶点序号al-vextices[i].firstarc=NULL;}printf(请输入边数：);scanf(%d,&e);printf(请输入弧的信息：);for(i=0;ie;i++){scanf(%d%d,&j,&k);//依次读入弧的信息，结点k为结点j的邻接点p=(Arcnode*)malloc(sizeof(Arcnode));//申请结点空间，分配结点p-adjvex=k;p-info='';p-nextarc=al-vextices[j].firstarc;al-vextices[j].firstarc=p;}al-vexnum=n;al-arcnum=e;returnal;}//////////////////////////////////////////////////////////////输出邻接表voidprint(AlGraph*alg){inti;Arcnode*p;printf(图的邻接表为：\n);for(i=1;i=alg-vexnum;i++){printf(\t%d-,alg-vextices[i].vexdata);p=alg-vextices[i].firstarc;while(p!=NULL){printf(%d-,p-adjvex);p=p-nextarc;}printf(\n);//符号“”表示空结点}}///////////////////////////////////////////////////////////释放邻接表结点空间voidFreeAlGraph(AlGraph*alg){inti;Arcnode*p,*q;for(i=0;i=alg-vexnum;i++){p=alg-vextices[i].firstarc;while(p!=NULL){q=p-nextarc;free(p);p=q;}}}////////////////////////////////////////////////////深度优先搜索遍历算法intdfs(AlGraph*alg,inti,intn){Arcnode*p;visited[i]=1;//标志已被访问p=alg-vextices[i].firstarc;while(p!=NULL){if(visited[p-adjvex]==0){if(p-adjvex==n){flag=1;}dfs(alg,p-adjvex,n);//访问未被访问过的结点if(flag==1)return1;}p=p-nextarc;//搜索下一个邻接点}return0;}////////////////////////////////////////////////初始化遍历数组并进行路径搜索voiddfs_trave(AlGraph*alg,intm,intn){inti;for(i=0;i=alg-vexnum;i++)visited[i]=0;//初始化访问数组dfs(alg,m,n);}/////////////////////////////////////////////////////////////主函数voidmain(){intm,n;//需要判断有无通路的两个结点AlGraph*alg;alg=create_AdjListGraph();print(alg);//输出链接表do{printf(请输入任意两个顶点（输入两个-1退出）：);scanf(%d%d,&m,&n);dfs_trave(alg,m,n);printf(\n);if(flag==1)printf(顶点%d到%d存在通路\n,m,n);elseprintf(顶点%d到%d不存在通路\n,m,n);flag=0;printf(\n);}while(m!=-1&&n!=-1);FreeAlGraph(alg);//释放结点空间}