数据结构知识点总结-(第六章.图)-图的存储结构及图的遍历

本文主要是介绍数据结构知识点总结-(第六章.图)-图的存储结构及图的遍历,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

上一篇见:数据结构知识点总结-(第六章.图)-图的基本概念

第六章.图

6.4 图的存储结构

图的存储必须要完整准确的反应顶点集和边集的信息。

根据不同图的结构和算法,可以采用不同的存储方式,但不同的存储方式对程序的效率影响相当的大。因此所选的数据结构应该适合于待求解的问题。

不论是有向图还是无向图,主要的存储方式都有两种:邻接矩阵和邻接表。前者属于图的顺序存储结构,后者属于图的链式存储结构。对于十字链表了解即可。

(1)邻接矩阵存储

        所谓邻接矩阵存储,就是用一个一维数组存储图中顶点的信息,用一个二维数组存储图中边的信息(即各顶点之间的邻接关系),存储顶点之间的邻接关系的二维数组称为邻接矩阵。 有时候结点按照序号编号,则可以省略存储图顶点信息一维数组。

对于带权图而言,若顶点vi和vj之间有边连接,则邻接矩阵中对应项存放该边对应的权值,若顶点vi和vj不相连,则用∞来表示这两个顶点之间不存在边。

邻接矩阵存储有以下特点:

(1)无向图的邻接矩阵是对称矩阵,并且唯一。

(2)对于无向图,邻接矩阵的第i行(或第i列)非零元素的个数正好是第i个顶点的度。

(3)对于有向图,邻接矩阵的第i行(或第i列)非零元素的个数正好是第i个顶点的出度(出度)。

(4)用邻接矩阵法存储图,很容易确定图中任意两个顶点之间是否有边相连。但是,要确定图中有多少条边,则必须按行、按列对每个元素进行遍历,所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

(5)稠密图适合用邻接矩阵存储表示。

(2)邻接表存储

        当一个图为稀疏图时,是用邻接矩阵表示法显然浪费了大量的存储空间。而图的邻接表存储结合了顺序存储和链式存储的方法,大大的减少了这种不必要的浪费。

        所谓邻接表就是对图G中的每个顶点Vi建立一个单链表,第i个单链表中的结点表示与顶点Vi相连的边(对于有向图则表示以顶点Vi射出的边),这个单链表就成为顶点Vi的边表(对有向图来说是出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表),所以在邻接表中存在两种结点:顶点表结点和边表结点。

        顶点表结点由顶点域(data)和指向第一条邻接边的指针构成,边表结点由邻接点域和指向下一条邻接边的指针域构成。

图的邻接表存储有以下特点:

(1)如果G为无向图,则所需的存储空间为O(|V| + 2|E|);如果G为有向图,则所需的存储空间为O(|V| + |E|)。前者的倍数2是由于无向图中,每条边在邻接表中出现了两次。

(2)对于稀疏图,采用邻接表存储将节省存储空间。

(3)在邻接表中,给定一顶点,能很容易的找到它的所有邻边,因为只需要读取它的邻接表就可以了。在邻接矩阵中,则需要扫描一行,花费的时间是O(n)。但是如果要确定给定的两个顶点间是否存在边,则在邻接矩阵里可以立即查到,在邻接表中则需要在相应结点对应的边表中查找另一节点,效率较低。

(4)在有向图的邻接表表示中,求一个给定顶点的出度只需计算其邻接表中结点个数即可;但求其顶点的入度,则需要遍历全部的邻接表。因此也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然这实际上与邻接表的存储方式是类似的。

(5)图邻接表表示并不唯一,这是因为在每个顶点对应的单链表中,各边结点的链接次序可以任意,取决于建立邻接表的算法以及边的输入次序。

(3)十字链表存储

邻接表和逆邻接表的整合。见图:

        弧结点中有5个域:其中尾域(tailvex)和头域(headvex)分别指示弧尾和弧头这两个顶点,链域headlink指向弧头相同的下一条弧,链域taillink指向弧尾相同的下一条弧,info域存储该弧的相关信息。这样弧头相同的弧在同一个链表上,弧尾相同的弧也在同一个链表上。

        顶点域中有三个域:data域存放顶点相关的数据信息,如顶点名称,firstin和firstout两个域分别指向以该顶点为弧头和弧尾的第一个弧结点。

6.5 图的遍历

        图的遍历是指从图中的某一顶点出发,按照某种搜索方式沿着途中的边对图中所有顶点访问一次且仅访问一次。注意到树是一种特殊的图,所以树的遍历实际上也可以看做是一种特殊的图的遍历。图的遍历是图的一种基本的操作,其他许多操作都建立在图的遍历操作基础之上。

        图的遍历主要有两种算法:广度优先搜索和深度优先搜索。

