资源描述：
《采用连接表存储有向图,设计算法判断任意两个顶点间是否存在路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、十一、采用连接表存储有向图，设计算法判断任意两个顶点间是否存在路径#include"stdio.h"#include"stdlib.h"#include"malloc.h"#definemax100//顶点的最大个数#defineNULL0typedefstructst1{//定义邻接表中结点类型intadjvex;//邻接点的位置structst1*nextarc;//指向下一个结点charinfo;//边的信息}Arcnode;typedefstruct{//定义邻接表中头结点类型charvexdata;//
2、顶点信息Arcnode*firstarc;//指向第一个邻接结点}AdjList;typedefstruct{//定义邻接表表头AdjListvextices[max];//存放表头结点信息intvexnum,arcnum;//有向图的顶点数和边数}AlGraph;intvisited[max];//定义深度优先搜索遍历数组，0表示未被访问过，1表示已被访问过intflag=0;//定义全局标志变量，用来确定两点间是否为通路，1表示存在，0表示不存在////////////////////////////////
3、/////////////////////////////////////建立邻接表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->vextice
4、s[i].firstarc=NULL;}printf("请输入边数：");scanf("%d",&e);printf("请输入弧的信息：");for(i=0;iadjvex=k;p->info='';p->nextarc=al->vextices[j].firstarc;al->vextices[j].first
5、arc=p;}al->vexnum=n;al->arcnum=e;returnal;}//////////////////////////////////////////////////////////////输出邻接表voidprint(AlGraph*alg){inti;Arcnode*p;printf("图的邻接表为：");for(i=1;i<=alg->vexnum;i++){printf("t%d-",alg->vextices[i].vexdata);p=alg->vextices[i].fir
6、starc;while(p!=NULL){printf("%d-",p->adjvex);p=p->nextarc;}printf("<");//符号“<”表示空结点}}///////////////////////////////////////////////////////////释放邻接表结点空间voidFreeAlGraph(AlGraph*alg){inti;Arcnode*p,*q;for(i=0;i<=alg->vexnum;i++){p=alg->vextices[i].firstarc;w
7、hile(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;}
8、dfs(alg,p->adjvex,n);//访问未被访问过的结点if(flag==1)return1;}p=p->nextarc;//搜索下一个邻接点}return0;}////////////////////////////////////////////////初始化遍历数组并进行路径搜索voiddfs_trave(AlGraph*alg,intm,intn){in
