`
- 浏览:
81307 次
- 性别:
- 来自:
西安
-
图的存储结构也叫图的存储表示和图的表示,主要介绍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
相关推荐
数据结构串的存储结构程序 数据结构是计算机科学中的一门重要课程,本程序是数据结构中串的存储结构的一个实现。串是由零个或多个字符组成的有限序列,串的存储结构是指如何将串存储在计算机中,以便于后续的操作。...
在数据结构实验报告中,线性表的存储结构被分为两大类:顺序存储结构和链式存储结构。 顺序存储结构(Sequential Storage Structure)是将线性表中的元素按顺序存储在一个连续的内存空间中。线性表的顺序存储结构...
图的存储结构和遍历 一、图的存储结构 图的存储结构是指将图结构存储在计算机中的方法。常见的图存储结构有两种:邻接矩阵存储法和邻接表存储法。 1. 邻接矩阵存储法 邻接矩阵存储法是将图的节点之间的关系存储...
在本主题中,我们将深入探讨线性表的两种主要存储结构:顺序存储结构和链式存储结构,以及在这两种结构上实现的基本操作。同时,我们还会涉及栈这种特殊类型的线性表及其顺序和链式存储结构。 一、线性表的顺序存储...
数据结构实验报告2线性表的链式存储结构 本实验报告的主要内容是介绍线性表的链式存储结构,并通过编程实验来掌握线性表的逻辑结构和链式存储结构,以及单链表的基本算法。 一、线性表的概念 线性表是最基本的...
1.基于顺序存储结构的图书信息表的创建和输出 问题描述定义一个包含图书信息 (书号、书名、价格)的顺序表,读入相应的图书数据来完成图书信息表的创建。然后,统计图书表中的图书个数,同时逐行输出每本图书的信息。...
### 数据结构中常用的逻辑结构和存储结构 #### 一、概念概述 数据结构是指在计算机科学中用于组织和管理数据的方式。它不仅涉及到数据本身的组成,还包括这些数据之间的关系、如何存储这些数据以及如何对数据进行...
数据结构课程设计之二叉树采用二叉链表作为存储结构 本课程设计的主要任务是设计并实现一个二叉树的存储结构,使用二叉链表作为存储结构,并实现按层次顺序遍历二叉树的算法。下面是本设计的详细解释和实现过程: ...
比较顺序存储和链接存储两种存储结构的有缺点 顺序存储和链接存储是两种常见的存储结构,在实现线性表时都有其优缺点。下面我们将详细比较这两种存储结构的优缺点,并说明其适用场合。 顺序存储 顺序存储是一种...
### 头歌数据结构图的邻接矩阵存储及遍历操作 #### 一、邻接矩阵存储 在数据结构中,图是一种常见的非线性结构,用于表示对象间的关系。根据边是否有方向,图可以分为有向图和无向图。而根据边是否具有权重值,又...
"二叉树的逻辑结构和存储结构" 本节主要讨论二叉树的逻辑结构和存储结构,并对其进行遍历操作。二叉树是一种常见的数据结构,它广泛应用于计算机科学和信息技术领域。 二叉树的逻辑结构 二叉树是指每个结点最多有...
### 二、头歌数据结构图的邻接表存储 #### 1. 数据类型定义 - **顶点类型**:`VertexType` 定义为一个字符数组,用于存储顶点的名称。 - **图的种类**:`GraphKind` 定义了四种类型的图:有向图 (DG)、有向网 (DN)...
数据结构 - 图的存储结构 - 邻接表的创建 - 无向图。 在数据结构中,图是一种非常重要的数据结构,它广泛应用于计算机科学和信息技术领域中。在本节中,我们将讨论图的存储结构,并使用 C 语言实现图的邻接表的创建...
要求选用顺序存储结构和二叉链表存储结构实现抽象数据类型二叉树的基本操作。有个亮点是利用字符在dos界面显示二叉树的结构形态。 里面包含了完整的源程序和实验报告文档。 实验报告包含了完整的步骤包括: 一.抽象...
在本节《数据结构》5.3树的存储结构中,首先介绍了树的数据存储结构的相关概念。树作为一种非线性数据结构,其数据存储方式有别于一般的线性结构,主要通过以下几种方法实现: 1. 顺序存储结构:顺序存储结构通常是...
本PPT讲解了Oracle数据库的逻辑存储结构、物理存储结构,以及在界面操作下的数据库创建
线性表的链式存储结构是一种在计算机科学中常见的数据结构实现方式,它与顺序存储结构有所不同。在链式存储结构中,线性表的数据元素并不必须存储在连续的内存位置,而是通过链接指针来建立逻辑上的顺序关系。每个...
本文将对数据结构的逻辑结构和存储结构进行讨论,并对数学知识点进行总述。 一、数据结构的逻辑结构与存储结构 在计算机科学中,数据结构的逻辑结构和存储结构是两种不同的概念。逻辑结构指的是数据结构的组织方式...
链式存储结构是数据结构中的一个重要概念,它与数组存储结构相对,提供了更加灵活的数据存储方式。本篇将深入探讨链式存储结构的基本算法及其在“DATASTRU.H”和“第3章-链式存储结构”中的应用。 链式存储结构的...