`

图的存储结构

阅读更多
图的存储结构也叫图的存储表示和图的表示,主要介绍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):类似于树的按层遍历。
同样对图的广度优先遍历也要两个函数,一是用于外部接口的驱动函数,二是完成访问所有顶点的工作函数;
在工作函数中需要使用一个队列,用来依次记住被访问过的顶点。函数开始时,对初始点访问后插入队列中,以后每从对队列中删除一个元素,就依次访问它的每一个未被访问过的邻接点,并令其进队,这样,当队列为空时,表明所有与初始点有路径相通的顶点都已访问完毕,算法就结束了。
对于非连通图,需要以图中未被访问到的每一个顶点作为起始点,再次调用搜索遍历方法即可;
0
0
分享到:
评论

相关推荐

    关于线性表的顺序存储和链式存储结构的实验报告

    在数据结构实验报告中,线性表的存储结构被分为两大类:顺序存储结构和链式存储结构。 顺序存储结构(Sequential Storage Structure)是将线性表中的元素按顺序存储在一个连续的内存空间中。线性表的顺序存储结构...

    实验报告:图的存储结构和遍历.doc

    图的存储结构和遍历 一、图的存储结构 图的存储结构是指将图结构存储在计算机中的方法。常见的图存储结构有两种:邻接矩阵存储法和邻接表存储法。 1. 邻接矩阵存储法 邻接矩阵存储法是将图的节点之间的关系存储...

    数据结构中常用的逻辑结构和存储结构

    ### 数据结构中常用的逻辑结构和存储结构 #### 一、概念概述 数据结构是指在计算机科学中用于组织和管理数据的方式。它不仅涉及到数据本身的组成,还包括这些数据之间的关系、如何存储这些数据以及如何对数据进行...

    数据结构 存储表示 数据元素

    根据给定文件的信息,我们可以详细地探讨数据结构中的核心概念,包括数据结构的定义、逻辑结构与存储结构的关系,以及算法复杂度分析等关键知识点。 ### 数据结构的基础概念 #### 数据与数据元素 数据(Data)是...

    数据结构课程设计二叉树采用二叉链表作为存储结构

    数据结构课程设计之二叉树采用二叉链表作为存储结构 本课程设计的主要任务是设计并实现一个二叉树的存储结构,使用二叉链表作为存储结构,并实现按层次顺序遍历二叉树的算法。下面是本设计的详细解释和实现过程: ...

    1、使学生熟练掌握二叉树的逻辑结构和存储结构。

    "二叉树的逻辑结构和存储结构" 本节主要讨论二叉树的逻辑结构和存储结构,并对其进行遍历操作。二叉树是一种常见的数据结构,它广泛应用于计算机科学和信息技术领域。 二叉树的逻辑结构 二叉树是指每个结点最多有...

    头歌数据结构图的邻接矩阵存储及遍历操作

    ### 头歌数据结构图的邻接矩阵存储及遍历操作 #### 一、邻接矩阵存储 在数据结构中,图是一种常见的非线性结构,用于表示对象间的关系。根据边是否有方向,图可以分为有向图和无向图。而根据边是否具有权重值,又...

    数据结构--图的存储结构及操作--思维导图.pdf

    数据结构--图的存储结构及操作 图的存储结构是数据结构中非常重要的一部分,它可以是图的邻接矩阵、邻接表、十字链表、邻接多重表等。下面我们将详细介绍每种存储结构的定义、实现、优缺点和应用场景。 1. 邻接...

    数据结构线性表的顺序存储结构

    实验 二 基于链式存储结构 实现线性表的基本的 常见的运算 提示: ⑴ 提供一个实现功能的演示系统 ⑵ 具体物理结构和数据元素类型自行选定 ⑶ 线性表数据可以使用磁盘文件永久保存

    oracle 逻辑存储结构

    oracle 逻辑存储结构

    数据库的存储结构

    本PPT讲解了Oracle数据库的逻辑存储结构、物理存储结构,以及在界面操作下的数据库创建

    线性表的链式存储结构

    线性表的链式存储结构是一种在计算机科学中常见的数据结构实现方式,它与顺序存储结构有所不同。在链式存储结构中,线性表的数据元素并不必须存储在连续的内存位置,而是通过链接指针来建立逻辑上的顺序关系。每个...

    以下说法正确的是()。 A.数据结构的逻辑结构独立于其存储结构 B.数.pdf

    本文将对数据结构的逻辑结构和存储结构进行讨论,并对数学知识点进行总述。 一、数据结构的逻辑结构与存储结构 在计算机科学中,数据结构的逻辑结构和存储结构是两种不同的概念。逻辑结构指的是数据结构的组织方式...

    数据结构实验报告-实现二叉树的基本操作-用顺序存储和链式存储结构

    要求选用顺序存储结构和二叉链表存储结构实现抽象数据类型二叉树的基本操作。有个亮点是利用字符在dos界面显示二叉树的结构形态。 里面包含了完整的源程序和实验报告文档。 实验报告包含了完整的步骤包括: 一.抽象...

    数据结构栈链式存储结构

    栈的链式存储结构与数组存储相比,有其独特的优势。数组存储栈时,空间是连续的,预设大小一旦确定,难以动态扩展;而链式存储则使用节点来存储元素,每个节点包含数据和指向下一个节点的指针,这使得在插入和删除...

    数据结构 链式存储结构基本算法

    链式存储结构是数据结构中的一个重要概念,它与数组存储结构相对,提供了更加灵活的数据存储方式。本篇将深入探讨链式存储结构的基本算法及其在“DATASTRU.H”和“第3章-链式存储结构”中的应用。 链式存储结构的...

    四川大学计算机学院-数据结构与算法分析高分实验报告-引用数使用空间表法广义表存储结构.rar

    本实验报告集中于一个特定的主题——引用数的使用,结合空间表法和广义表的存储结构,这些都是在高级编程和系统设计中至关重要的概念。 首先,让我们详细探讨“引用数”。在计算机科学中,引用数(或称为计数器)...

    《数据结构》5.3树的存储结构

    在本节《数据结构》5.3树的存储结构中,首先介绍了树的数据存储结构的相关概念。树作为一种非线性数据结构,其数据存储方式有别于一般的线性结构,主要通过以下几种方法实现: 1. 顺序存储结构:顺序存储结构通常是...

    数据结构实验报告2线性表的链式存储结构.doc

    在实际应用中,链式存储结构常用于实现各种复杂数据结构,如图和树。在处理不确定数据量或频繁进行插入、删除操作的场景下,链式存储通常比顺序存储更优。实验报告的编写有助于巩固理论知识,提高实践能力,同时培养...

Global site tag (gtag.js) - Google Analytics