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

十一、采用连接表存储有向图，设计算法判断任意两个顶点间是否存在路径#include stdio.h #include stdlib.h #include malloc.h #define max 100 /顶点的最大个数#define NULL 0typedef struct st1 /定义邻接表中结点类型 int adjvex; /邻接点的位置 struct st1 *nextarc; /指向下一个结点 char info; /边的信息Arcnode; typedef struct /定义邻接表中头结点类型 char vexdata; /顶点信息 Arcnode *firstarc; /指向第一个邻接结点AdjList; typedef struct /定义邻接表表头 AdjList vexticesmax; /存放表头结点信息 int vexnum,arcnum; /有向图的顶点数和边数AlGraph; int visitedmax; /定义深度优先搜索遍历数组，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;ivexticesi.vexdata=(char)i; /数据域存放顶点序号 al-vexticesi.firstarc=NULL; printf(请输入边数：); scanf(%d,&e); printf(请输入弧的信息：); for(i=0;iadjvex=k; p-info= ; p-nextarc=al-vexticesj.firstarc; al-vexticesj.firstarc=p; al-vexnum=n; al-arcnum=e; return al; /输出邻接表 void print(AlGraph *alg) int i; Arcnode *p; printf(图的邻接表为：n); for(i=1;ivexnum;i+) printf(t%d-,alg-vexticesi.vexdata); p=alg-vexticesi.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;ivexnum;i+) p=alg-vexticesi.firstarc; while(p!=NULL) q=p-nextarc; free(p); p=q; /深度优先搜索遍历算法 int dfs(AlGraph *alg,int i,int n) Arcnode *p; visitedi=1; /标志已被访问 p=alg-vexticesi.firstarc; while(p!=NULL) if(visitedp-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;ivexnum;i+) visitedi=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);