




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
课程设计题目和内容
一.图的基本操作的实现
1)自选存储结构,输入含n个顶点(用字符表示顶点)和
e条边的图G;
(2)求每个顶点的度,输出结果;
(3)指定任意顶点x为初始顶点,对图G作DFS遍历,输
出DFS顶点序列(提示:使用一个栈实现DFS);
(4)指定任意顶点x为初始顶点,对图G作BFS遍历,输出
BFS顶点序列(提示:使用一个队列实现BFS);
(5)输入顶点x,查找图G:若存在含x的顶点,则删除该结
点及与之相关连的边,并作DFS遍历(执行操作3);否则
输出信息“无X”;
(6)判断图G是否是连通图,输出信息“YES”/“NO”;
(7)如果选用的存储结构是邻接矩阵,则用邻接矩阵的信
息生成图G的邻接表,即复制图G,然再执行操作(2);反
之亦然。
二.程序中所采用的数据结构及存储结构的说明
1邻接矩阵:适用于图中边或弧的
数目比较多的情况,压缩存储方式结构。
邻接矩阵是表示顶点之间相邻关系的矩阵。若图有n个
顶点,则邻接矩阵是一个n*n阶的方阵,结构唯一。邻
接矩阵A的元素规定为:用邻接矩阵存储网时只需要将
矩阵中的1换为相应的权值,将0用一个不可能存在的
权值代替即可。当图用邻接矩阵表示后图的某些操作的
实现是很方便的,如求某一顶点Vi的第一邻接点,只需
在第i行找到第1个非零元即可。若求某一顶点vi的度,
对于无向图来说,只须统计第i行的非零元个数或第i
列的非零元个数(无向图的邻接矩阵是对称的);当图
中顶点数确定,插入一条边(V“Vj)只须将矩阵中第i
行j列和第j行i列的元素分别改为1或相应的权值;
插入一条弧i,V。只须将矩阵中第i行j列的元素改为1
或相应的权值即可。
2邻接表:一种链式存储结构
在邻接表中对图的每个顶点建立一个单链表,第i个单
链表中包含第i个顶点的所有邻接点,每一个单链表包
含两种结点,头结点和表结点。
在图的邻接表中,可以比较方便地查找一个顶点的边(出
边)或邻接点(出边邻接点),这只要首先从表头向量
中取出对应的表头指针,然后从表头指针出发进行查找
即可。
邻接表则是以一数组(结构体数组)的元素作为头指针,
后面链接和它相邻的结点.
3邻接矩阵表示法与邻接表表示法的
比较:
1)邻接矩阵是唯一的,邻接表不唯一;
2)存储稀疏图用邻接表,存储稠密图用邻接矩阵;
3)求无向图顶点的度都容易,求有向图顶点的度邻
接矩阵较方便;
4)判断是否是图中的边,邻接矩阵容易,邻接表最
坏时间为0(n);
5)求边数e,邻接矩阵耗时为0(rT2),与e无关,
邻接表的耗时
三.算法的设计思想
1邻接矩阵存储图的基本思路:
图用邻接矩阵表示后图的某些操作的实现是很方便的,
如求某一顶点V1的第一邻接点,只需在第i行找到第1
个非零元即可。若求某一顶点X的度,对于无向图来说,
只须统计第i行的非零元个数或第i列的非零元个数(无
向图的邻接矩阵是对称的);对于有向图来说,第i行
的非零元个数为该顶点的出度,第i列的非零元个数为
该顶点的入度,两者相加为该顶点的度。当图中顶点数
确定,插入一条边(Vi,Vj)只须将矩阵中第i行j列和
第j行i列的元素分别改为1或相应的权值;插入一条
弧i,V。只须将矩阵中第i行j列的元素改为1或相应的
权值即可。
2邻接表存储图的基本思路:
若无向图中有n个顶点e条边,则邻接表需要n个头结
点和2e个表结点。在边稀疏的情况下,采用邻接表比采
用邻接矩阵节省存储空间。
在无向图的邻接表中,顶点Vi的度恰好为第i个链表中
的表结点数。
若有向图中有n个顶点e条弧,则邻接表需要n个头结
点和e个表结点。在有向图的邻接表中,第i个链表中
的结点数为顶点Vi的出度。为求顶点V1的入度,需要遍
历整个邻接表,在所有链表中其邻接点域的值为i的结
点个数为顶点口的入度。在邻接表中,容易找到任意一
顶点的第一邻接点和下一个邻接点,但要判断任意两个
顶点Vi和Vj之间是否有边相连,则须搜索第i或j个链
表,因此,不及邻接矩阵方便。
3深度优先遍历图的基本思路是:
(1)访问图中的指定起始点Vo;
(2)从Vo出发,访问一个与Vo邻接的顶点叫
后,再从W1出发,访问与W1邻接的且未访问的顶点W2。
然后从W2出发,重复上述过程,直到找不到未被访问的
顶点为止。
(3)回退到尚有未被访问过的邻接点的顶点,
从该顶点出发,重复上面的步骤,直到所有被
访问过的顶点的邻接点都已访问为止。
4广度优先遍历是图的实现思路是:
(1)访问图中的指定起始点Vo;
(2)从Vo出发,依次访问Vo的未被访问的邻
接点W),w2,W3,,,,,Wno然后依次访问Wl,W2,W3,,,,,Wn的未被
访问的邻接点。
(3)重复上面的第二步,直到所有顶点的邻
接点都已访问为止。
四.程序清单
#include<stdio.h>
#include<stdlib.h>
#defineNULL0
#definemaxsize10
typedefstructnode
{
intdata;
structnode*next;
}dnode;
typedefstruct
{intvex;
dnode*first;
}Node;
typedefstruct
{
Nodearry[maxsize];
intnum;
}graph;
intvisit[maxsize];
graphcreat()〃创建邻接表
grapha;
dnode*p;
inti,x,y,e;
printf("输入顶点数和边数(以空格分割):");
scanf("%d%d",&a.num,&e);
for(i=1;i<=a.num;i++)
{
a.arry[i].first=NULL;
a.arry[i].vex=i;
)
for(i=1;i<=e;i++)
{
printf("输入第%d个顶点的边二i);
scanf("%d%d",&x,&y);
p=(dnode*)malloc(sizeof(dnode));
p->data=y;
p->next=a.arry[x].first;
a.arry[x].first=p;
p=(dnode*)malloc(sizeof(dnode));
p->data=x;
p->next=a.arry[y].first;
a.arry[y].first=p;
returna;
voidcopy(graphb,intv[][maxsize])〃令B接矩阵与令B接表
转换
{
inti,j;
dnode*p;
for(i=1;i<=b.num;i++)
for(j=1;j<=b.num;j++)
v[i]U]=O;
for(i=1;i<=b.num;i++)
(
p=(dnode*)malloc(sizeof(dnode));
p=b.arry[i].first;
while(p)
v[i][p->data]=1;
p=p->next;
for(i=1;i<=b.num;i++)
for(j=1;j<=b.num;j++)
printf("%d",v[i][j]);
printf("\n");
)
)
voidvexdu(grapha)//求度数
{
dnode*p;
inti,count;
for(i=1;i<=a.num;i++)
(
p=a.arry[i].first;
count=0;
while(p)
{
count++;
p=p->next;
)
printf("%d的度数:%d\rT,a.arry[i].vex,count);
voidclr()
inti;
for(i=1;i<=maxsize;i++)
visit[i]=0;
)
voiddfs(grapha,intv)
{
dnode*p;
if(a.arry[v].vex!=O)
printf("%d",a.arry[v].vex);
visit[v]=1;
p=a.arry[v].first;
while(p)
if(!visit[p->data])
dfs(a,p->data);
p=p->next;
voidfindl(grapha)
intv;
clr();
printf("输入开始搜索节点:");
scanf("%d",&v);
dfs(a,v);
printf("\n");
)
voidfind2(grapha)
{
intx,i;
dnode*p,*q;
dr();
printf("输入要查找删除的点:");
scanf("%d",&x);
for(i=1;i<=a.num;i++)
if(a.arry[i].vex==x)break;
if(i>a.num)
printf("没找到!\rT);
return;
)
else
{
printf("找至U!\n");
q=p=a.arry[i].first;
a.arry[i].vex=O;
if(p->data==x)p=p->next;
else
while(p)
(
if(p->data==x)
{
q->next=p->next;
break;
)
q=p;
p=p->next;
)
)
dfs(a,x);
printf("\n");
voidfind3(grapha)
inti;
clr();
dfs(a,1);
for(i=1;i<a.num;i++)
if(visit[i]==O)
{
printf("此图不是连通的。\n");
return;
)
printf("此图不是连通的。\n");
return;
)
voidfind4(grapha)
(
intv[maxsize][maxsize];
copy(a,v);
voidmain()
graphh;
h=creat();
vexdu(h);
find1(h);
find2(h);
find3(h);
find4(h);
}
五.运行结果
6*C:\DOCUIEITSAUDSETTIIGSXADIINISTRATOR.IICROSOF-ABlFF7\^ffi\Debug\fe...
以
敢
好
入
顶V
j44
边
□点L
入
T顶12
度
点
边
个
入
顶22
边
点
入
个
顶32
度
点
边
入
顶
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 在全镇第二批保持共产党员先进性教育活动第一阶段转段动员大会上的讲话
- 网络监管平台加强机关效能建设的调查
- 云南省玉溪市2023-2024学年高二下学期期末教学质量检测语文试卷(含答案)
- 2025建筑工程施工合同范本
- 江苏开放大学2025年春财务报表分析第二次模拟练习题
- 河南省项城市2024~2025学年 高三下册第一次考试数学试卷附解析
- 贵州省六校联考2024~2025学年 高三下册3月月考数学试卷附解析
- 福建省龙岩市2024~2025学年 高二下册第一次月考(2月)数学试卷附解析
- 2025年中考语文(长沙用)课件:主题5 最是激荡‘长沙红’演讲比赛
- 石家庄赵县城市管理综合行政执法局招聘笔试真题2024
- 30题投资管理类岗位常见面试问题含HR问题考察点及参考回答
- 15D501 建筑物防雷设施安装
- 世界500强CFO的财务管理笔记2
- 申请提取住房公积金个人授权、承诺书(样表)
- 小动物外科手术学-浙江大学中国大学mooc课后章节答案期末考试题库2023年
- 物流公司运输安全管理制度
- 三个合伙人分配合同范本
- PLC课程设计-四人抢答器
- 化妆品生产工艺及流程图
- 提高住院患者临床路径占比PDCA
- “四电”工程施工工艺标准
评论
0/150
提交评论