数据结构B上机实验四图.docx
《数据结构B上机实验四图.docx》由会员分享，可在线阅读，更多相关《数据结构B上机实验四图.docx（31页珍藏版）》请在冰点文库上搜索。
数据结构B上机实验四图
数据结构上机实验六
实验内容:
图的基本操作
实验要求:
1）图的遍历与基本操作要作为函数被调用.
2）把自己使用的图结构明确的表达出来.
3）基本上实现每个实验题目的要求.
分组要求：
可单独完成，也可两人一组。
实验目的:
1）熟悉C/C++基本编程,培养动手能力.
2）通过实验,加深对图的理解.
评分标准：
1）只完成第一和第二题，根据情况得4，5分；
2）完成前3题，根据情况得5，6分；
3）在2）基础上，选做四）中题目，根据情况得7到10分。
题目:
一）建立一个无向图+遍历+插入
（1）以数组表示法作为存储结构，从键盘依次输入顶点数、弧数与各弧信息建立一个无向图；
（2）对
（1）中生成的无向图进行广度优先遍历并打印结果；
（3）向
（1）中生成的无向图插入一条新弧并打印结果；
二）建立一个有向图+遍历+插入+删除
（1）以邻接表作为图的存储结构，从键盘输入图的顶点与弧的信息建立一个有向图；
（2）对
（1）中生成的有向图进行深度优先遍历并打印结果；
（3）在
（1）中生成的有向图中，分别插入与删除一条弧并打印其结果；
（4）在
（1）中生成的有向图中，分别插入与删除一个顶点并打印结果；
（5）在
（1）中生成的有向图中,各顶点的入度与出度并打印结果；
三）基本应用题
（1）编写算法，判断图中指定的两个顶点是否连通。
（2）编写算法，判断图的连通性。
如果不连通，求连通分量的个数
（3）编写算法，判断图中任意两个顶点的连通性
（4）编写算法，判断图中是否存在回路。
（5）实现图的广度优先搜索算法。
四）高级应用题
（1）实现Prim算法
（2）实现Kruskal算法
（3）实现迪杰斯特拉算法
（4）实现拓扑排序算法
（5）实现关键路径算法
#include
#include
#include
//……………………宏定义……………………
#defineint_max1000
#defineintf999
#definemax20
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineStatusint
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
//……………………标志矩阵定义……………………
intvisited[max];//访问标记
intparent[max];
intindegree[max];//入度
intoutdegree[max];//初度
intve[max];
intfinal[max];
intwe;
//…………邻接矩阵定义………………………
typedefstructArcCell
{
intadj;//权值
char*info;//相关信息
}ArcCell,AdjMatrix[20][20];
typedefstruct
{
charvexs[20];//顶点向量
AdjMatrixarcs;//邻接矩阵
intvexnum,arcnum;//图当前顶点数和弧数
}MGraph_L;
//……………邻接链表表示……………………
typedefstructArcNode//弧结点
{
intadjvex;//该弧所指向的顶点的位置
structArcNode*nextarc;//指向下一条弧的指针
int*info;//该弧相关信息的指针
}ArcNode;
typedefstructvnode//邻接链表顶点头接点
{
chardata;//顶点信息
ArcNode*firstarc;//指向第一条依附该顶点的弧的指针
}vnode,adjlist;
typedefstruct//图的定义
{
adjlistvertices[max];
intvexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;
//…………………………队列定义……………………
typedefstructQnode
{
intdata;//队列数据
structQnode*next;//队列指针
}Qnode,*Queueptr;
typedefstruct
{
Queueptrfront;//队首指针
Queueptrrear;//队尾指针
}Linkqueue;
//……………………………堆栈定义……………………
typedefstructStack
{
int*base;//栈底指针
int*top;//栈顶指针
Statusstacksize;
}SqStack;
//…………………………………最小生成树……………………
typedefstruct{
charadjvex;//顶点信息
intlowcost;//权值
}minside[max];
//…………………………队列基本操作……………………
StatusInitqueue（Linkqueue&q）//初始化队列
{
q.rear=（Queueptr）malloc（sizeof（Qnode））;
q.front=q.rear;
if（!
q.front）
return0;
q.front->next=NULL;
return1;
}
StatusEnqueue（Linkqueue&q,inte）//入队
{
Queueptrp;
p=（Queueptr）malloc（sizeof（Qnode））;
if（!
p）return0;
p->data=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
return1;
}
StatusDequeue（Linkqueue&q,int&e）//出队
{
Queueptrp;
if（q.front==q.rear）return0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if（q.rear==p）q.rear=q.front;
free（p）;
return1;
}
StatusQueueempty（Linkqueueq）//判断队为空
{
if（q.front==q.rear）
return1;
return0;
}
//……………………………堆栈基本操作……………………
StatusCreatStack（SqStack&S）//创建空栈
{
S.base=（int*）malloc（STACK_INIT_SIZE*sizeof（structStack））;
if（!
S.base）return0;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return1;
}
StatusPush（SqStack&S,inte）//元素入栈
{
if（S.top-S.base>=S.stacksize）//栈满,追加存储空间
{
S.base=（int*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（structStack））;
if（!
S.base）return0;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return1;
}
StatusPop（SqStack&S,inte）//出栈元素
{
if（S.top==S.base）return0;
e=*--S.top;
returne;
}
//……………………………数组表示图函数…………………
intLocateVex（MGraph_LG,charv）//查找顶点v的序号
{
inti;
for（i=0;iif（v==G.vexs[i]）
returni;
return-1;
}
intcreateMGraph_L（MGraph_L&G）//创建图用邻接矩阵表示
{
charv1,v2;
inti,j,w;
printf（"--------------创建无向图--------------\n"）;
printf（"请输入无向图G的顶点数和弧数:
"）;
scanf（"%d%d",&G.vexnum,&G.arcnum）;
for（i=0;i{
printf（"输入顶点%d\n",i）;
fflush（stdin）;
scanf（"%c",&G.vexs[i]）;
}
for（i=0;ifor（j=0;j{
G.arcs[i][j].adj=int_max;
G.arcs[i][j].info=NULL;
}
printf（"输入一条边依附的顶点和权:
\n"）;
for（intk=0;k!
=G.arcnum;++k）
{
fflush（stdin）;
scanf（"%c%c%d",&v1,&v2,&w）;//输入一条边依附的两点及权值
i=LocateVex（G,v1）;//确定顶点V1和V2在图中的位置
j=LocateVex（G,v2）;
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
printf（"图G邻接矩阵创建成功!
\n"）;
returnG.vexnum;
}
voidMGraph_Lprint（MGraph_LG）//打印邻接矩阵
{
inti,j;
for（i=0;i!
=G.vexnum;++i）
{
for（j=0;j!
=G.vexnum;++j）
{
if（G.arcs[i][j].adj!
=1000）printf（"%d",G.arcs[i][j].adj）;
else{printf（"∞"）;}
}
printf（"\n"）;
}
}
intFirstAdjVex（MGraph_LG,charv）//顶点V的第一个连接向量
{
inti,j=1000,k;
k=LocateVex（G,v）;//k为顶点v在图G中的序号
for（i=0;iif（G.arcs[k][i].adj!
=j）
returni;
return-1;
}
intNextAdjVex（MGraph_LG,charv,charw）//顶点V的下一个连接向量
{
inti,j=1000,k1,k2;
k1=LocateVex（G,v）;//k1为顶点v在图G中的序号
k2=LocateVex（G,w）;//k2为顶点w在图G中的序号
for（i=k2+1;iif（G.arcs[k1][i].adj!
=j）
returni;
return-1;
}
voidInsertvex（MGraph_L&G,charv1,charv2,intw）//在两个顶点间插入弧
{
inti,j;
i=LocateVex（G,v1）;//确定顶点V1和V2在图中的位置
j=LocateVex（G,v2）;
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
//……………………………无向图的应用………………………
voidConnected（MGraph_LG,charv1,charv2,int&flag）//判断任意两个顶点是否连接
{
intk1,k2;
charw;
k1=LocateVex（G,v1）;//k1为顶点v在图G中的序号
k2=LocateVex（G,v2）;//k2为顶点w在图G中的序号
if（k1<0||k2<0）{printf（"不存在这样的两个顶点\n"）;}
else
{
if（k1==k2）flag=1;
elseif（flag!
=1）flag=-1;
visited[k1]=TRUE;
for（w=FirstAdjVex（G,v1）;w>=0;w=NextAdjVex（G,v1,G.vexs[w]））
if（!
visited[w]）Connected（G,G.vexs[w],v2,flag）;
}
}
intDfs（MGraph_LG,inti）//深度遍历无向图
{
visited[i]=1;
intwe1;
printf（"%c",G.vexs[i]）;
for（we=FirstAdjVex（G,G.vexs[i]）;we>=0;we=NextAdjVex（G,G.vexs[i],G.vexs[we]））
{
we1=we;
if（visited[we]==0）
Dfs（G,we）;
we=we1;
}
return0;
}
intDfstra（MGraph_LG）
{
inti,j,num=0;
for（i=0;i!
=G.vexnum;++i）
{visited[i]=0;}
for（j=0;j!
=G.vexnum;++j）
{
if（visited[j]==0）
{Dfs（G,j）;num++;}
}
returnnum;
}
intFindCycle（MGraph_LG,charv0）//判断图是否有回路
{
intk1;
k1=LocateVex（G,v0）;
visited[k1]=TRUE;
for（we=FirstAdjVex（G,v0）;we>=0;we=NextAdjVex（G,v0,G.vexs[we]））
{
if（!
visited[we]）
{
parent[we]=k1;
returnFindCycle（G,G.vexs[we]）;
}
elseif（we!
=parent[k1]）returnTRUE;
}
returnFALSE;
}
//……………………………无向图的高级应用………………………
intminimum（minsideSZ,MGraph_LG）
{
inti=0,j,k,min;
while（!
SZ[i].lowcost）i++;
min=SZ[i].lowcost;/*将最小权值记在min中*/
k=i;/*把与边关联的生成树外的顶点序号记在k中*/
for（j=i+1;jif（SZ[j].lowcost>0&&min>SZ[j].lowcost）
{
min=SZ[j].lowcost;
k=j;
}
returnk;
}
voidMiniSpanTree_PRIM（MGraph_LG,charu）//Prim最小生成树
{
inti,j,k;
minsideclosedge;
k=LocateVex（G,u）;
for（j=0;j{
closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j].adj;
}
closedge[k].lowcost=0;/*将顶点vk加入生成树中*/
printf（"最小代价生成树的各条边为:
\n"）;
for（i=1;i{
k=minimum（closedge,G）;
printf（"（%c-%c）\n",closedge[k].adjvex,G.vexs[k]）;/*输出最小边及权值*/
closedge[k].lowcost=0;
for（j=0;jif（G.arcs[k][j].adj{
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
//……………………………有向图的链表表示………………………
intlocateVex（ALGraphG,charu）//查找顶点v的序号
{
inti;
for（i=0;iif（u==G.vertices[i].data）
returni;
return-1;
}
intCreateUDG（ALGraph&G1）//用邻接表存储图
{
inti,j,k;
intw;
charva=NULL,vb=NULL;
ArcNode*p;
printf（"请输入图的顶点数，弧数:
"）;
scanf（"%d%d",&G1.vexnum,&G1.arcnum）;
for（i=0;i{
printf（"输入顶点%d\n",i）;
fflush（stdin）;
scanf（"%c",&G1.vertices[i].data）;
G1.vertices[i].firstarc=NULL;
}
printf（"请顺序输入每条弧边的弧头,弧尾和权值:
\n"）;
for（k=0;k{
fflush（stdin）;
scanf（"%c%c%d",&va,&vb,&w）;//输入一条边依附的两点及权值）;
i=locateVex（G1,va）;//弧头
j=locateVex（G1,vb）;//弧尾
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->adjvex=j;
p->info=（int*）malloc（sizeof（int））;
*（p->info）=w;
p->nextarc=G1.vertices[i].firstarc;//插在表头
G1.vertices[i].firstarc=p;
}
printf（"图G1邻接链表创建成功!
\n"）;
returnG1.vexnum;
}
voidUDGprint（ALGraphgra）//打印指向
{
inti;
for（i=0;i!
=gra.vexnum;++i）
{
ArcNode*p;
printf（"顶点%d指向的点的位置:
\n",i）;
p=gra.vertices[i].firstarc;
while（p!
=NULL）
{
printf（"%d",p->adjvex）;
p=p->nextarc;}
printf（"\n"）;
}
}
intfirstAdjVex（ALGraphG,charv）//顶点V的第一个连接向量
{
ArcNode*p;
intv1;
v1=locateVex（G,v）;//v1为顶点v在图G中的序号
p=G.vertices[v1].firstarc;
if（p）
returnp->adjvex;
else
return-1;
}
intnextAdjVex（ALGraphG,charv,intw）//顶点V的第二个连接向量
{
ArcNode*p;
intv1,w1;
v1=locateVex（G,v）;//v1为顶点v在图G中的序号
w1=locateVex（G,w）;//w1为顶点w在图G中的序号
p=G.vertices[v1].firstarc;
while（p&&p->adjvex!
=w1）p=p->nextarc;
if（!
p||!
p->nextarc）//没找到w或w是最后一个邻接点
return-1;
else//p->adjvex==w
returnp->nextarc->adjvex;
}
voidinsertVex（ALGraph&G,charv）//插入一个顶点
{
G.vertices[G.vexnum].data=v;//构造新顶点向量
G.vertices[G.vexnum].firstarc=NULL;
G.vexnum++;//图G的顶点数加1
}
voiddeletevex（ALGraph&G,charv）//删除一个顶点
{
inti,j;
ArcNode*p,*q;
j=locateVex（G,v）;
if（j<0）printf（"没有该顶点!
\n"）;
p=G.vertices[j].firstarc;//删除以v为出度的弧或边
while（p）
{
q=p;
p=p->nextarc;
free（q->info）;
free（q）;
G.arcnum--;//弧或边数减1
}
G.vexnum--;//顶点数减1
for（i=j;iG.vertices[i]=G.vertices[i+1];
for（i=0;i{
p=G.vertices[i].firstarc;//指向第1条弧或边
while（p）//有弧
{
if（p->adjvex==j）
{
if（p==G.vertices[i].firstarc）//待删结点是第1个结点
{
升级会员 