`
- 浏览:
79106 次
- 性别:
- 来自:
西安
-
图的存储结构也叫图的存储表示和图的表示,主要介绍3种:邻接矩阵、邻接表、边集数组
1、邻接矩阵(adjacency matrix)表示图形中顶点之间相邻关系的矩阵。amx[i,j]=1,表示i,j之间存在边的关系,若为0则表示二者之间无边的关系。无向图的邻接矩阵是按照主对角线对称的,
有向图则不是。若是带权图,则把1换成相应的权值即可。
因邻接矩阵中的元素可以随机存取,所以查找一条边的时间复杂度为O(1)。
由于求任一顶点的度需要访问对应一行或者一列中的所有元素,所以其时间复杂度为O(n);
图的邻接矩阵的存储需要暂用n*n个实数存储空间,所以其空间复杂度为O(n^2)。若用于存储稠密图能够充分利用存储空间,但若是用于表示稀疏图,则使邻接矩阵变为稀疏矩阵,从而造成存储空间的很大浪费。
2、邻接表(adjacency matrix)是对图中的每个顶点建立一个邻接关系的单链表,并把它们的表头指针用一维数组(向量)存储的一种图的表示方法。邻接表中每个结点用来存储一条边的信息,因而称之为边结点。边结点通常包含3个域:邻接点域,用来存储顶点的一个邻接顶点的序号;权值域,用来存储边上的权;邻接域,用来存储邻接表中的下一个边结点。
每个顶点单链表的平均长度为e/n(对于有向图)或2e/n(对于无向图),其中e是边数,n是点数。所以查找运算的时间复杂度为O(e/n)。对于需要经常查找顶点入边或入边邻接点的运算,可以专门建立一个逆邻接表,该表中每个顶点的单链表不是存储该顶点的所有出边的信息,而是存储所有边的入边信息,邻接点域存储的是入边邻接点的序号。
3、边集数组(edgeset array)是利用一维数组存储图中所有边的一种图的表示方法。数组中的每个元素存储一条边的起点、终点(对于无向图,可选定边的任一端点为起点或终点)、和权值,边的的信息在数组中可以任意安排。边集数组中只存储图中所有边的信息,若需要存储顶点的信息,同样需要一个具有n个元素的一维数组。在边集数组中查找一条边或一个顶点的度都需要扫描整个数组,所以时间复杂度是O(e),空间复杂度为O(e)。从空间复杂度上讲,边集数组也适合表示稀疏图。
图的遍历:深度优先+广度优先
深度优先搜索遍历(depth-first search):类似于树的先序遍历,是一个递归的过程。对图进行深度优先搜索遍历时得到的顶点序列不是唯一的。图的深度优先搜索遍历的过程分为两个函数定义来实现,一个驱动函数,另一个工作函数。驱动函数为一个非递归函数,它起到与外界接口和调用内部递归函数的作用;工作函数是只允许在图类内部调用的私有递归函数,该函数具体完成对图中每个顶点的访问任务。
对邻接矩阵表示的图进行深度优先搜索遍历时,可能需要扫描邻接矩阵中的每一个元素,其时间复杂度为O(n^2);对邻接表表示的图进行深度优先遍历时,可能需要扫描邻接表中的表头数组的每个元素和所有边结点,其时间复杂度为O(n+e);二者的空间复杂度均为O(n)
广度优先搜索遍历(breadth-first search):类似于树的按层遍历。
同样对图的广度优先遍历也要两个函数,一是用于外部接口的驱动函数,二是完成访问所有顶点的工作函数;
在工作函数中需要使用一个队列,用来依次记住被访问过的顶点。函数开始时,对初始点访问后插入队列中,以后每从对队列中删除一个元素,就依次访问它的每一个未被访问过的邻接点,并令其进队,这样,当队列为空时,表明所有与初始点有路径相通的顶点都已访问完毕,算法就结束了。
对于非连通图,需要以图中未被访问到的每一个顶点作为起始点,再次调用搜索遍历方法即可;
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
/* 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执行
数据结构栈链式存储结构