(1)BFS

        广度优先搜索(BFS)类似于二叉树的层次遍历算法,它的基本思想是:首先访问起始顶点v0,接着由v0出发,依次访问v0各个未访问过的邻接顶点,然后再依次访问它们所有未被访问过的邻接顶点,以此类推,直到所有顶点都被访问过。类似的思想将应用于Dijkstra单源最短路径算法和prime最小生成树算法。

        广度优先搜索是一种分层的查找过程,每向前走一步可能访问一批结点,不像深度优先搜索那样有回退的情况。因此他不是一个递归的算法,为了实现逐层的访问,算法必须借助一个辅助队列,以记忆正在访问的顶点的下一层顶点。

下面以求解非带权图的单源最短路径问题为例介绍BFS的算法模板。

   如果图G=(V,E)为非带权图,定义从顶点u到顶点v的最短路径d(u,v)为从u到v的任何路径中最少的边数;如果没有通路,则为d(u,v)=∞。

    使用BFS,我们可以求解一个满足上述定义的非带权路径的单源最短路径问题,这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。

//以此模板来熟悉BFS 要背下来
void BFS_MIN_Distance(Graph G, int u){for(int i = 0; i < G.vexnum; i++)d[i] = INT_MAX;visited[u] = true; //标记当前顶点被访问过d[u] = 0; //当前节点的最短路径为0,求u到k的最短路,则输出d[k]即可。EnQueue(Q, u);while( !IsEmpty(Q) ) {DeQueue(Q,u);for(w = FirstNeighbor(G,u); w >= 0; w = NextNeighbor(G,u,w)) {if(!visited[w]) {visited[w] = true;d[w] = d[u]+1;EnQueue(Q,w);}}}
}

(2)DFS

        深度优先搜索(DFS)类似于树的先序遍历。正如其名称中所表达的意思一样,这种搜索算法所遵循的策略是尽可能“深”的搜索一个图。

        它的基本思想如下:首先访问图中某一起始顶点v0,然后从v0出发,访问与v0邻接且未被访问的任一定点w1,再访问与w1邻接且未被访问的任意顶点w2,……重复上述过程。当不能再继续向下访问时,一次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,若它的邻接点均被访问完毕,则继续回退执行相同的操作,直到搜索顶点均被访问过为止。

        深度优先的算法过程时递归定义的,其代码过程如下:

#define MAX_VERTEX_NUM 100
bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G)
{for(v=0;v<G.vexnum;i++)visited[v]=false;for(v=0;v<G.vexnum;i++)if(!visited[v])DFS(G,v);
}
void DFS(Graph G,int v)
{visit(v);visited[v]=true;for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w))if(!visited[w])DFS(G,w);
}

        DFS算法是一个递归算法,需要借助一个递归工作栈,故她的空间复杂度为O(|V|)。

        遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所采用的存储结构。当以邻接矩阵进行表示时,查找每个顶点的邻接点所需时间为O(|V|),故总的时间复杂度为O(|V|2)。当以邻接表表示时,查找所有顶点的临接点所需时间为O(|E|),访问顶点所需时间为O(V),此时,总的时间复杂度为O(|V|+|E|)。

下一篇介绍图的应用:最小生成树、最短路径、拓扑排序、关键路径

这篇关于数据结构知识点总结-(第六章.图)-图的存储结构及图的遍历的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/762296

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

使用Java实现通用树形结构构建工具类

《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录完整代码一、设计思想与核心功能二、核心实现原理1. 数据结构准备阶段2. 循环依赖检测算法3. 树形结构构建4. 搜索子

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

java常见报错及解决方案总结

《java常见报错及解决方案总结》:本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案:2. 空指针异常 (NullPoi

Oracle存储过程里操作BLOB的字节数据的办法

《Oracle存储过程里操作BLOB的字节数据的办法》该篇文章介绍了如何在Oracle存储过程中操作BLOB的字节数据,作者研究了如何获取BLOB的字节长度、如何使用DBMS_LOB包进行BLOB操作... 目录一、缘由二、办法2.1 基本操作2.2 DBMS_LOB包2.3 字节级操作与RAW数据类型2.

Java实现数据库图片上传与存储功能

《Java实现数据库图片上传与存储功能》在现代的Web开发中,上传图片并将其存储在数据库中是常见的需求之一,本文将介绍如何通过Java实现图片上传,存储到数据库的完整过程,希望对大家有所帮助... 目录1. 项目结构2. 数据库表设计3. 实现图片上传功能3.1 文件上传控制器3.2 图片上传服务4. 实现

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

MySQL常见的存储引擎和区别说明

《MySQL常见的存储引擎和区别说明》MySQL支持多种存储引擎,如InnoDB、MyISAM、MEMORY、Archive、CSV和Blackhole,每种引擎有其特点和适用场景,选择存储引擎时需根... 目录mysql常见的存储引擎和区别说明1. InnoDB2. MyISAM3. MEMORY4. A