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

十一、采用连接表存储有向图，设计算法判断任意两个顶点间是否存在路径
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define max 100 //顶点的最大个数
#define NULL 0
typedef struct st1{ //定义邻接表中结点类型
int adjvex; //邻接点的位置
struct st1 *nextarc; //指向下一个结点
char info; //边的信息
}Arcnode;
typedef struct{ //定义邻接表中头结点类型
char vexdata; //顶点信息
Arcnode *firstarc; //指向第一个邻接结点
}AdjList;
typedef struct{ //定义邻接表表头
AdjList vextices[max]; //存放表头结点信息
int vexnum,arcnum; //有向图的顶点数和边数
}AlGraph;
int visited[max]; //定义深度优先搜索遍历数组，0表示未被访问过，1表示已被访问过
int flag=0; //定义全局标志变量，用来确定两点间是否为通路，1表示存在，0表示不存在
/////////////////////////////////////////////////////////////////////建立邻接表
AlGraph *create_AdjListGraph(){
int n,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;i<e;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;
return al;
}
//////////////////////////////////////////////////////////////输出邻接表
void print(AlGraph *alg){
int i;
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"); //符号“<”表示空结点
}
}
///////////////////////////////////////////////////////////释放邻接表结点空间
void FreeAlGraph(AlGraph *alg){
int i;
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;
}
}
}
////////////////////////////////////////////////////深度优先搜索遍历算法
int dfs(AlGraph *alg,int i,int n){
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) return 1;
}
p=p->nextarc; //搜索下一个邻接点
}
return 0;
}
////////////////////////////////////////////////初始化遍历数组并进行路径搜索
void dfs_trave(AlGraph *alg,int m,int n){
int i;
for(i=0;i<=alg->vexnum;i++)
visited[i]=0; //初始化访问数组
dfs(alg,m,n);
}
/////////////////////////////////////////////////////////////主函数
void main(){
int m,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);
else printf("顶点%d到%d不存在通路\n",m,n);
flag=0;
printf("\n");
}while(m!=-1&&n!=-1) ;
FreeAlGraph(alg); //释放结点空间
}