对有n个结点、e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历，时..

免费智能真题库 > 历年试卷 > 数据库系统工程师 > 2018年上半年数据库系统工程师上午试卷综合知识

第10题

知识点：矩阵邻接矩阵表示法数组深度优先遍历

关键词：遍历邻接矩阵深度优先时间复杂度数组章/节：计算机软件基础知识

对有n个结点、e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历，时间复杂度为（）。

A. O(n²)

B. O(e²)

C. O(n+e)

D. O(n*e)


知识点讲解
· 矩阵 · 邻接矩阵表示法 · 数组 · 深度优先遍历

矩阵

矩阵是很多科学与工程计算问题中研究的数学对象。在数据结构中主要讨论如何在尽可能节省存储空间的情况下，使矩阵的各种运算能高效地进行。

在一些矩阵中，存在很多值相同的元素或者是零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。压缩存储的含义是为多个值相同的元素只分配一个存储单元，对零元不分配存储单元。

特殊矩阵

常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。对于特殊矩阵，由于其非零元的分布都有一定的规律，所以可将其压缩存储在一维数组中，并建立起每个非零元在矩阵中的位置与其在一维数组中的位置之间的对应关系。

若矩阵A_n_×_n中的元素有a_ij=a_ji（1≤i，j≤n）的特点，则称之为对称矩阵。

若为对称矩阵中的每一对元素分配一个存储单元，那么就可将n²个元素压缩存储到能存放n（n+1）/2个元素的存储空间中。不失一般性，以行为主序存储下三角（包括对角线）中的元素。假设以一维数组B［n（n+1）/2］作为n阶对称矩阵A中元素的存储空间，则B［k］（0≤k<n（n+1）/2）与矩阵元素a_ij（a_ji）之间存在着一一对应的关系。

对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为零。一个n阶的三对角矩阵如下图所示。

三对角矩阵示意图

若以行为主序将n阶三对角矩阵A_n_×_n的非零元素存储在一维数组B［k］（0≤k<3n-2）中，则元素位置之间的对应关系为：

k=3×（i-1）-1+j-i+1=2i+j-3（1≤i，j≤n）

其他特殊矩阵可作类似的推导和计算，这里不再一一说明。

稀疏矩阵

在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵。

对于稀疏矩阵，存储非零元素时必须同时存储其位置（即行号和列号），所以三元组（i，j，a_ij）可唯一确定矩阵中的一个元素。由此，一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。

一个6行7列的稀疏矩阵如下图所示，其三元组表为（1，2，12），（1，3，9），（3，1，-3），（3，6，14），（4，3，24），（5，2，18），（6，1，15），（6，4，-7））。

稀疏矩阵示意图

稀疏矩阵的三元组表构成一个线性表，其顺序存储结构称为三元组顺序表，其链式存储结构称为十字链表。

邻接矩阵表示法

邻接矩阵表示法利用一个矩阵来表示图中顶点之间的关系。对于具有n个顶点的图G=（V，E）来说，其邻接矩阵是一个n阶方阵，且满足：

有向图和无向图的邻接矩阵如下图中的矩阵A和B所示。

有向图和无向图的邻接矩阵存储示意图

由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，而有向图的邻接矩阵则不一定具有该性质。

借助于邻接矩阵，可判定任意两个顶点之间是否有边（或弧）相连，并且容易求得各个顶点的度。对于无向图，顶点ν_i的度是邻接矩阵中第i行（或列）的值不为0的元素数目（或元素的和）；对于有向图，第i行的元素之和为顶点ν_i的出度OD（ν_i），第j列的元素之和为顶点ν_j的入度ID（ν_j）。

类似地，网（赋权图）的邻接矩阵可定义为：

下图所示的是网及其邻接矩阵C。

一个网及其邻接矩阵表示

若图用邻接矩阵表示，则图的数据类型可定义为：

或

数组

数组的定义及基本运算

一维数组是长度固定的线性表，数组中的每个数据元素类型相同。n维数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。

设有n维数组A［b₁，b₂，…，b_n］，其每一维的下界都为1，b_i是第i维的上界。从数据结构的逻辑关系角度来看，A中的每个元素A［j₁，j₂，…，j_n］（1≤j_i≤b_i）都被n个关系所约束。在每个关系中，除第一个和最后一个元素外，其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言，这n个关系仍是线性的。

以下面的二维数组A［m］［n］为例，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。

可将A看作一个行向量形式的线性表：

A_m_*_n=［［a₁₁a₁₂…a₁_n］［a₂₁a₂₂…a_2n］…［a_m₁a_m₂…a_mn］］

也可将A看作列向量形式的线性表：

A_m_*_n=［［a₁₁a₂₁…a_m₁］［a₁₂a₂₂…a_m₂］…［a₁_na₂_n…a_mn］］

数组结构的特点如下：

（1）数据元素数目固定。一旦定义了一个数组结构，就不再有元素的增减变化。

（2）数据元素具有相同的类型。

（3）数据元素的下标关系具有上下界的约束且下标有序。

在数组中通常做下面两种操作：

（1）取值操作。给定一组下标，读其对应的数据元素。

（2）赋值操作。给定一组下标，存储或修改与其相对应的数据元素。

几乎所有的程序设计语言都提供了数组类型。实际上，在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是，不能对数组进行整体的运算，只能对单个数组元素进行运算。

数组的顺序存储

由于数组一般不作插入和删除运算，也就是说，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。

对于数组，一旦确定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置，也就是说，在数据的顺序存储结构中，数据元素的位置是其下标的线性函数。

二维数组的存储结构可分为以行为主序（按行存储）和以列为主序（按列存储）两种方法，如下图所示。

二维数组的两种存储方式

设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为：

Loc（a_ij）=Loc（a₁₁）+（（i-1）×n+（j-1））×L

同理，以列为主序优先存储的地址计算公式为：

Loc（a_ij）=Loc（a₁₁）+（（j-l）×m+（i-1））×L

深度优先遍历

从图G中任一个顶点v出发，深度优先遍历（DFS）的算法步骤如下。

（1）设立搜索指针p，使p指向顶点v。

（2）访问p顶点，并使p指向与p顶点相邻接的且尚未被访问过的顶点。

（3）若p不空，则重复步骤（2）；否则执行步骤（4）。

（4）沿着刚才访问的次序、方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使p指向这个未被访问的邻接顶点，然后重复步骤（2），直至所有的顶点均被访问为止。

这个算法的特点是尽可能先对纵深方向搜索，因此可以很容易得到其遍历的递归算法。

深度优先遍历图的过程实质上是对某个顶点查找其邻接节点的过程，其耗费的时间取决于所采用的存储结构。当图用邻接矩阵表示时，查找所有顶点的邻接点所需时间为O(n²)。若以邻接表作为图的存储结构，则需要O(e)的时间复杂度查找所有顶点的邻接点。因此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。

题号导航 2018年上半年数据库系统工程师上午试卷综合知识

本试卷我的完整做题情况



	第10题在手机中做本题