数据结构图.docx
- 文档编号:4082606
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:23
- 大小:123.80KB
数据结构图.docx
《数据结构图.docx》由会员分享,可在线阅读,更多相关《数据结构图.docx(23页珍藏版)》请在冰点文库上搜索。
数据结构图
常熟理工学院
《数据结构与算法》实验指导与报告书
_2017-2018_____学年第__1__学期
专业:
物联网工程
实验名称:
实验七图
实验地点:
N6-210
*******
计算机科学与工程学院
2017
实验七图
【实验目的】
1、掌握图的邻接矩阵和邻接表表示。
2、掌握图的深度优先和广度优先搜索方法。
3、掌握图的最小生成树Prim算法。
4、掌握图的拓扑排序算法。
5、掌握图的单源最短路径dijkstra算法。
【实验学时】
4-6学时
【实验预习】
回答以下问题:
1、写出图7-1无向图的邻接矩阵表示。
2、写出图7-2有向图的邻接表表示。
3、写出图7-1的深度优先搜索序列和广度优先搜索序列。
深度优先搜索序列:
A,C,B,D,E,F,G,H
广度优先搜索序列:
A,B,C,D,E,F,G,H,
4、写出图7-2的拓扑序列,说明该有向图是否有环?
拓扑序列:
EABCD
该有向图没有环
5、根据图7-3,写出其最小生成树。
图7-3无向带权图G3
6、根据图7-4,求从顶点A到其他顶点的单源最短路径。
X`图7-4有向带权图G4
单源最短路径:
AC=50:
AED=30:
AE=60:
AEDF
【实验内容和要求】
1、编写程序exp7_1.c,实现图的邻接矩阵存储及图的深度优先搜索和广度优先搜索。
以图7-1的无向图为例,补充完整程序,调试运行并写出运行结果。
运行结果:
(包括输入数据)
exp7_1.c参考程序如下:
#include
#defineN20
#defineTRUE1
#defineFALSE0
#defineMAX100
intvisited[N];/*访问标志数组*/
typedefstruct{/*辅助队列的定义*/
intdata[N];
intfront,rear;
}queue;
typedefstruct{/*图的邻接矩阵表示*/
intvexnum,arcnum;
charvexs[N];
intarcs[N][N];
}MGraph;
voidcreateGraph(MGraph*g);/*建立一个无向图的邻接矩阵*/
voiddfs(inti,MGraph*g);/*从第i个顶点出发深度优先搜索*/
voidtdfs(MGraph*g);/*深度优先搜索整个图*/
voidbfs(intk,MGraph*g);/*从第k个顶点广度优先搜索*/
voidtbfs(MGraph*g);/*广度优先搜索整个图*/
voidinit_visit();/*初始化访问标识数组*/
voidcreateGraph(MGraph*g){/*建立一个无向图的邻接矩阵*/
inti=0,j,e=0;
charv;
g->vexnum=0;
g->arcnum=0;
printf("\n输入顶点序列(以#结束):
\n");
while((v=getchar())!
='#'){
g->vexs[i]=v;/*读入顶点信息*/
i++;
}
g->vexnum=i;/*顶点数目*/
for(i=0;i
for(j=0;j
g->arcs[i][j]=0;/*
(1)-邻接矩阵元素初始化为0*/
printf("\n输入边的信息(顶点序号,顶点序号),以(-1,-1)结束:
\n");
scanf("%d,%d",&i,&j);/*读入边(i,j)*/
while(i!
=-1){/*读入i为-1时结束*/
g->arcs[i][j]=1;/*
(2)-i,j对应边等于1*/
e++;
scanf("%d,%d",&i,&j);
}
g->arcnum=e;/*边数目*/
}/*createGraph*/
/*(3)---从第i个顶点出发深度优先搜索,补充完整算法*/
voiddfs(inti,MGraph*g)
{
intj;
printf("%c",g->vexs[i]);
visited[i]=1;
for(j=0;j
if((g->arcs[i][j]==1)&&(!
visited[j]))
dfs(j,g);
}
/*dfs*/
voidtdfs(MGraph*g){/*深度优先搜索整个图*/
inti;
printf("\n从顶点%C开始深度优先搜索序列:
",g->vexs[0]);
for(i=0;i
if(visited[i]!
=1)/*(4)---对尚未访问过的顶点进行深度优先搜索*/
dfs(i,g);
printf("\n");
}/*tdfs*/
voidbfs(intk,MGraph*g){/*从第k个顶点广度优先搜索*/
inti,j;
queueqlist,*q;
q=&qlist;
q->rear=0;
q->front=0;
printf("%c",g->vexs[k]);
visited[k]=TRUE;
q->data[q->rear]=k;
q->rear=(q->rear+1)%N;
while(q->rear!
=q->front){/*当队列不为空,进行搜索*/
i=q->data[q->front];
q->front=(q->front+1)%N;
for(j=0;j
if((g->arcs[i][j]==1)&&(!
visited[j])){
printf("%c",g->vexs[j]);
visited[j]=TRUE;
q->data[q->rear]=j;/*(5)---刚访问过的结点入队*/
q->rear=(q->rear+1)%MAX;/*(6)---修改队尾指针*/
}
}
}/*bfs*/
voidtbfs(MGraph*g){/*广度优先搜索整个图*/
inti;
printf("\n从顶点%C开始广度优先搜索序列:
",g->vexs[0]);
for(i=0;i
if(visited[i]!
=TRUE)
bfs(i,g);/*从顶点i开始广度优先搜索*/
printf("\n");
}/*tbfs*/
voidinit_visit(){/*初始化访问标识数组*/
inti;
for(i=0;i visited[i]=FALSE; } intmain(){ MGraphga; inti,j; printf("***********图邻接矩阵存储和图的遍历***********\n"); printf("\n1-输入图的基本信息: \n"); createGraph(&ga); printf("\n2-无向图的邻接矩阵: \n"); for(i=0;i for(j=0;j printf("%3d",ga.arcs[i][j]); printf("\n"); } printf("\n3-图的遍历: \n"); init_visit();/*初始化访问数组*/ tdfs(&ga);/*深度优先搜索图*/ init_visit(); tbfs(&ga);/*广度优先搜索图*/ return0; } 2、编写程序exp7_2.c,实现图的邻接表存储和拓扑排序算法。 以图7-2的有向图为例,补充完整程序,调试运行并写出运行结果。 运行结果: (包括输入数据) exp7_2.c程序代码参考如下: #include #include #defineN20 /*图的邻接表: 邻接链表结点*/ typedefstructEdgeNode{ intadjvex;/*顶点序号*/ structEdgeNode*next;/*下一个结点的指针*/ }EdgeNode; /*图的邻接表: 邻接表*/ typedefstructVNode{ chardata;/*顶点信息*/ intind;/*顶点入度*/ structEdgeNode*link;/*指向邻接链表指针*/ }VNode; typedefstructALgraph{/*图的邻接表*/ intvexnum,arcnum;/*顶点数、弧数*/ VNodeadjlist[N]; }ALGraph; voidcreateGraph_list(ALGraph*g);/*建立有向图的邻接表*/ voidtopSort(ALGraph*g);/*拓扑排序*/ /*建立有向图的邻接表*/ voidcreateGraph_list(ALGraph*g){ inti,j,e; charv; EdgeNode*s; i=0; e=0; printf("\n输入顶点序列(以#结束): \n"); while((v=getchar())! ='#'){ g->adjlist[i].data=v;/*读入顶点信息*/ g->adjlist[i].link=NULL; g->adjlist[i].ind=0; i++; } g->vexnum=i;/*建立邻接链表*/ printf("\n请输入弧的信息(顶点序号,顶点序号),以(-1,-1)结束: \n"); scanf("%d,%d",&i,&j); while(i! =-1){ s=(structEdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex=j; s->next=g->adjlist[i].link;;/* (1)s插入链表*/ g->adjlist[i].link=s; g->adjlist[j].ind++;/* (2)顶点j的入度加1*/ e++; scanf("%d,%d",&i,&j); } g->arcnum=e; }/*createGraph_list*/ voidtopSort(ALGraph*g){/*拓扑排序*/ inti,j,k,top=0,m=0,s[N];/*m为拓扑排序输出的结点数*/ EdgeNode*p; for(i=0;i if(! g->adjlist[i].ind) { /*(3)入度为0的顶点入栈*/ s[top++]=i; } printf("\n输出拓扑序列: "); while(top>0){ j=s[--top]; printf("%c",g->adjlist[j].data); m++; p=g->adjlist[j].link; while(p! =NULL){ k=p->adjvex; g->adjlist[k].ind--;/*顶点k入度减1*/ if(g->adjlist[k].ind==0)/*顶点k入度为0,进栈*/ s[top++]=k; p=p->next; } } printf("\n共输出%d个顶点\n",m); if(m printf("图中有环! "); else printf("图中无环! "); }/*topSort*/ intmain(){ ALGraphg; inti; EdgeNode*s; printf("***********图的邻接表存储结构和拓扑排序***********\n"); printf("\n1-输入图的基本信息: \n"); createGraph_list(&g);/*创建图的邻接表存储结构*/ printf("\n2-图的邻接表: "); for(i=0;i printf("\n%c,%d: ",g.adjlist[i].data,g.adjlist[i].ind); s=g.adjlist[i].link; while(s! =NULL){ printf("->%d",s->adjvex); s=s->next; } } printf("\n"); printf("\n3-根据图的邻接表实现拓扑排序: \n"); topSort(&g);/*进行拓扑排序*/ return0; } (3)调试下面给出的图的信息,写出运行结果,画出该有向图。 ABCDEF# 1,0 1,3 2,1 2,5 3,2 3,4 3,5 4,0 5,0 5,1 5,4 -1,-1 3、编写程序exp7_3.c,实现带权图的存储、图的最小生成树及单源最短路径算法。 以图7-3(求该图最小生成树)和图7-4(求该图的单源最短路径)为例,补充完整程序,调试运行并写出运行结果。 运行结果: (包括输入数据) exp7_3.c程序代码参考如下: #include #defineN20 #defineTRUE1 #defineINF10002766/*邻接矩阵中的无穷大元素*/ #defineINFIN10002767/*比无穷大元素大的数*/ typedefstruct{/*图的邻接矩阵表示*/ intvexnum,arcnum; charvexs[N]; intarcs[N][N]; }MGraph; voidprintPath(MGraphg,intstartVex,intEndVex,intpath[][N]);/*打印最短路径*/ voidcreateMGraph_w(MGraph*g,intflag);/*建带权图的邻接矩阵*/ voidprim(MGraph*g,intu);/*求最小生成树Prim算法,u为出发顶点*/ voiddijkstra(MGraphg,intv);/*dijkstra算法求单源最短路径*/ voidcreateMGraph_w(MGraph*g,intflag){ /*建带权图的邻接矩阵,若flag为1则为无向图,flag为0为有向图*/ inti,j,w; charv; g->vexnum=0; g->arcnum=0; i=0; printf("\n输入顶点序列(以#结束): \n"); while((v=getchar())! ='#'){ g->vexs[i]=v;/*读入顶点信息*/ i++; } g->vexnum=i; for(i=0;i<6;i++)/*邻接矩阵初始化*/ for(j=0;j<6;j++) g->arcs[i][j]=INF; printf("\n输入边的信息: (顶点,顶点,权值),以(-1,-1,-1)结束\n"); scanf("%d,%d,%d",&i,&j,&w);/*读入边(i,j,w)*/ while(i! =-1){/*读入i为-1时结束*/ g->arcs[i][j]=w; if(flag==1) g->arcs[j][i]=w; scanf("%d,%d,%d",&i,&j,&w); } }/*createMGraph_w*/ voidprim(MGraph*g,intu){/*求最小生成树Prim算法,u为出发顶点*/ intlowcost[N],closest[N],i,j,k,min; for(i=0;i lowcost[i]=g->arcs[u][j];/* (1)-顶点i到u的代价最小的边权值*/ closest[i]=u; } lowcost[u]=0; printf("\n最小生成树: \n"); for(i=1;i min=INFIN; for(j=0;j if(lowcost[j]! =0&&lowcost[j] min=lowcost[j];/* (2)-修改当前最小边*/ k=j; } printf("(%c,%c)--%d\n",g->vexs[closest[k]],g->vexs[k],lowcost[k]);/*输出该边*/ lowcost[k]=0;/*顶点k纳入最小生成树*/ for(j=0;j if(g->arcs[k][j]! =0&&g->arcs[k][j] lowcost[j]=g->arcs[k][j];/*(3)-其他顶点到k的代价最小的边权值*/ closest[j]=k; } } }/*prim*/ voidprintPath(MGraphg,intstartVex,intEndVex,intpath[][N]){ intstack[N],top=0;//堆栈 inti,k,j; intflag[N];//输出路径顶点标志 k=EndVex; for(i=0;i j=startVex; printf("%c",g.vexs[j]); flag[j]=1; stack[top++]=k; while(top>0){//找j到k的路径 for(i=0;i if(path[k][i]==1&&flag[i]==0){//j到k的路径含有i顶点 if(g.arcs[j][i]! =INF){//j到i的路径含有中间顶点 printf("->%c(%d)",g.vexs[i],g.arcs[j][i]);//输出j到k路径顶点i flag[i]=1; j=i; k=stack[--top]; break; } else if(i! =k)stack[top++]=i; } } } if(flag[k]==0)printf("->%c(%d)",g.vexs[k],g.arcs[j][k]); } voiddijkstra(MGraphg,intv){/*dijkstra算法求单源最短路径*/ ints[N],path[N][N],dist[N]; intmindis,i,j,u,k; for(i=0;i dist[i]=g.arcs[v][i]; s[i]=0; for(j=0;j path[i][j]=0; if(dist[i] path[i][v]=1; path[i][i]=1; } } dist[v]=0; s[v]=1; for(i=0,u=1;i mindis=INFIN; for(j=0;j if(s[j]==0) if(dist[j] u=j; mindis=dist[j]; } s[u]=1; for(j=0;j if((s[j]==0)&&dist[u]+g.arcs[u][j] dist[j]=dist[u]+g.arcs[u][j]; for(k=0;k path[j][k]=path[u][k]; path[j][j]=1; } } printf("\n顶点%c->到各顶点的最短路径\n",g.vexs[v]); for(i=0;i if(i==v)continue; printf("\n顶点%c->顶点%c: ",g.vexs[v],g.vexs[i]); if(dist[i]==INF||dist[i]==0) printf("无路径"); else{ printf("%d",dist[i]); printf("经过顶点: "); printPath(g,v,i,path);//输出v到i的路径 } } }/*dijkstra*/ intmain(){ intselect; MGraphga; do{ printf("\n***************MENU******************\n"); printf("1.图的最小生成树-Prim算法\n"); printf("2.图的单源最短路径-dijstra算法\n"); printf("0.EXIT"); printf("\n***************MENU******************\n"); printf("\ninputchoice: "); scanf("%d",&select); getchar(); switch(select){ case1: printf("\n1-图的最小生成树-Prim算法\n"); printf("\n输入带权图的基本信息: \n"); createMGraph_w(&ga,1); prim(&ga,0); break; case2: printf("\n2-图的单源最短路径-dijstra算法\n"); printf("\n输入带权图的基本信息: \n"); createMGraph_w(&ga,0); dijkstra(ga,0); break; default: break; } }while(select); return0; } 【拓展实验】 4、编写算法,实现最小生成树的Kr
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 结构图