数据结构实验十一：图实验(共6页)

1、精选优质文档-倾情为你奉上一，实验题目实验十一：图实验采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。1， 数据的输入形式和输入值的范围：输入的图的结点均为整型。2， 结果的输出形式：输出的是两结点间是否存在路径的情况。3， 测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2， 2 3，3 1 三，概要设计（1）为了实现上述程序的功能，需要：A，用邻接

2、表的方式构建图B，深度优先遍历该图的结点C，判断任意两结点间是否存在路径（2）本程序包含6个函数：a，主函数main（）b，用邻接表建立图函数create_adjlistgraph()c，深度优先搜索遍历函数 dfs()d，初始化遍历数组并判断有无通路函数 dfs_trave()e，输出邻接表函数 print()f，释放邻接表结点空间函数 freealgraph()各函数间关系如右图所示：create_adjlistgraph()dfs()dfs_trave()main（）print()freealgraph()四，详细设计（1）邻接表中的结点类型定义：typedef struct arcno

3、de int adjvex; arcnode *nextarc; arcnode;（2）邻接表中头结点的类型定义：typedef struct char vexdata; arcnode *firstarc; adjlist;（3）邻接表类型定义：typedef struct adjlist vexticesmax; int vexnum,arcnum; algraph;（4）深度优先搜索遍历函数伪代码：int dfs(algraph *alg,int i,int n) arcnode *p; visitedi=1; p=alg->vexticesi.firstarc; while(p!

4、=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; （5）初始化遍历数组并判断有无通路函数伪代码：void dfs_trave(algraph *alg,int x,int y)int i; for(i=0;i<=alg->vexnum;i+) visitedi=0; dfs(alg,x,y); 五，源代码#include "stdio.h" #incl

5、ude "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode /定义邻接表中的结点类型 int adjvex; /定点信息 arcnode *nextarc; /指向下一个结点的指针nextarcarcnode; typedef struct /定义邻接表中头结点的类型 char vexdata; /头结点的序号 arcnode *firstarc; /定义一个arcnode型指针指向头结点所对应的下一个结点adjlist; typedef struct /定义邻接表类

6、型 adjlist vexticesmax; /定义表头结点数组 int vexnum,arcnum; /定点个数和弧的个数algraph; algraph *create_adjlistgraph() /建立邻接表函数 int n,e,i,j,k; arcnode *p; /定义一个邻接表结点型指针变量p algraph *al; /定义邻接表表头结点指针al al=(algraph *)malloc(sizeof(algraph); /为邻接表结点申请空间 printf("请输入节点数：n"); scanf("%d",&n); /输入结点数

7、for(i=0;i<=n;i+) al->vexticesi.vexdata=(char)i; /给头结点赋值 al->vexticesi.firstarc=NULL; /初始化头结点 printf("请输入边数：n"); scanf("%d",&e); /输入边得数目 printf("请输入弧的信息：n"); for(i=0;i<e;i+) printf("请输入边得两个结点："); scanf("%d%d",&j,&k); /输入边的两个结点

8、p=(arcnode *)malloc(sizeof(arcnode); /申请新的结点 p->adjvex=k; /将k赋值给新申请的结点 p->nextarc=al->vexticesj.firstarc; /使新结点指向该头结点所指向的下一个结点 al->vexticesj.firstarc=p; /使头结点指向新结点 al->vexnum=n; /将顶点数n给al->vexnum al->arcnum=e; /将边数e给al->arcnum return al; /返回该邻接表 void print(algraph *alg) /输出邻接

9、表 int i; arcnode *p; /定义一个邻接表结点型指针变量p printf("该图的邻接表输出为：n"); for(i=1;i<=alg->vexnum;i+) /当在结点个数范围内时 printf("%d-",alg->vexticesi.vexdata); /输出i头结点的值 p=alg->vexticesi.firstarc; /把i头结点所指的第一个结点给p while(p!=NULL) /当p不为空时 printf("%d-",p->adjvex); /输出给结点 p=p->

10、nextarc; /p指向下一个结点 printf("-n"); void freealgraph(algraph *alg) /释放邻接表结点空间函数 int i; arcnode *p,*q; /定义两个邻接表结点型指针变量p，q for(i=0;i<=alg->vexnum;i+) /当结点个数不超出范围时 p=alg->vexticesi.firstarc; /p指向i头结点所对应的第一个结点 while(p!=NULL) /当p不为空时 q=p->nextarc; /q指向p的下一个结点 free(p); /释放p p=q; /将q赋给p

11、int visitedmax; /定义深度优先搜索遍历数组 int flag=0; /设置标志，用来判断两点间是否为通路int dfs(algraph *alg,int i,int n) /深度优先搜索遍历函数arcnode *p; /定义邻接表结点类型指针pvisitedi=1; /将顶点i设置为已访问p=alg->vexticesi.firstarc; /使p指向i头结点所指的第一个结点 while(p!=NULL) /当p不为空时if(visitedp->adjvex=0) /如果p结点未被访问if(p->adjvex=n) /如果n=p结点的值flag=1; /则将标

12、志位设置为1 dfs(alg,p->adjvex,n); /递归调用深度优先搜索遍历函数if(flag=1) /如果已被访问return 1; /则返回1 p=p->nextarc; /p指向下一个结点 return 0; void dfs_trave(algraph *alg,int x,int y) /初始化遍历数组并判断有无通路函数int i; for(i=0;i<=alg->vexnum;i+) visitedi=0; dfs(alg,x,y); int main() /主函数 int m,n; algraph *alg; alg=create_adjlistg

13、raph(); /创建图 print(alg); /输出该图 printf("请输入任意要判定有无通路的两个顶点（输入（-1 -1）时退出）："); scanf("%d%d",&m,&n); while(m!=-1&&n!=-1) dfs_trave(alg,m,n); /调用初始化遍历数组并判断有无通路函数if(flag=1) printf("顶点%d和%d之间存在路径n",m,n); else printf("顶点%d和%d之间不存在路径n",m,n); flag=0; printf("请输入任意要判定有无通路的两个顶点（输入（-1 -1）时退出）："); scanf("%d%d",&am