1305120411-何彬实验报告07.doc

计算机科学与工程学院 《算法与数据结构》实验报告(七) 专业班级 2013网络工程01 实验地点 423机房 学生学号 1305120411 指导教师 赵卿松 学生姓名 何彬 实验时间 2015.5.20 实验项目 图的应用一 实验类别 基础性（） 设计性（√） 综合性（） 其它（ ） 实验目的及要求 （1）熟练掌握图的基本存储方法；（2）熟练掌握图的深度优先和广度优先有哪些信誉好的足球投注网站方法。 成 绩 评 定 表 类 别 评 分 标 准 分值 得分 合 计 上机表现 积极出勤、遵守纪律 按要求完成设计任务 30分 程序与报告 程序代码规范、功能正确 报告详实完整、体现收获 70分 说明： 评阅教师： 赵卿松  日 期： 2015 年 5 月 30 日 实 验 内 容 实验内容：图的两种遍历方法及对应的生成树。 自己编写源程序，把图的深度优先遍历、广度优先遍历改为输出深度优先生成树、广度优先生成树。 实验说明：（1）读懂教师给定的程序或课本的程序； （2）输入图； （3）把显示遍历序列改为显示深度优先、广度优先生成树。 #includestdio.h #includemalloc.h #define MAXV 100 #define INF 32767 typedef int Infotype; typedef struct { int no; Infotype info; } Vertextype; typedef struct { int edges[MAXV][MAXV]; int n,e; Vertextype vexs[MAXV]; }Mgraph; typedef struct Anode { int adjvex; struct Anode *nextarc; Infotype info; }Arcnode; typedef int Vertex; typedef struct VNode { Vertex data; Arcnode *firstarc; }Vnode; typedef Vnode Adjlist[MAXV]; typedef struct { Adjlist adjlist; int n,e; }Algraph; void Mattolist(Mgraph g,Algraph *G) { int i,j; Arcnode *p; G=(Algraph *)malloc(sizeof(Algraph)); for(i=0;ig.n;i++) G-adjlist[i].firstarc=NULL; for(i=0;ig.n;i++) for(j=g.n-1;j=0;j--) if(g.edges[i][j]!=0) { p=(Arcnode *)malloc(sizeof(Arcnode)); p-adjvex=j; p-nextarc=G-adjlist[i].firstarc; G-adjlist[i].firstarc=p; } G-n=g.n;G-e=g.e;} void Dispadj(Algraph *G) { int i; Arcnode *p; for(i=0;iG-n;i++) { p=G-adjlist[i].firstarc; printf(%3d:,i); while(p!=NULL) { printf(%3d,p-adjvex); p=p-nextarc;} printf(\n); } } int visited[MAXV]; void DFS(Algraph *G,int v) { Arcnode *p; visited[v]=1; p=G-adjlist[v].firstarc; while(p!=NULL) { if(visited[p-adjvex]==0) { printf(%d,%d ,v,p-adjvex); DFS(G,p-adjvex);} p=p-nextarc; } } void BFS(Algraph *G,int v) { Arcnode *p; int queue[MAXV],front=0,rear=0; int w,i; for(i=0;iG-n;i++) visited[i]=0; visited[v]=1; rear=(rear+1)%MAXV;