




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第七章图图的基本概念及术语图的表示法图的遍历图的应用本章目标7.2图的存储结构邻接矩阵表示法邻接表表示法邻接多重表十字链表设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A
[n][n],定义:故,图的邻接矩阵表示法也称为:数组表示法7.2.1邻接矩阵(AdjacencyMatrix)无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。0123012863129542031网的邻接矩阵1.无向图的邻接矩阵是对称矩阵,所以可采用压缩存储法(下三角),其存储空间只需_____。2.有向图的邻接矩阵一定不是对称矩阵,对吗?3.有向图的邻接矩阵需要______个存储空间。练习n(n-1)/2n2不对!有可能是对称矩阵在有向图中,统计第i
行
1的个数可得顶点
i
的出度,统计第j列
1的个数可得顶点j
的入度。在无向图中,统计第i
行(列)1的个数可得顶点i
的度。邻接矩阵的C语言描述采用邻接矩阵表示法创建有向网-P205见算法7.1思考:如何采用邻接矩阵表示法创建有向网的其它操作???只须将实现有向网中边的权值表示方式按如下修改即可
每条边的边权规定为1,边权为0时表示无边用邻接矩阵实现有向图边权规定为1,边权为0时表示无边一条边可看作两条相反方向的弧,如:-----插入一条边(i,j)的操作:用邻接矩阵实现无向图G->arcs[i][j].adj=1;G->arcs[j][i].adj=1;优点:易于操作缺点:对于稀疏图来讲,该方法极浪费邻接矩阵表示法解决方法:邻接表表示法邻接矩阵表示法内容结束之后回邻接表(AdjacencyList)表示法ABCDvexdata
firstarcABCD0123adjvex
nextarc
130210无向图的邻接表表头结点表边表表头结点表下标可从1开始也可从0开始ABCABC012
ABC012102
011有向图的邻接表邻接表(出边表)逆邻接表(入边表)vexdata
firstarcadjvex
nextarcvexdata
firstarcadjvex
nextarcBACD69528ABCD0123
1
53
62
83
2(出边表)(顶点表)有向网(带权图)的邻接表1
9vexdata
firstarcadjvexinfonextarc优点:不必存储不存在的边(弧)缺点:结构较复杂如建立逆邻接表,方便计算入度,但实际上,一条边需分别在邻接表与逆邻接表中存储邻接表表示法解决方法:十字链表(优点一条弧只被存放一次)
十字链表“结点结构”之后回弧结点:0312info35189013tailvex=0headvex=1hlink=弧<1,3>地址31tlink=弧<0,2>地址02info存储弧的相关信息:如权值3顶点结点:031B35189A1DDA0231B123D1firstin=弧<1,0>地址firstout=弧<0,2>地址data存储与顶点有关的信息,如:名字A
十字链表1.“图例”后回并练习2.形式化定义与算法作图方法:1.先画出顶点结点(数组形式)2.画出所有弧结点(刚弧尾将各弧结点放置在对应的顶点结点后面)3.连线是有向图的一种链式存储结点结构优点:计算出度、入度十分方便缺点:结构较复杂十字链表表示法
邻接多重表内容结束后回是无向图的一种存储结构优点:提供更为方便的边处理信息,如:
比较无向图的邻接表表示法中,每一条边在邻
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025版临时工聘用协议书(含薪酬福利待遇与绩效考核)
- 2025版波形护栏安装与道路绿化工程合同
- 二零二五版搬家服务与设备安装合同规范
- 2025年汽车报废回收与环保处理合同范本
- 二零二五版现代农业设施设备采购与安装合同
- 二零二五年度彩钢瓦施工安全监督及应急预案合同
- 二零二五年高端游戏电视购买协议
- 二零二五年度实习生劳动合同样本及实习管理制度
- 二零二五年新型仓储设备租赁与维护协议
- 河南省安阳市内黄县市级名校2026届中考英语仿真试卷含答案
- 2025年版义务教育道德与法治课程标准题库(教师培训考试专用)
- 施工图识读基础知识课件
- 金属热处理工技能测试题库及答案
- 小学足球校队管理办法
- 血透室病区环境管理
- 企业建设工程管理办法
- 甘肃低空经济政策
- 2025公需课《人工智能赋能制造业高质量发展》试题及答案
- 关于加强医药卫生领域廉政建设的意见(2025年版)解读
- 某港池航道疏浚和吹填造陆工程施工组织设计
- 《工程建设标准强制性条文电力工程部分2023年版》
评论
0/150
提交评论