实验四 2.docx
- 文档编号:15404851
- 上传时间:2023-07-04
- 格式:DOCX
- 页数:18
- 大小:229.99KB
实验四 2.docx
《实验四 2.docx》由会员分享,可在线阅读,更多相关《实验四 2.docx(18页珍藏版)》请在冰点文库上搜索。
实验四2
实验四图的操作及应用
实验课程名:
数据结构与算法
专业班级:
软件工程2016班学号:
************姓名:
张文昊
实验时间:
2017.5.18实验地点:
K4-108指导教师:
程细才
一、实验目的和要求
1、理解图的基本概念及术语。
2、掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法。
3、熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤,并能列出在两种存储结构上按上述两种遍历算法得到的序列。
4、理解最小生成树的概念,能按Prim算法构造最小生成树。
二、实验内容
任务一
(1):
构造如图1所示的图的邻接矩阵存储结构。
图1
(1)源代码如下:
#include
#defineINFINITY-1
#defineMAX_VERTEX_NUM20
#defineOK1
typedefenum{DG,DN,UDG,UDN}GraphKind;
typedefintEType;
typedefintInfoType;
typedefintVertexType;
typedefstructArcCell
{
ETypeadj;
InfoType*info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
VertexTypevexs[MAX_VERTEX_NUM];
AdjMatrixarcs;
intvexnum,arcnum;
GraphKindkind;
}MGraph;
intCreatUDN(MGraph&G)
{
intIncInfo,i,j,k,v1,v2,w;
printf("输入顶点数G.vexnum(eg,G.vexnum=4):
");
scanf("%d",&G.vexnum);
printf("输入边数G.arcnum(eg,G.arcnum=4):
");
scanf("%d",&G.arcnum);
printf("输入弧相关信息(0fornone):
");
scanf("%d",&IncInfo);
for(i=0;i for(j=0;j { G.arcs[i][j].adj=INFINITY; G.arcs[i][j].info=NULL; } printf("请输入邻接矩阵\n"); for(k=0;k { printf("请输入一条边V1V2: ",k+1); scanf("%d%d",&v1,&v2); printf("请输入边的权值: "); scanf("%d",&w); i=v1;j=v2; i--;j--; G.arcs[i][j].adj=G.arcs[j][i].adj=w; if(IncInfo) { printf("Pleaseinputthe%dtharc'sInfo: ",k+1); scanf("%s",*G.arcs[i][j].info); } } return(OK); } voidprint_Great(MGraph&G) {inti,j; printf("TheGraphis: \n"); for(i=0;i {for(j=0;j if(G.arcs[i][j].adj==INFINITY)printf("∞"); elseprintf("%d",G.arcs[i][j].adj); printf("\n"); } } intmain() { MGraphG; CreatUDN(G); print_Great(G); return0; } (2)程序运行结果: (3)结果分析: 运行良好。 任务一: (2)构造图的邻接表存储结构。 图1 (1)源代码如下: #defineMAX_VERTEX_NUM20//最大值 #defineMAX_VERTEX_NUM20 #defineOK1 #include #include typedefenum{DG,DN,UDG,UDN}GraphKind; typedefintEType; typedefintInfoType; typedefintVertexType; typedefstructArcNode { intadjvex; structArcNode*nextarc; InfoType*info; }ArcNode; typedefstructVNode { VertexTypedata; ArcNode*firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedefstruct { AdjListvertices; intvexnum,arcnum; intkind; }ALGraph; intCreateDG(ALGraph&G) { intIncInfo,i,j,k,v1,v2; printf("输入顶点数G.vexnum: "); scanf("%d",&G.vexnum); printf("输入弧数G.arcnum: "); scanf("%d",&G.arcnum); printf("输入弧的信息(0fornone): "); scanf("%d",&IncInfo); for(i=0;i { G.vertices[i].data=i; G.vertices[i].firstarc=NULL; } printf("请输入所有边\n"); for(k=0;k { printf("请输入第%d条边: ",k+1); scanf("%d%d",&v1,&v2); i=v1;j=v2; i--;j--; ArcNode*p; p=(ArcNode*)malloc(sizeof(ArcNode));; if(! p) { printf("Overflow! ");return(0); } p->adjvex=j; p->nextarc=G.vertices[i].firstarc; p->info=NULL; G.vertices[i].firstarc=p; if(IncInfo) { printf("Pleaseinputtheinfo: "); scanf("%s",*(p->info)); } } return(OK); } voidprint_Great(ALGraph&G) { inti; ArcNode*p; printf("TheGraphis: \n"); for(i=0;i { printf("%d",i+1); p=G.vertices[i].firstarc; while(p) { printf("->%d",(p->adjvex)+1); p=p->nextarc; } printf("\n"); } } voidmain() { ALGraphG; printf("DG\n"); printf("============================\n"); if(CreateDG(G))print_Great(G); elseprintf("failed,OVER\n"); } (2)程序运行结果: (3)结果分析: 运行良好。 任务二: 用邻接表的存储结构创建一个如图2所示的图a和b,分别打印出这两个图的深度优先遍历和广度优先遍历的结点信息序列。 图2 (1)源代码如下: #defineMAX_VERTEX_NUM20 #defineOK1 #defineMaxSize100 #include #include typedefintQElemType; typedefenum{DG,DN,UDG,UDN}GraphKind; typedefintEType; typedefintInfoType; typedefintVertexType; typedefstructArcNode { intadjvex; structArcNode*nextarc; InfoType*info; }ArcNode; typedefstructVNode { VertexTypedata; ArcNode*firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedefstruct { AdjListvertices; intvexnum,arcnum; intkind; }ALGraph; typedefstruct { QElemType*base; intfront; intrear; }SqQueue; intCreateDG(ALGraph&G) { intIncInfo,i,j,k,v1,v2; printf("输入顶点数G.vexnum"); scanf("%d",&G.vexnum); printf("输入弧数G.arcnum: "); scanf("%d",&G.arcnum); printf("请输入弧的信息数: "); scanf("%d",&IncInfo); for(i=0;i { G.vertices[i].data=i; G.vertices[i].firstarc=NULL; } printf("请输入所有的边\n"); for(k=0;k { printf("输入第%d条边",k+1); scanf("%d%d",&v1,&v2); i=v1;j=v2; ArcNode*p; p=(ArcNode*)malloc(sizeof(ArcNode)); if(! p) { printf("Overflow! ");return(0); } p->adjvex=j; p->nextarc=G.vertices[i].firstarc; p->info=NULL; G.vertices[i].firstarc=p; if(IncInfo) { printf("Pleaseinputtheinfo: "); scanf("%s",*(p->info)); } } return(OK); } voidprint_Great(ALGraph&G) { inti; ArcNode*p; printf("TheGraphis: \n"); for(i=0;i { printf("%d",i); p=G.vertices[i].firstarc; while(p) { printf("->%d",p->adjvex); p=p->nextarc; } printf("\n"); } } voidDFS(ALGraphG,intv,int*visited) {intw; visited[v]=1;//v printf("%d->",v); for(w=G.vertices[v].data;G.vertices[v].firstarc! =NULL; w=G.vertices[v].firstarc->adjvex, G.vertices[v].firstarc=G.vertices[v].firstarc->nextarc) if(visited[w]==0) DFS(G,w,visited); } voidDFSTraverse(ALGraphG) {intv; intvisited[MAX_VERTEX_NUM]; for(v=0;v visited[v]=0; for(v=1;v if(visited[v]==0) DFS(G,v,visited); } voidInitQueue(SqQueue*Q) { Q->base=(QElemType*)malloc(MaxSize*sizeof(QElemType)); if(! Q->base)return; Q->front=Q->rear=0; return; } intEnQueue(SqQueue&Q,QElemTypee) {if((Q.rear+1)%MaxSize==Q.front) {printf("队列已满! \n"); return0; } Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MaxSize; return(OK); } intDeQueue(SqQueue&Q,QElemType&e) { if(Q.front==Q.rear)return0; e=Q.base[Q.front]; Q.front=(Q.front+1)%MaxSize; return(OK); } voidBFSTraverse(ALGraphG) {intv,w,u; intvisited[MAX_VERTEX_NUM]; SqQueueQ; for(v=0;v visited[v]=0; InitQueue(&Q); for(v=0;v if(visited[v]==0) {visited[v]=1; printf("%d-->",v+1); EnQueue(Q,v); while(! Q.base==Q.front) {DeQueue(Q,u); for(w=G.vertices[u].data; G.vertices[u].firstarc! =NULL; w=G.vertices[u].firstarc->adjvex, G.vertices[u].firstarc=G.vertices[u].firstarc->nextarc) if(visited[w]==0) {visited[w]=1; printf("%d-->",w+1); EnQueue(Q,w); } } } } voidmain() {ALGraphG; printf("===============\n"); CreateDG(G); print_Great(G); printf("DFSTraverseisasfollows: \n"); printf("Begin->"); DFSTraverse(G); printf("\nBFSTraverseisasfollows: \n"); printf("Begin->"); BFSTraverse(G); printf("\n"); } (2)程序运行结果: (3)结果分析: 运行良好。 任务三: 用Prim算法求图1所示的图的最小生成树。 (1)源代码如下: #include structEdge { intfrom,to,weight; }; Edgeedge[100],temp; inti,j,n,m;intp[100]; intseek(intx) { if(p[x]==x) returnx; else returnp[x]=seek(p[x]); } intKruskal() { intx,y,k=0; for(i=0;i<100;i++) p[i]=i; for(i=0;i { x=seek(edge[k].from); y=seek(edge[k].to); if(x! =y) { printf("(%d,%d): %d\n",edge[k].from,edge[k].to,edge[k].weight); p[x]=y; } k++; } return0; } intmain() { printf("Pleaseinputthenumberofthenodesandedges: \n"); scanf("%d%d",&n,&m); printf("Pleaseinputtheedgesanditsweight: \n"); for(i=0;i { scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].weight); } for(i=0;i for(j=i+1;j if(edge[i].weight>edge[j].weight) { temp=edge[i]; edge[i]=edge[j]; edge[j]=temp; } printf("Theminimumspanningtreeis: \n"); Kruskal(); return0; } (2)程序运行结果: (3)结果分析: 运行良好。 三、结论(写本次实验的收获) 1、掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法。 2、熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤,并能列出在两种存储结构上按上述两种遍历算法得到的序列。 3、理解最小生成树的概念,能按Prim算法构造最小生成树。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验四 实验