实验三 图的存储结构及各种运算的实现

《实验三 图的存储结构及各种运算的实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、辽宁师范大学上机实验报告计算机与信息技术学院计算机科学与技术专业课程名称：数据结构—用C语言描述实验题目：图的存储结构及各种运算的实现班级：2010级6班学号：20101118050097姓名：刘云鹏指导教师：黄丹完成时间：2011.11.11一．实验目的：   1、掌握图的逻辑结构及其常用的存储表示方法，建立图的邻接表与邻接矩阵。2、熟练掌握图的深度与广度优先搜索算法的基本思想，能在不同存储结构上实现算法。3、深入理解最小生成树的定义，掌握Prim算法和Kruskar算法构造最小生成树的基本思想，并实现Prim算法。4、掌握用DIJKSTTRA算法求解单源最短路径的基本过程和算法。三．实验

2、内容及要求：1、建立图的邻接表与邻接矩阵，并在不同存储结构上实现深度与广度优先搜索算法。   2、用Prim算法构造带权网络的最小生成树。   3、用DIJKSTTRA算法求解单源最短路径。 选做部分：4、求拓朴序列和关键路径。四．概要设计：第一题：（1）输入顶点信息：abcd顶点对序号为：10；20；21；30；31；DFSL序列为（起点序号为1）：bdacBFSL序列为（起点序号为0）：adcb(2)输入顶点信息：abcd顶点对序号为：10；20；21；30；31；邻接矩阵为：abcda0111b1011c1100d1100DFS序列为（起点序号为1）：bacdBFS序列为（起点序号为2

3、）：cabd第二题：输入顶点信息：abcdef顶点对序号及权值：016；021；035；143；125；245；254；352；456；237；最小生成树：1—>3：13—>6：46—>4：23—>5：55—>2：3第三题：输入的顶点信息：12345输入的顶点对和权值：0110；0330；04100；1250；2410；3220；3460起始结点：4单元最短路径：max1max2203<—404305<—3<—4DIJKSTRA动态执行情况循环红点集SK+1D[0]~D[4]P[0]~P[4]初始化{4}—maxmax20060004041{4,3}3maxmax20030004032{4,

4、3,5}2maxmax20030004033{4,3,5,1}1maxmax20030004034{4,3,5,1}2maxmax2003000403五．实验结果分析及程序代码：第一题邻接表#include#include#definetrue1#definefalse0#definemax60#definen4#definee5typedefstructnode{intadjvex;structnode*next;}edgenode;typedefstruct{charvertex;edgenode*link;}vexnode;vexnodega[n]

5、;intvisited[max];intq[max];creatadjlist(vexnodega[]){inti,j,k;edgenode*s;printf("请输入顶点信息:");for(i=0;iadjvex=j;s->next=ga[i].link;ga[i].link=s;s=malloc(sizeof(e

6、dgenode));s->adjvex=i;s->next=ga[j].link;ga[j].link=s;}}DFSL(inti){edgenode*p;printf("node:%c",ga[i].vertex);visited[i]=1;p=ga[i].link;while(p!=NULL){if(!visited[p->adjvex])DFSL(p->adjvex);p=p->next;}}BFSL(intk){inti;edgenode*p;intrear,front;front=-1;rear=-1;printf("node:%c",ga[k].vertex);visit

7、ed[k]=1;rear++;q[rear]=k;while(front!=rear){front++;i=q[front];p=ga[i].link;while(p!=NULL){if(!visited[p->adjvex]){printf("node:%c",ga[p->adjvex].vertex);visited[p->adjvex]=1;rear++;q[rear]=p->adjvex;}p=p