图的基本操作与kruskal最小生成树实验报告.docx
- 文档编号:6257255
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:25
- 大小:151.46KB
图的基本操作与kruskal最小生成树实验报告.docx
《图的基本操作与kruskal最小生成树实验报告.docx》由会员分享,可在线阅读,更多相关《图的基本操作与kruskal最小生成树实验报告.docx(25页珍藏版)》请在冰点文库上搜索。
图的基本操作与kruskal最小生成树实验报告
数
据
结
构
实验五图的基本操作
一、实验目的
1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、熟练掌握图的两种遍历算法。
二、实验内容
[问题描述]
对给定图,实现图的深度优先遍历和广度优先遍历。
[基本要求]
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。
【测试数据】
由学生依据软件工程的测试技术自己确定。
三、实验前的准备工作
1、掌握图的相关概念。
2、掌握图的逻辑结构和存储结构。
3、掌握图的两种遍历算法的实现。
四、详细设计
五、源程序
#defineINFINITY10000
#defineMAX_VERTEX_NUM40
#defineMAX40
#include
#include
#include
#include
typedefstructArCell
{
intadj;
}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
charname[20];
}infotype;
typedefstruct
{
infotypevexs[MAX_VERTEX_NUM];
AdjMatrixarcs;
intvexnum,arcnum;
}MGraph;
intLocateVex(MGraph*G,char*v)
{intc=-1,i;
for(i=0;i
if(strcmp(v,G->vexs[i].name)==0)
{c=i;break;}
returnc;
}
MGraph*CreatUDN(MGraph*G)//初始化图,接受用户输入
{
inti,j,k,w;
charv1[20],v2[20];
printf("请输入图的顶点数,弧数:
");
scanf("%d%d",&G->vexnum,&G->arcnum);
printf("结点名字:
\n");
for(i=0;i
printf("No.%d:
",i+1);
scanf("%s",G->vexs[i].name);}
for(i=0;i
for(j=0;j
G->arcs[i][j].adj=INFINITY;
printf("请输入一条边依附的两个顶点和权值:
\n");
for(k=0;k
{printf("第%d条边:
\n",k+1);
printf("起始结点:
");
scanf("%s",v1);
printf("结束结点:
");
scanf("%s",v2);
printf("边的权值:
");
scanf("%d",&w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
if(i>=0&&j>=0){
G->arcs[i][j].adj=w;
G->arcs[j][i]=G->arcs[i][j];
}}
returnG;
}
intFirstAdjVex(MGraph*G,intv)
{
inti;
if(v<=0&&v
for(i=0;i
if(G->arcs[v][i].adj!
=INFINITY)
returni;
}
return-1;
}
voidVisitFunc(MGraph*G,intv)
{
printf("%s",G->vexs[v].name);
}
intNextAdjVex(MGraph*G,intv,intw)
{
intk;
if(v>=0&&v
{
for(k=w+1;k
if(G->arcs[v][k].adj!
=INFINITY)
returnk;
}
return-1;
}
intvisited[MAX];
voidDFS(MGraph*G,intv)//从第v个顶点出发递归地深度优先遍历图G
{
intw;
visited[v]=1;
VisitFunc(G,v);//访问第v个结点
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
if(!
visited[w]){
DFS(G,w);
printf("%d",G->arcs[v][w].adj);}
}
voidDFSTraverse(MGraph*G,char*s)//深度优先遍历
{intv,k;
for(v=0;v
visited[v]=0;
k=LocateVex(G,s);
if(k>=0&&k
for(v=k;v>=0;v--){
if(!
visited[v])
DFS(G,v);}
for(v=k+1;v
if(!
visited[v])
DFS(G,v);
}
}
typedefstructQnode
{
intvexnum;
structQnode*next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
intInitQueue(LinkQueue*Q)
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
if(!
Q->front)exit(0);
Q->front->next=NULL;
return1;
}
voidEnQueue(LinkQueue*Q,inta)
{
QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode));
if(!
p)exit(0);
p->vexnum=a;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
intDeQueue(LinkQueue*Q,int*v)
{QueuePtrp;
if(Q->front==Q->rear)
{printf("结点不存在!
\n");exit(0);}
p=Q->front->next;
*v=p->vexnum;
Q->front->next=p->next;
if(Q->rear==p)
Q->front=Q->rear;
return*v;
}
intQueueEmpty(LinkQueue*Q)
{
if(Q->rear==Q->front)
return0;
return1;
}
intVisited[MAX];
voidBFSTraverse(MGraph*G,char*str)//广度优先遍历
{intw,u,v,k;
LinkQueueQ,q;
for(v=0;v
InitQueue(&Q);InitQueue(&q);
k=LocateVex(G,str);
for(v=k;v>=0;v--)
if(!
Visited[v])
{
Visited[v]=1;
VisitFunc(G,v);
EnQueue(&Q,v);//v入队
while(!
QueueEmpty(&Q))
{
DeQueue(&Q,&u);//出队
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
if(!
Visited[w])
{
Visited[w]=1;
VisitFunc(G,v);
EnQueue(&Q,w);
}
}
}
for(v=k+1;v
if(!
Visited[v])
{
Visited[v]=1;
VisitFunc(G,v);
EnQueue(&Q,v);//v入队
while(!
QueueEmpty(&Q))
{
DeQueue(&Q,&u);//出队
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
if(!
Visited[w])
{
Visited[w]=1;
VisitFunc(G,v);
EnQueue(&Q,w);
}
}
}
}
voidmain()
{
MGraph*G,b;
charv[10];
G=CreatUDN(&b);
printf("请输入起始结点名称:
");
scanf("%s",v);
printf("\n深度优先遍历:
\n");
DFSTraverse(G,v);
printf("\n广度优先遍历:
\n");
BFSTraverse(G,v);
getch();
}
六、测试数据及调试
实验六图的应用
一、实验目的
1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、掌握如何应用图解决各种实际问题。
二、实验内容
本次实验提供2个题目,学生可以任选一个!
题目一:
最小生成树问题
[问题描述]
若要在n个城市之间建设通信网络,只需要假设n-1条线路即可。
如何以最低的经济代价建设这个通信网,是一个网的最小生成树问题。
[基本要求]
1.利用克鲁斯卡尔算法求网的最小生成树。
2.要求输出各条边及它们的权值。
[实现提示]
通信线路一旦建成,必然是双向的。
因此,构造最小生成树的网一定是无向网。
设图的顶点数不超过30个,并为简单起见,网中边的权值设成小于100的整数。
图的存储结构的选取应和所作操作相适应。
为了便于选择权值最小的边,此题的存储结构既不选用邻接矩阵的数组表示法,也不选用邻接表,而是以存储边(带权)的数组表示图
三、详细设计
。
存储结构
该函数包含三个结构体,即存储顶点、存储边和存储图的结构体,其结构体分别如下所示:
1.顶点和边的存储表示
用字符串name表示顶点信息,num表示顶点的序号。
structnode{
charname[10];
intnum;
}vex[20];
用整型begin和end表示边的起点和终点,weight表示边的权值。
typedefstruct
{
intbegin;
intend;
intweight;
}edge;
2.图的邻接矩阵存储表示
用整型adj表示顶点间的关系,weight表示权值。
typedefstruct
{
intadj;
intweight;
}AdjMatrix[MAX][MAX];
用arc表示邻接矩阵,vexnum和arcnum表示图当前的顶点数和边数。
typedefstruct
{
AdjMatrixarc;
intvexnum,arcnum;
}MGraph;
3.2算法描述
该算法是建立一个带权的无向图,并用Kruskal算法求该图的最小生成树,用父结点和子女结点集的形式输出最小生成树。
1.无向带权图的建立
图的存储结构如上所示,;用adj是否为1判断两顶点间是否有边,adj为1时表示有边,反之没有边,vexnum和arcnum分别表示顶点数和边数,name和num分别表示顶点信息和顶点序号,建图的算法如下所示:
voidCreatGraph(MGraph*G)
{
inti,j,n,h,m,k;
charu[MAX],v[MAX];
printf("请输入边数和顶点数:
");
scanf("%d%d",&G->arcnum,&G->vexnum)
for(i=1;i<=G->vexnum;i++)//初始化图
{
for(j=1;j<=G->vexnum;j++)
{
G->arc[i][j].adj=G->arc[j][i].adj=0;
}
}
printf("\n请输入顶点的信息:
");
for(n=1;n<=G->vexnum;n++)
{
scanf("%s",vex[n].name);
vex[n].num=n;
}
for(i=1;i<=G->arcnum;i++)
{
printf("\n请输入有边的2个顶点:
");
scanf("%s",v);
scanf("%s",u);
for(k=1;k<=G->vexnum;k++)
{
if(strcmp(v,vex[k].name)==0)
{m=vex[k].num;}
if(strcmp(u,vex[k].name)==0)
{h=vex[k].num;}
}
G->arc[m][h].adj=G->arc[h][m].adj=1;
getchar();
printf("\n请输入%s与%s之间的权值:
",vex[m].name,vex[h].name);
scanf("%d",&G->arc[m][h].weight);
}
printf("邻接矩阵为:
\n");
for(i=1;i<=G->vexnum;i++)
{
for(j=1;j<=G->vexnum;j++)
{
printf("%d",G->arc[i][j].adj);
}
printf("\n");
}
}
2.Kruskal算法
克鲁斯卡尔算法:
假设连通网N=(V,{E}),则令最小生成树的起始状态为只有n个顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。
在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加到T中,否则舍去此边而选择下一条代价最小的边。
以此类推,直至T中所有的顶点都在同一连通分量上为止。
算法代码如下所示:
voidMiniSpanTree(MGraph*G)
{
inti,j,n,m;
intk=1;
intparent[M];
edgeedges[M];
for(i=1;i
{
for(j=i+1;j<=G->vexnum;j++)
{
if(G->arc[i][j].adj==1)
{
edges[k].begin=i;
edges[k].end=j;
edges[k].weight=G->arc[i][j].weight;
k++;
}
}
}
sort(edges,G);
for(i=1;i<=G->arcnum;i++)
{
parent[i]=0;
}
printf("最小生成树为:
\n");
for(i=1;i<=G->arcnum;i++)
{
n=Find(parent,edges[i].begin);
m=Find(parent,edges[i].end);
if(n!
=m)
{
parent[n]=m;
printf("<<%s,%s>>%d\n",vex[edges[i].begin].name,vex[edges[i].end].name,edges[i].weight);
}
}
}
intFind(int*parent,intf)
{
while(parent[f]>0)
{
f=parent[f];
}
returnf;
}
3.用起泡法对边权值按从小到大的顺序排列
voidsort(edgeedges[],MGraph*G)
{
inti,j;
inttemp;
for(i=1;i
{
for(j=i+1;j<=G->arcnum;j++)
{
if(edges[i].weight>edges[j].weight)
{
temp=edges[i].begin;
edges[i].begin=edges[j].begin;
edges[j].begin=temp;
temp=edges[i].end;
edges[i].end=edges[j].end;
edges[j].end=temp;
temp=edges[i].weight;
edges[i].weight=edges[j].weight;
edges[j].weight=temp;
}
}
}
四、调试
4.1调试过程
经过我仔细的调试发现以下三个问题
1、问题一:
求出图中的最小值
现象:
求出的最小值是0
原因:
图中没有连通的两个顶点之间的权值赋值为0
2、问题二:
求最小生成树时,出现漏洞
现象:
对某些二叉树能求出最小生成树,但不能普遍适应
原因:
对于找最小生成树边的各种可能没有考虑全面,代码才没有广泛的适应性
3、问题三:
两个顶点之间的边是否是最小生成树的边
现象:
代码的功能不能分辨出是否是最小生成树的边
原因:
把简单的代码写的很复杂,从而杂乱无章出现错误。
4.2程序执行过程
1.图4.2.1所示为一10条边6个顶点的无向带权图的顶点间的关系,图4.2.2为输入顶点及边权值的运行情况,图4.2.3为邻接矩阵和最小生成树的输出结果。
运行结果:
五、源代码
#include
#include
#include
#include
#defineM20
#defineMAX20
structnode{
charname[10];
intnum;
}vex[20];
typedefstruct
{
intbegin;
intend;
intweight;
}edge;
typedefstruct
{
intadj;
intweight;
}AdjMatrix[MAX][MAX];
typedefstruct
{
AdjMatrixarc;
intvexnum,arcnum;
}MGraph;
voidCreatGraph(MGraph*);
voidMiniSpanTree(MGraph*);
voidsort(edge*,MGraph*);
intFind(int*,int);
voidCreatGraph(MGraph*G)
{
inti,j,n,h,m,k;
charu[MAX],v[MAX];
printf("请输入边数和顶点数:
");
scanf("%d%d",&G->arcnum,&G->vexnum);
for(i=1;i<=G->vexnum;i++)//初始化图
{
for(j=1;j<=G->vexnum;j++)
{
G->arc[i][j].adj=G->arc[j][i].adj=0;
}
}
printf("\n请输入顶点的信息:
");
for(n=1;n<=G->vexnum;n++)
{
scanf("%s",vex[n].name);
vex[n].num=n;
}
for(i=1;i<=G->arcnum;i++)
{
printf("\n请输入有边的2个顶点:
");
scanf("%s",v);
scanf("%s",u);
for(k=1;k<=G->vexnum;k++)
{
if(strcmp(v,vex[k].name)==0)
{m=vex[k].num;}
if(strcmp(u,vex[k].name)==0)
{h=vex[k].num;}
}
G->arc[m][h].adj=G->arc[h][m].adj=1;
getchar();
printf("\n请输入%s与%s之间的权值:
",vex[m].name,vex[h].name);
scanf("%d",&G->arc[m][h].weight);
}
printf("邻接矩阵为:
\n");
for(i=1;i<=G->vexnum;i++)
{
for(j=1;j<=G->vexnum;j++)
{
printf("%d",G->arc[i][j].adj);
}
printf("\n");
}
}
voidsort(edgeedges[],MGraph*G)//对权值进行排序
{
inti,j;
inttemp;
for(i=1;i
{
for(j=i+1;j<=G->arcnum;j++)
{
if(edges[i].weight>edges[j].weight)
{
temp=edges[i].begin;
edges[i].begin=edges[j].begin;
edges[j].begin=temp;
temp=edges[i].end;
edges[i].end=edges[j].end;
edges[j].end=temp;
temp=edges[i].weight;
edges[i].weight=edges[j].weight;
edges[j].weight=temp;
}
}
}
printf("权排序之后的为:
\n");
for(i=1;i<=G->arcnum;i++)
{
printf("<<%s,%s>>%d\n",vex[edges[i].begin].name,vex[edges[i].end].name,edges[i].weig
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基本 操作 kruskal 最小 生成 实验 报告