原文链接:http://andy100861.blog.163.com/blog/static/98551191200992202558438/
图的存储结构
图的存储结构除了要存储图中各个顶点的本身的信息外,同时还要存储顶点与顶点之间的所有关系(边的信息),因此,图的结构比较复杂,很难以数据元素在存储区中的物理位置来表示元素之间的关系,但也正是由于其任意的特性,故物理表示方法很多。常用的图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。
8.2.1邻接矩阵表示法
对于一个具有n个顶点的图,可以使用n*n的矩阵(二维数组)来表示它们间的邻接关系。图8.10和图8.11中,矩阵A(i,j)=1表示图中存在一条边(Vi,Vj),而A(i,j)=0表示图中不存在边(Vi,Vj)。实际编程时,当图为不带权图时,可以在二维数组中存放bool值,A(i,j)=true表示存在边(Vi,Vj),A(i,j)=false表示不存在边(Vi,Vj);当图带权值时,则可以直接在二维数组中存放权值,A(i,j)=null表示不存在边(Vi,Vj)。
图8.10所示的是无向图的邻接矩阵表示法,可以观察到,矩阵延对角线对称,即A(i,j)= A(j,i)。无向图邻接矩阵的第i行或第i列非零元素的个数其实就是第i个顶点的度。这表示无向图邻接矩阵存在一定的数据冗余。
图8.11所示的是有向图邻接矩阵表示法,矩阵并不延对角线对称,A(i,j)=1表示顶点Vi邻接到顶点Vj;A(j,i)=1则表示顶点Vi邻接自顶点Vj。两者并不象无向图邻接矩阵那样表示相同的意思。有向图邻接矩阵的第i行非零元素的个数其实就是第i个顶点的出度,而第i列非零元素的个数是第i个顶点的入度,即第i个顶点的度是第i行和第i列非零元素个数之和。
由于存在n个顶点的图需要n2个数组元素进行存储,当图为稀疏图时,使用邻接矩阵存储方法将出现大量零元素,照成极大地空间浪费,这时应该使用邻接表表示法存储图中的数据。
8.2.2 邻接表表示法
图的邻接矩阵存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。邻接表由表头结点和表结点两部分组成,其中图中每个顶点均对应一个存储在数组中的表头结点。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。如图8.12所示,表结点存放的是邻接顶点在数组中的索引。对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A所指链表中存在一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点。
有向图的邻接表有出边表和入边表(又称逆邻接表)之分。出边表的表结点存放的是从表头结点出发的有向边所指的尾顶点;入边表的表结点存放的则是指向表头结点的某个头顶点。如图8.13所示,图(b)和(c)分别为有向图(a)的出边表和入边表。
以上所讨论的邻接表所表示的都是不带权的图,如果要表示带权图,可以在表结点中增加一个存放权的字段,其效果如图8.14所示。
【注意】:观察图8.14可以发现,当删除存储表头结点的数组中的某一元素,有可能使部分表头结点索引号的改变,从而导致大面积修改表结点的情况发生。可以在表结点中直接存放指向表头结点的指针以解决这个问题(在链表中存放类实例即是存放指针,但必须要保证表头结点是类而不是结构体)。在实际创建邻接表时,甚至可以使用链表代替数组存放表头结点或使用顺序表存代替链表存放表结点。对所学的数据结构知识应当根据实际情况及所使用语言的特点灵活应用,切不可生搬硬套。
相关推荐
/* 1、实现图的邻接矩阵和邻接表存储结构; 2、完成基于邻接矩阵或邻接表的深度优先搜索遍历及广度优先搜索遍历; 3、实现从键盘输入任意一对顶点,求出顶点间的最短路径。*/
数据结构--图的存储结构及操作--思维导图.pdf
结构化存储结构化存储结构化存储结构化存储
本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系,难点是算法复杂度的分析方法。 需要达到<识记>层次的基本概念和术语有:数据、数据元素、数据项、数据结构。特别是数据结构的...
实现线性表的顺序存储结构、链式存储结构,以及定义在上述结构的基本操作,栈的顺序存储结构、链式存储结构,以及定义在上述结构的基本操作
1.基于顺序存储结构的图书信息表的创建和输出 问题描述定义一个包含图书信息 (书号、书名、价格)的顺序表,读入相应的图书数据来完成图书信息表的创建。然后,统计图书表中的图书个数,同时逐行输出每本图书的信息。...
实验 二 基于链式存储结构 实现线性表的基本的 常见的运算 提示: ⑴ 提供一个实现功能的演示系统 ⑵ 具体物理结构和数据元素类型自行选定 ⑶ 线性表数据可以使用磁盘文件永久保存
数据结构实验报告(1) 学院: 专业: 班级: "姓名 " "学号 " "实验组" " "实验时间 "2011-10-28 "指导教师" "成绩 " " "实验项目名称 "线性表的顺序存储结构 " "实 "1. 熟练掌握线性表的基本操作在顺序存储和链式...
头歌数据结构图的邻接矩阵存储及遍历操作 第1关图的邻接矩阵存储及求邻接点操作 第2关图的深度优先遍历 第3关图的广度优先遍历 稳过
非常珍贵的Netfilter存储结构图,对理解netfilter架构很有帮助,看懂这个图,也就理解了netfilter架构。
数据结构实验报告2线性表的链式存储结构.pdf
oracle 逻辑存储结构
Input 第一行:输入图的顶点个数n(各个顶点的默认编号为1~n), 边的条数m。 第二 ~ m+1行:每行输入两个...分n行输出n*n的邻接矩阵,表示所输入的图存储,顶点i和顶点j之间如果有边相连,则输出1,没边相连则输出0。
线性表的链式存储结构.doc 线性表的链式存储结构.doc 线性表的链式存储结构.doc
该文档饱含了数据结构课程中关于线性表的十二个基本操作的实现。对于不同的线性表的存储结构,利用C语言分别实现相应的算法
要求选用顺序存储结构和二叉链表存储结构实现抽象数据类型二叉树的基本操作。有个亮点是利用字符在dos界面显示二叉树的结构形态。 里面包含了完整的源程序和实验报告文档。 实验报告包含了完整的步骤包括: 一.抽象...
本PPT讲解了Oracle数据库的逻辑存储结构、物理存储结构,以及在界面操作下的数据库创建
本节主要讲述二叉树的线索链表存储结构和相关操作
熟悉串的七种基本操作的定义,并能利用这些基本操作实现串的其他各种操作的方法;熟悉掌握在串的定长顺序存储结构上实现串操作的方法 本程序可以在98/2000/XP下运行,可以用VC++6.0执行
数据结构栈链式存储结构