08 梁伟华 实验四

《08 梁伟华 实验四》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验四图的的操作及应用实验课程名：数据结构专业班级：计算机科学与技术（2）班学号：201140410208姓名：梁伟华实验时间：12.13实验地点：K4-209指导教师：祁文青一、实验目的1、理解图的基本概念及术语；2、掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法；3、熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；4、理解最小生成树的概念，能按Prim算法构造最小生成树；领会并掌握拓扑排序、关键路径、最短路径的算法思想。二、实验内容 任务1：构造图的邻接矩阵存储结构或邻接表存储结构图的邻接表#incl

2、ude#include#defineGRAPH_H#defineMAX_VRTEX_NUM20structedgenode{intadjvex;edgenode*next;};//定义邻接表的边结点类型typedefedgenode**adjlist;//定义邻接表类型voidInitGAdjoin(adjlist&GL,intn);//初始化图的邻接表voidCreateAdjoin(adjlist&GL,intn,intm);#include#includevoidCheck(intn,int&i,in

3、t&j);voidInitGAdjoin(adjlist&GL,intn)//初始化图的邻接表{GL=newedgenode*[n];for(inti=1;i<=n;i++)GL[i]=NULL;26}voidCreateAdjoin(adjlist&GL,intn,intm)//建立图的邻接表{inti,j,k,e;cout<<"输入图的总边数：";cin>>e;if(m==0){//建立无向图for(k=0;k>i>>j;Check(n,i,j);edgenode*p=newedgenode;p->ad

4、jvex=j;p->next=GL[i];GL[i]=p;//向序号为i的单链表的表头插入一个边结点p=newedgenode;p->adjvex=i;p->next=GL[j];GL[j]=p;//向序号为j的单链表的表头插入一个边结点}cout<

5、"<<"V"<next)cout<<"

6、-

7、->

8、"<adjvex;cout<<"

9、

10、^

11、";cout<>i>>j;Check(n,i,j);//向序号为i的表头插入一个边结点edgenode*p=newedgenode;p->adjvex=j;26p->next=GL[i];GL[i]=p;}cout<<"图的邻接表为:"<

12、"<<"V"<

13、;p=p->next)cout<<"

14、-

15、->

16、"<adjvex;cout<<"

17、^

18、";cout<

19、

20、i>n

21、

22、j<=0

23、

24、j>n)cout<<"输入有误,请重新输入！";elsereturn;cin>>i>>j;}}voidmain(){inti,n,m;//cout<<"=============="<>n;cout<<"输入是否有向（0为无，1为有）:";cin

25、>>m;bool*visited=newbool[n];adjlistgl;InitGAdjoin(gl,n);CreateAdjoin(gl,n,m);cout<#include#defineM20#defineMAX20typedefstruct{intbegin;intend;intweigh