采用邻接表格模板存储结构编写一个求无向图的连通分量个数的算法.docx
- 文档编号:8828624
- 上传时间:2023-05-15
- 格式:DOCX
- 页数:5
- 大小:26.19KB
采用邻接表格模板存储结构编写一个求无向图的连通分量个数的算法.docx
《采用邻接表格模板存储结构编写一个求无向图的连通分量个数的算法.docx》由会员分享,可在线阅读,更多相关《采用邻接表格模板存储结构编写一个求无向图的连通分量个数的算法.docx(5页珍藏版)》请在冰点文库上搜索。
采用邻接表格模板存储结构编写一个求无向图的连通分量个数的算法
学院名称
专业班级
实验成绩
学生姓名
学号
实验日期
课程名称
数据结构
实验题目
3图
一、实验目的与要求
熟悉图的存储结构,掌握有关算法的实现,了解图在计算机科学及其他工程技术中的应用。
二、主要仪器设备
Cfree
三、实验内容和原理
[问题描述]
采用邻接表存储结构,编写一个求无向图的连通分量个数的算法。
[输入]
图顶点的个数,和以各个顶点为弧尾的所有弧,并以-1结束输入。
[输出]
连通分量的个数。
[存储结构]
图采用邻接矩阵的方式存储。
[算法的基本思想]
用到深度优先搜索,先从任意一个顶点开始进行深度优先搜索,搜索完后,连通分量个数增1。
然后再从没有遍历过的顶点找一个出来进行深度优先搜索,搜索完后,连通分量个数增1。
一直到所有的顶点都被遍历过。
[参考源程序]
#include
#include
intn;
structVNode{//顶点
intposition;
structVNode*next;
};
structArcNode{//弧
intmark;
structVNode*first;
};
voidDFS(structArcNode*v,structArcNode*w){//深度优先搜索
structVNode*L;
w->mark=1;
L=w->first;
while(L!
=NULL){
if((v+(L->position))->mark==0){
DFS(v,(v+L->position));//递归调用
}
L=L->next;
}
}
intmain(){
inti,j,k;
intnum=0;
structArcNode*p;
structVNode*temp;
structVNode*flag;
printf("\n请输入顶点个数n:
");
scanf("%d",&n);
while(n<1){
printf("你输入的值不合理,请重新输入:
\n");
scanf("%d",&n);
}
p=(structArcNode*)malloc(n*sizeof(structArcNode));
/*说明:
1.Vi表示第i个顶点,它在表中的位置为i-1,如V3在表中的位置为2;
2.如果输入以V1为弧尾的所有弧(假设存在弧
则输入:
21-1(只需输入弧头的位置,并用-1表示结束)*/
for(i=0;i printf("\n请输入以V%d为弧尾的所有弧,并以-1结束输入\n",i+1); scanf("%d",&k); if(k==-1){ p[i].mark=0; p[i].first=NULL; } else{ temp=(structVNode*)malloc(sizeof(structVNode)); temp->position=k; temp->next=NULL; p[i].first=temp; p[i].mark=0; flag=temp; scanf("%d",&k); while(k! =-1){ temp=(structVNode*)malloc(sizeof(structVNode)); temp->position=k; temp->next=NULL; flag->next=temp; flag=temp; scanf("%d",&k); } } } i=0; while(p[i].mark==0){//计算连通分量的个数 DFS(p,(p+i)); num++; i=0; while(p[i].mark! =0&&i i++; } } printf("此图的连通分量个数为: %d\n",num); system("pause"); return0; } 五、实验结果与分析 习题1: 这题主要还是用到深度优先搜索,先从任意一个顶点开始进行深度优先搜索,搜索完后,连通分量个数增1。 然后再从没有遍历过的顶点找一个出来进行深度优先搜索,搜索完后,连通分量个数增1。 一直到所有的顶点都被遍历过。 实验结果如图: 六、实验心得及体会 通过本次实验,我更好的掌握了图的相关操作,能够熟练的进行图的建立、遍历。 在编写程序时,有很多不明白的地方,在得到同学的鼎立相助后,基本解决了这些问题。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 采用 邻接 表格 模板 存储 结构 编写 一个 连通 分量 个数 算法