数据结构实验十一：图实验

《数据结构实验十一：图实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一，实验题目实验十一：图实验采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。二，问题分析本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。1，数据的输入形式和输入值的范围：输入的图的结点均为整型。2，结果的输出形式：输出的是两结点间是否存在路径的情况。3，测试数据：输入的图的结点个数为：4输入的图的边得个数为：3边的信息为：12，23，31三，概要设计（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）邻接表中的结点类型定义：ty

3、pedefstructarcnode{intadjvex;arcnode*nextarc;}arcnode;（2）邻接表中头结点的类型定义：typedefstruct{charvexdata;arcnode*firstarc;}adjlist;（3）邻接表类型定义：typedefstruct{adjlistvextices[max];intvexnum,arcnum;}algraph;（4）深度优先搜索遍历函数伪代码：intdfs(algraph*alg,inti,intn){arcnode*p;visited[i]=1;p=alg->vextic

4、es[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;}（5）初始化遍历数组并判断有无通路函数伪代码：voiddfs_trave(algraph*alg,intx,inty){inti;for(i=0;i<=alg->vexnum;i++)visited[i]=0;dfs(alg,x,y);}五，源代码#include

5、"stdio.h"#include"stdlib.h"#include"malloc.h"#definemax100typedefstructarcnode{//定义邻接表中的结点类型intadjvex;//定点信息arcnode*nextarc;//指向下一个结点的指针nextarc}arcnode;typedefstruct{//定义邻接表中头结点的类型charvexdata;//头结点的序号arcnode*firstarc;//定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist;typedefstruct{//定义邻接表

6、类型adjlistvextices[max];//定义表头结点数组intvexnum,arcnum;//定点个数和弧的个数}algraph;algraph*create_adjlistgraph(){//建立邻接表函数intn,e,i,j,k;arcnode*p;//定义一个邻接表结点型指针变量palgraph*al;//定义邻接表表头结点指针alal=(algraph*)malloc(sizeof(algraph));//为邻接表结点申请空间printf("请输入节点数：");scanf("%d",&n);//输入结点数for(i=0;i<=

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

8、赋值给新申请的结点p->nextarc=al->vextices[j].firstarc;//使新结点指向该头结点所指向的