图实验报告.docx
- 文档编号:11036332
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:15
- 大小:196.04KB
图实验报告.docx
《图实验报告.docx》由会员分享,可在线阅读,更多相关《图实验报告.docx(15页珍藏版)》请在冰点文库上搜索。
图实验报告
闽江学院电子 系
实验 报 告
学生姓名:
班级:
学号:
课程:
算法与数据结构
一、实验题目:
:
图及其应用
一、实验地点:
实验楼A210
二、实验目得:
.熟练掌握图得两种存储结构(邻接矩阵与邻接表)得表示方法
.掌握图得基本运算及应用
。
加深对图得理解,逐步培养解决实际问题得编程能力
三、实验内容:
。
采用邻接表或邻接矩阵方式存储图,实现图得深度遍历与广度遍历;
、用广度优先搜索方法找出从一顶点到另一顶点边数最少得路径;
。
图得存储结构得转换。
四、实验环境(使用得软硬件):
VisualC++集成开发环境
5、实验步骤及操作
1。
启动VC++;
2、新建工程/Win32ConsoleApplication,选择输入位置:
输入工程得名称:
tu;
按“确定”按钮,选择“AnEmptyProject”,再按“完成”按钮,
3。
新建文件/C++ SourceFile,选中“添加到工程得复选按钮”,输入文件名“1.cpp”,按“确定”
按钮,在显示得代码编辑区内输入如下得参考程序:
#include〈stdio.h>
#include <stdlib。
h〉
#defineInfinity1000
#defineMAX20
typedefstruct{
intvexnum; //顶点数目
intarcnum; //弧数目
ﻩcharvexs[MAX]; //顶点向量
ﻩintarcs[MAX][MAX]; //邻接矩阵
ﻩchar kind;//图得种类:
有向图D,无向图U
}MGraph;
//图得建立
MGraph Creat_MGraph(){
MGraph G;
int i,j,k,w;
charv1,v2;
ﻩprintf("请输入图得种类(有向图(D),无向图(U)!
\n");
scanf("%c",&G。
kind);
ﻩprintf("请输入顶点数目与弧数目!
\n");
scanf("%d%d”,&G。
vexnum,&G、arcnum);
ﻩgetchar();
printf("请输入各个顶点(abc)!
\n");
for(i=0;i〈G。
vexnum;i++)
ﻩscanf(”%c",&G。
vexs[i]);
getchar();
for(i=0;i<G.vexnum;i++){
ﻩfor(j=0;j〈G、vexnum;j++)
ﻩG.arcs[i][j]=Infinity;
}
for(i=0;i〈G。
arcnum;i++){
printf("请输入第 (%d)条弧得起始点与它得权重(ccd)!
\n",i+1);
ﻩﻩscanf("%c%c%d”,&v1,&v2,&w);
ﻩgetchar();
j=k=0;
while(G、vexs[j]!
=v1)j++; //起点
ﻩﻩwhile(G。
vexs[k]!
=v2) k++; //终点
ﻩﻩG、arcs[j][k]=w;
ﻩif(G、kind=='U')
G、arcs[k][j]=w;
ﻩ}
ﻩreturn G;
}
intvisited[MAX];//标志数组,显示就是否遍历
//递归深度遍历调用函数
voidDFS(MGraphG,inti){
ﻩint j;
visited[i]=1;
printf(” %c",G、vexs[i]);
ﻩfor(j=0;j<G.vexnum;j++)
ﻩif(!
visited[j]&&G.arcs[i][j]〈Infinity)
ﻩﻩDFS(G,j);
}
//深度遍历函数
void M_DFSTraverse(MGraphG){
ﻩinti;
printf(”深度遍历图结果如下:
\n");
for(i=0;i〈G。
vexnum;i++)
visited[i]=0;
ﻩfor(i=0;i<G。
vexnum;i++)
ﻩﻩif(!
visited[i])
ﻩﻩDFS(G,i);
printf("\n”);
}
ﻩﻩ
//广度遍历函数
voidM_BFSTraverse(MGraphG){
inti,j,k,Q[MAX],w;
j=k=0;
printf("广度遍历图结果如下:
\n”);
for(i=0;i〈G。
vexnum;i++)
visited[i]=0;
ﻩfor(i=0;i ﻩif(! visited[i]){ ﻩvisited[i]=1; ﻩprintf(” %c ",G。 vexs[i]); ﻩﻩQ[k++]=i; ﻩﻩwhile(j! =k){ ﻩﻩj++; ﻩfor(w=0;w〈G.vexnum;w++) ﻩﻩif(! visited[w]&&G、arcs[j][w]〈Infinity){ ﻩﻩﻩﻩvisited[w]=1; ﻩﻩﻩﻩprintf(" %c ”,G.vexs[w]); ﻩQ[k++]=w; ﻩﻩﻩ} ﻩﻩ} } ﻩprintf("\n"); } //最小生成树函数,对无向图适用 voidMiniSpanTree_PRIM(MGraphG,charu){ charadjvex[MAX]; int lowcost[MAX]; ﻩint i,j,k=0,min; ﻩprintf("图得最小生成树为: \n"); while(G。 vexs[k]! =u) k++; for(i=0;i〈G、vexnum;i++) ﻩif(i! =k){ adjvex[i]=u; lowcost[i]=G。 arcs[k][i]; ﻩ} lowcost[k]=0; for(i=0;i ﻩmin=Infinity; for(j=0;j<G.arcnum;j++) ﻩif(lowcost[j]&& lowcost[j] ﻩﻩﻩﻩmin=lowcost[j]; ﻩﻩﻩk=j; } printf("%c—-(%d)-—%c\n”,adjvex[k],lowcost[k],G、vexs[k]); ﻩﻩ lowcost[k]=0; ﻩﻩfor(j=0;j ﻩ if(G.arcs[k][j]〈lowcost[j]){ ﻩadjvex[j]=G、vexs[k]; ﻩﻩ lowcost[j]=G、arcs[k][j]; ﻩﻩ} } } //求最短路径得函数,对有向图适用 voidShortestPath_DIJ(MGraph G,charu){ ﻩint P[MAX][MAX], //二维数组,标志最短路径上得点 ﻩD[MAX], //记录最短路径得长度 ﻩﻩfinal[MAX], //标志就是否求得它得最短路径 ﻩi,j,v,w,v0,min; ﻩv0=0; ﻩwhile(G.vexs[v0]! =u)v0++; for(v=0;v〈G.vexnum;++v){//初始化 ﻩﻩD[v]=G。 arcs[v0][v]; final[v]=0; ﻩﻩfor(w=0;w<G、vexnum;w++) ﻩﻩP[v][w]=0; if(D[v]〈Infinity){ ﻩP[v][v0]=1;P[v][v]=1; ﻩ} } D[v0]=0;final[v0]=1; for(i=1;i<G、vexnum;i++){ //循环求出各个最短路径 ﻩﻩmin=Infinity; ﻩﻩfor(w=0;w vexnum;++w) ﻩﻩﻩif(! final[w]) ﻩﻩﻩif(D[w]<min){ ﻩv=w;min=D[w]; ﻩ} final[v]=1; for(w=0;w<G。 vexnum;w++) ﻩﻩ if(! final[w]&&(min+G.arcs[v][w] ﻩD[w]=min+G、arcs[v][w]; ﻩﻩfor(j=0;j〈G.vexnum;j++) ﻩﻩﻩP[w][j]=P[v][j]; ﻩﻩﻩ P[w][w]=1; ﻩﻩ} ﻩ} printf("从已知点到其她各点得最短路径为: \n"); ﻩfor(v=0;v〈G、vexnum;v++) ﻩﻩif(final[v]){ ﻩprintf("%c-—%c得最短路径长度为 %d,路径为: ”,u,G、vexs[v],D[v]); ﻩﻩfor(w=0;w ﻩﻩﻩif(P[v][w]) ﻩﻩprintf(”%c",G。 vexs[w]); printf("\n”); ﻩﻩ} } ﻩ void main(){ ﻩMGraphG; G=Creat_MGraph(); M_DFSTraverse(G); M_BFSTraverse(G); if(G、kind=='U') MiniSpanTree_PRIM(G,'a');//无向图就求它得最小生成树 ﻩelse ShortestPath_DIJ(G,'a’); //有向图就求它得最短路径 } 4、按F7 键,或工具图标进行工程得建立,如有错误,根据错误显示区中得提示,改正错误,重新建立 应用程序; 5.按Ctrl+F5 键,或工具图标进行工程得执行。 6、新建工程/Win32ConsoleApplication,选择输入位置: 输入工程得名称: 图得存储结构转换; 按“确定”按钮,选择“An Empty Project”,再按“完成"按钮, 7.新建文件/C++SourceFile,选中“添加到工程得复选按钮”,输入文件名“1。 cpp”,按“确定” 按钮,在显示得代码编辑区内输入如下得参考程序: #include h〉 #include<stdlib、h〉 #defineMAX5 #defineINF100000 intvisit[MAX]={0}; typedefstructmgraph { int edges[MAX][MAX]; intn,e; }MGraph; typedefstructnode { int adjvex; structnode*nextarc; }ArcNode; typedefstruct Vnode { ArcNode*firstarc; }VNode; typedef structalgraph { VNode adjlist[MAX]; intn,e; }ALGraph; voidMtoAL(MGraphmg,ALGraph*&alg) { int i,j,n=mg.n; ArcNode*p; alg=(ALGraph*)malloc(sizeof(ALGraph)); for(i=0;i<n;i++) alg->adjlist[i]、firstarc=NULL; for(i=0;i { for(j=n—1;j>=0;j—-) { if(mg、edges[i][j]! =0) { p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p-〉nextarc=alg->adjlist[i].firstarc; alg->adjlist[i]。 firstarc=p; } } alg-〉n=mg、n; alg—〉e=mg.e; } } voidALtoM(ALGraph*alg,MGraph &mg) { inti=0,n=alg-〉n; ArcNode*p; for(i=0;i〈n;i++) { p=alg-〉adjlist[i].firstarc; while(p) { mg、edges[i][p->adjvex]=1; p=p—>nextarc; } } mg。 n=alg->n; mg。 e=alg—〉e; } voidPrintMGraph(MGraphmg) { for(inti=0;i { for(intj=0;j〈MAX;j++) printf(”%-3d",mg。 edges[i][j]); printf(”\n"); } printf(”thenumofedge is: %-3d\n”,mg。 e); printf("the numofvertexis: %-3d\n",mg、n); } void PrintALGraph(ALGraph*alg) { for(int i=0;i〈MAX;i++) { if(alg->adjlist[i]、firstarc) { printf(”vertex[%d]: ”,i); ArcNode*p=alg-〉adjlist[i]、firstarc; while(p) { printf(”%-3d”,p->adjvex); p=p—>nextarc; } } printf("\n"); } } void main() { MGraphmg; ALGraph*alg; mg、n=5;mg、e=6; int path[MAX]; inta[MAX][MAX]={ {0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0}}; inti,j; for(i=0;i〈mg、n;i++) for(intj=0;j<mg。 n;j++) mg、edges[i][j]=a[i][j]; printf("邻接矩阵表示图: \n”); PrintMGraph(mg); MtoAL(mg,alg); printf(”转化为邻接表表示图: \n”); PrintALGraph(alg); ALtoM(alg,mg); printf(”转化为邻接矩阵表示图: \n"); PrintMGraph(mg); } 8。 按F7键,或工具图标进行工程得建立,如有错误,根据错误显示区中得提示,改正错误,重新建立 应用程序; 9、按Ctrl+F5键,或工具图标进行工程得执行。 六、实验结果: (1)无向图 (2)有向图 (3)图得存储结构得转换 五、实验总结及心得体会: 从一个顶点出发只能访问到它所在连通分量得各顶点、如果有回路存在,一个顶点被访问之后又可能沿回路回到该顶点,为了避免对同一个顶点多次访问,在遍历过程中必须记下已经访问过得顶点,通常利用一维辅助数组记录顶点被访问得情况、 六、对本实验过程及方法、手段得改进建议: 报告评分: 指导教师签字: 批阅日期:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)