1万+  考点词条:  标题检索     全文检索
图的存储结构
图主要有以下4种存储结构:邻接矩阵、邻接表、邻接多重表及十字链表。其中最常用的存储结构为邻接矩阵和邻接表,尤其是邻接表。
邻接矩阵是表示顶点之间相邻关系的矩阵。有n个顶点的图G=(V,E)的邻接矩阵为n阶方阵,其定义为:
将邻接矩阵中的0、1换成权值,就是图的邻接矩阵。无向图的邻接矩阵是对称矩阵;顶点vi的度是邻接矩阵中第i行(或第i列)的元素1之和。有向图的邻接矩阵不一定是对称矩阵;顶点vi的出度是邻接矩阵中第i行元素之和,入度是邻接矩阵中第i列的元素之和。
可见,通过邻接矩阵可以很容易地判定顶点间有无边(弧),容易计算顶点的度(出度、入度);缺点是所占空间只和顶点个数有关,和边数无关,在边数较少时,空间浪费较大。一般在顶点数较少且边数稠密时应用邻接矩阵。
邻接表是为克服邻接矩阵在图为稀疏图时的空间浪费大这个缺点而提出的。
邻接表是顶点的向量结构和边(弧)的单链表结构的集合,每个顶点节点包括两个域,将n个顶点放在一个向量中(称为顺序存储的节点表);一个顶点的所有邻接点链接成单链表,该顶点在向量中有一个指针域指向其第一个邻接点。邻接表的结构如下:
顶点节点
边(弧)节点
其中,vexdata是顶点数据,firstarc是指向该顶点第一个邻接点的指针,adjvex是邻接点在向量中的下标,info是邻接点的信息,next是指向下一邻接点的指针。
对无向图,容易求各顶点的度;边表中节点个数是边数的两倍。对有向图,容易求顶点的出度;若求顶点的入度则不容易,要遍历整个表。为了求顶点的入度,有时可设逆邻接表(指向某顶点的邻接点链接成单链表)。所谓逆邻接表就是对图中的每个顶点i建立一个单链表,把被i邻接的顶点放在一个链表中,即边表中存放的是入度边而不是出度边。一般在处理以顶点为主且为边稀疏时用邻接表。
未完............


 相关词条:
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。


工作时间:9:00-20:00

客服

点击这里给我发消息 点击这里给我发消息 点击这里给我发消息

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


京ICP证140039号 | 京ICP备13027030号-1 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2019 All Rights Reserved 软考在线版权所有