数据结构与算法之图

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

1、仲恺农业工程学院实验报告纸（院、系）专业班组课学号姓名实验日期教师评定实验四图的建立及应用一、实验目的1、掌握图的存储思想及其存储实现。2、掌握图的深度、广度优先遍历算法思想及其程序实现。3、理解最小生成树的有关概念以及普里姆算法和克鲁斯卡尔算法的实现。4、理解最短路径、拓朴排序、关键路径算法及实现。二、实验要求1、编写程序实现图的各种运算，并在此基础上设计主函数，使其完成如下功能：（1）建立无向图（2）输出无向图对应的邻接表。（3）实现深度遍历和广度遍历。三、程序运算结果截图四、程序源代码#include#includeu

2、singnamespacestd;////////////////////////////#defineN20typedefcharVertexType;/////////////////////////////////typedefstructArcNode{第5页共5页intadjdex;structArcNode*next;//图的边界点}AN;//////////////////////////////typedefstructVNode{VertexTypedata;boolmark;AN*firstarc;//图的顶点}VN;/////////////

3、///////////////////VNG[N];//定义图的顶点/////////////////////////////////voidCreate(intn,VNG[])//创建无向图{AN*p,*q;inti,e;VertexTyped;cout<<"Inputtheinformationofthevertex";for(i=0;i>d;G[i].data=d;//初始化图的顶点G[i].firstarc=NULL;G[i].mark=false;}for(i=0;i

4、ut<<"CreatetheedgesfotheG["<>e;while(e!=-1){p=(AN*)malloc(sizeof(AN));p->next=NULL;p->adjdex=e;//建立顶点间的关系if(G[i].firstarc==NULL)G[i].firstarc=p;elseq->next=p;q=p;cout<<"按-1退出，否则继续创建边结点"<>e;}第5页共5页}}//////////////////////////////////voidvisit(VNG[],intv){cou

5、t<<"G["<adjdex;//查找顶点的第一条边return-1;}//////////////////////////////////intNextAdj(VNG[],intv){AN*p;p=G[v].firstarc;while(p->next!=NULL){if(G[p->nex

6、t->adjdex].mark==true)//查找顶点的下一条边p=p->next;elsereturnp->next->adjdex;}return-1;}//////////////////////////////////voidVisit(VNG[],intn){inti,j,w;for(i=0;i

7、"]";G[w].mark=true;w=NextAdj(G,i);第5页共5页}cout<

8、/////