数据结构实验六图.docx
《数据结构实验六图.docx》由会员分享，可在线阅读，更多相关《数据结构实验六图.docx（16页珍藏版）》请在冰点文库上搜索。
数据结构实验六图
实验六图的表示与遍历
一、实验目的
1、掌握图的邻接矩阵和邻接表表示
2、掌握图的深度优先和广度优先搜索方法
3、理解图的应用方法
二、实验内容和要求
1、阅读并运行下面程序，根据输入写出运行结果。
#include
#defineN20
#defineTRUE1
#defineFALSE0
intvisited[N];
typedefstruct/*队列的定义*/
{
intdata[N];
intfront,rear;
}queue;
typedefstruct/*图的邻接矩阵*/
{
intvexnum,arcnum;
charvexs[N];
intarcs[N][N];
}
graph;
voidcreateGraph（graph*g）;/*建立一个无向图的邻接矩阵*/
voiddfs（inti,graph*g）;/*从第i个顶点出发深度优先搜索*/
voidtdfs（graph*g）;/*深度优先搜索整个图*/
voidbfs（intk,graph*g）;/*从第k个顶点广度优先搜索*/
voidtbfs（graph*g）;/*广度优先搜索整个图*/
voidinit_visit（）;/*初始化访问标识数组*/
voidcreateGraph（graph*g）/*建立一个无向图的邻接矩阵*/
{inti,j;
charv;
g->vexnum=0;
g->arcnum=0;
i=0;
printf（"输入顶点序列（以#结束）：
\n"）;
while（（v=getchar（））!
='#'）
{
g->vexs[i]=v;/*读入顶点信息*/
i++;
}
g->vexnum=i;/*顶点数目*/
for（i=0;ivexnum;i++）/*邻接矩阵初始化*/
for（j=0;jvexnum;j++）
g->arcs[i][j]=0;
printf（"输入边的信息：
\n"）;
scanf（"%d,%d",&i,&j）;/*读入边i,j*/
while（i!
=-1）/*读入i,j为－1时结束*/
{
g->arcs[i][j]=1;
g->arcs[j][i]=1;
scanf（"%d,%d",&i,&j）;
}
}
voiddfs（inti,graph*g）/*从第i个顶点出发深度优先搜索*/
{
intj;
printf（"%c",g->vexs[i]）;
visited[i]=TRUE;
for（j=0;jvexnum;j++）
if（（g->arcs[i][j]==1）&&（!
visited[j]））
dfs（j,g）;
}
voidtdfs（graph*g）/*深度优先搜索整个图*/
{
inti;
printf（"\n从顶点%C开始深度优先搜索序列：
",g->vexs[0]）;
for（i=0;ivexnum;i++）
if（visited[i]!
=TRUE）
dfs（i,g）;
}
voidbfs（intk,graph*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;jvexnum;j++）
if（（g->arcs[i][j]==1）&&（!
visited[j]））
{
printf（"%c",g->vexs[j]）;
visited[j]=TRUE;
q->data[q->rear]=j;
q->rear=（q->rear+1）%N;
}
}
}
voidtbfs（graph*g）/*广度优先搜索整个图*/
{
inti;
printf（"\n从顶点%C开始广度优先搜索序列：
",g->vexs[0]）;
for（i=0;ivexnum;i++）
if（visited[i]!
=TRUE）
bfs（i,g）;
}
voidinit_visit（）/*初始化访问标识数组*/
{
inti;
for（i=0;ivisited[i]=FALSE;
}
intmain（）
{
graphga;
inti,j;
createGraph（&ga）;
printf（"无向图的邻接矩阵：
\n"）;
for（i=0;i{
for（j=0;jprintf（"%3d",ga.arcs[i][j]）;
printf（"\n"）;
}
init_visit（）;
tdfs（&ga）;
init_visit（）;
tbfs（&ga）;
return0;
}
▪根据右图的结构验证实验，输入：
ABCDEFGH#
0,1
0,2
0,5
1,3
1,4
2,5
2,6
3,7
4,7
-1,-1
▪运行结果：
2、阅读并运行下面程序，补充拓扑排序算法。
#include
#include
#defineN20
typedefstructedgenode{/*图的邻接表：
邻接链表结点*/
intadjvex;/*顶点序号*/
structedgenode*next;/*下一个结点的指针*/
}edgenode;
typedefstructvnode{/*图的邻接表：
邻接表*/
chardata;/*顶点信息*/
intind;/*顶点入度*/
structedgenode*link;/*指向邻接链表指针*/
}vnode;
voidcreateGraph_list（vnodeadjlist[],int*p）；/*建立有向图的邻接表*/
voidtopSort（vnodeg[],intn）；/*拓扑排序*/
voidcreateGraph_list（vnodeadjlist[],int*p）{/*建立有向图的邻接表*/
inti,j,n,e;
charv;
edgenode*s;
i=0;n=0;e=0;
printf（"输入顶点序列（以#结束）：
\n"）;
while（（v=getchar（））!
='#'）
{
adjlist[i].data=v;/*读入顶点信息*/
adjlist[i].link=NULL;
adjlist[i].ind=0;
i++;
}
n=i;
*p=n;
/*建立邻接链表*/
printf（"\n请输入弧的信息（i=-1结束）：
i,j:
\n"）;
scanf（"%d,%d",&i,&j）;
while（i!
=-1）{
s=（structedgenode*）malloc（sizeof（edgenode））;
s->adjvex=j;
s->next=adjlist[i].link;
adjlist[i].link=s;
adjlist[j].ind++;/*顶点j的入度加1*/
e++;
scanf（"%d,%d",&i,&j）;
}
printf（"邻接表:
"）;
for（i=0;iprintf（"\n%c,%d:
",adjlist[i].data,adjlist[i].ind）;
s=adjlist[i].link;
while（s!
=NULL）{
printf（"->%d",s->adjvex）;
s=s->next;
}
}
}
voidtopSort（vnodeg[],intn）{/*拓扑排序*/
}
intmain（）{
vnodeadjlist[N];
intn,*p;
p=&n;
createGraph_list（adjlist,p）;
return0;
}
▪根据输入，输出有向图的拓扑排序序列。
并画出有向图。
输入:
ABCDEF#
0,1
1,2
2,3
4,1
4,5
-1,-1
▪运行结果：
3、阅读并运行下面程序。
#include
#defineN20
#defineTRUE1
#defineINF32766/*邻接矩阵中的无穷大元素*/
#defineINFIN32767/*比无穷大元素大的数*/
typedefstruct
{/*图的邻接矩阵*/
intvexnum,arcnum;
charvexs[N];
intarcs[N][N];
}
graph;
voidcreateGraph_w（graph*g,intflag）;
voidprim（graph*g,intu）;
voiddijkstra（graphg,intv）;
voidshowprim（）;
voidshowdij（）;
/*建带权图的邻接矩阵,若flag为1则为无向图，flag为0为有向图*/
voidcreateGraph_w（graph*g,intflag）
{
inti,j,w;
charv;
g->vexnum=0;
g->arcnum=0;
i=0;
printf（"输入顶点序列（以#结束）：
\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"）;
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）;
}
}
voidprim（graph*g,intu）/*出发顶点u*/
{
intlowcost[N],closest[N],i,j,k,min;
for（i=0;ivexnum;i++）/*求其他顶点到出发顶点u的权*/
{
lowcost[i]=g->arcs[u][i];
closest[i]=u;
}
lowcost[u]=0;
for（i=1;ivexnum;i++）/*循环求最小生成树中的各条边*/
{min=INFIN;
for（j=0;jvexnum;j++）/*选择得到一条代价最小的边*/
if（lowcost[j]!
=0&&lowcost[j]{
min=lowcost[j];
k=j;
}
printf（"（%c,%c）--%d\n",g->vexs[closest[k]],g->vexs[k],lowcost[k]）;/*输出该边*/
lowcost[k]=0;/*顶点k纳入最小生成树*/
for（j=0;jvexnum;j++）/*求其他顶点到顶点k的权*/
if（g->arcs[k][j]!
=0&&g->arcs[k][j]{
lowcost[j]=g->arcs[k][j];
closest[j]=k;
}
}
}
voiddijkstra（graphg,intv）{/*dijkstra算法求单源最短路径*/
intpath[N][N],dist[N],s[N];
intmindis,i,j,u,k;
for（i=0;idist[i]=g.arcs[v][i];
s[i]=0;
for（j=0;jpath[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;imindis=INFIN;
for（j=0;jif（s[j]==0）
if（dist[j]u=j;
mindis=dist[j];
}
s[u]=1;
for（j=0;jif（（s[j]==0）&&dist[u]+g.arcs[u][j]dist[j]=dist[u]+g.arcs[u][j];
for（k=0;kpath[j][k]=path[u][k];
path[j][j]=1;
}
}
printf（"\n顶点%c->到各顶点的最短路径\n",g.vexs[v]）;
for（i=0;iprintf（"\n顶点%c->顶点%c：
",g.vexs[v],g.vexs[i]）;
if（dist[i]==INF）
printf（"无路径"）;
else{
printf（"%d",dist[i]）;
printf（"经过顶点：
"）;
for（j=0;jif（path[i][j]==1&&i!
=j）
printf（"->%c",g.vexs[j]）;
printf（"->%c\n",g.vexs[i]）;
}
}
}
voidshowprim（）/*最小生成树prim算法演示*/
{
graphga;
createGraph_w（&ga,1）;
prim（&ga,0）;
}
voidshowdij（）{/*dijstra算法演示*/
graphga;
createGraph_w（&ga,0）;
dijkstra（ga,0）;
}
intmain（）{
showprim（）;/*prim算法演示*/
getchar（）;
showdij（）;/*dijstra算法演示*/
return0;
}
▪下面的输入分别验证prim算法和dijstra算法。
输入的第一部分为无向图，求其最小生成树；输入的第二部分为有向图，求其最短路径。
ABCDEF#
0,1,6
0,2,1
0,3,5
1,2,5
1,4,3
2,3,5
2,4,6
2,5,4
3,5,2
4,5,6
-1,-1,-1
ABCDEF#
0,2,10
0,5,100
0,4,30
1,2,5
2,3,50
3,4,20
3,5,10
4,3,20
4,5,60
-1,-1,-1
▪运行结果：
（并画出两个图）
三、实验小结
四、教师评语
升级会员 