三级数据库第二章考试要点

第二章   数据结构与算法
本章内容主要是:数据结构、算法的基本概念;线性表的逻辑结构，链表、数组的存储和运算;队列与栈的定义，存储及应用;树和二*树的定义，互相转换，二*树的存储，二*树的周游;图的基本概念，图的存储的周游;排序的基本概念与排序算法（选择排序，插入排序，交换排序，归并排序）;检索的基本概念与检索算法（顺序检索，二分检索，散列技术检索，二*排序树）。
以下介绍一些常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，以及在这些数据结构上进行的各种运算和实际的执行算法，并对算法的效率进行简单的分析。 
一、基本概念1.什么是数据结构
数据是描述客观事物的数字、字符以及所有能直接输入到计算机中并被计算机程序处理的符号的集合。
数据对象是具有相同性质的数据元素的集合。通常，一个数据对象中的数据元素不是孤立的，而是彼此之间存在着一定的联系，这种联系就是数据结构。数据对象中数据元素之间的联系需要在对数据进行存储和加工中反映出来，因此，数据结构概念一般包括三方面的内容:数据之间的逻辑关系、数据在计算机中的存储方式、以及在这些数据上定义的运算的集合。
（1）数据的逻辑结构
数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，它与数据的存储无关，是独立于计算机的。 
数据的逻辑结构分为线性结构和非线性结构两大类。线性结构的逻辑特征是:有且仅有一个开始结点和一个终端结点，并且所有的结点都最多有一个直叫馨驱和一个直接后继。线性表就是一个典型的线性结构。非线性结构的逻辑特征是:一个结点可能有多个直叫馨驱和直接后继。树、图等都是非线性结构。
（2）数据的存储结构
数据的存储结构是数据的逻辑结构在计算机存储器里的实现（亦称为映象）。它是依赖于计算机的，并有四种基本的存储映象方法。它们是:
①顺序存储方法 该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元内，结点间的逻辑关系由存储单元的邻接关系来体现。顺序存储方法主要用于线性的数据结构，非线性的数据结构也可以通过某种线性化方法来实现顺序存储。
②链接存储方法 在链接存储方法中，逻辑上相邻的结点在物理位置上未必相邻，结点间的逻辑关系是由附加的指针字段表示的。③索引存储方法 该方法通常是在存储结点信息的同时，还建立一个附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是:关键字，地址。关键字是能唯一标识一个结点的那些数据项。
④散列存储方法 在散列存储方法中，结点的存储地址是根据结点的关键字值直接计算出来的。上述四种基本的存储方法也可以组合起来对数据结构进行存储映象。
（3）数据的运算
数据的运算定义在数据的逻辑结构之上，每种逻辑结构都有一个运算的集合。常用的运算有:查找、插入、删除、更新、排序等。显然，对数据运算的具体实现方法只有在确定了存储结构之后才能加以考虑。
2.算法
（1）算法及其特征
简单地说，一个算法就是一种解题方法，更严格地说，算法是由若干条指令组成的有穷序列，它必须具有以下特征:
①有穷性 一个算法必须在执行有穷步后结束。 
②确定性 算法的每一步必须是确切地定义的，无二义性。
③可行性 算法中的所有待实现的运算必须在原则上能够由人使用笔和纸在做有穷次运算后完成。
④输入 一个算法具有0个或多个输入的外界量，它们是算法开始前对算法最初给出的量。⑤输出 一个算法至少产生一个输出，它们是与输入有某种关系的量。
算法的含义与程序十分相似，但二者又有区别。一个程序不一定满足有穷性，操作系统就是如此，只要整个系统不被破坏，操作系统就永远不会停止，所以操作系统程序不是一个算法。另外，程序中的指令必须是机器可以执行的，而算法中的指令则无此限制。但是，一个算法如果用机器可执行的语言书写，则它就是一个程序。
对一个算法的描述可以采用自然语言、数学语言、约定的符号语言、以及图解等方式。
（2）算法的分析
求解同一个问题可以有多种不同的算法，评价一个算法的优劣除了正确性和简明性外，主要考虑两点:一是执行算法所耗费的时间，二是执行算法所耗费的存储空间，特别是辅助存储空间的耗费。就这两者而言，前者显得比后者更为重要，在数据结构中往往更注重对算法执行时间的分析。
一个算法所耗费的时间是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句执行次数（频度）与该语句一次执行所需时间的乘积。如果假定每条语句一次执行所需的时间均为单位时间，则一个算法的时间耗费就是该算法中所有语句的频度之和。
二、线性表
（1）线性表及其基本操作
线性表是n≥0个元素的一个有限序列:（a 1 ，a 2 ，a 3 ，…，a n- 1 ，a n ）
表中元素的个数n称为表的长度，长度n=0的表称为空表。表元素又称为结点，线性表的一个重要特性是可以按照诸元素在表中的位置确定它们在表中的先后次序。若
n≥1，则a 1 ，为第一个元素，a n 为最后一个元素。元素a i-1 先于a i ，我们称a i-1 为a i 的前驱;a i 在a i-1 之后，则a i 为a i-1 的后继。除第一个元素外，每个元素都有一个且仅有一个直叫馨驱;除最后一个元素外，每个元素都有一个且仅有一个直接后继。下面所列的是其中一些常用的运算。①查找运算

·查找线性表的第i（0≤i≤n-1）个表元;
·在线性表中查找具有给定键值的表元;②插入运算
·把新表元插在线性表的第i（0≤i≤n）个位置上;
·把新表元插在具有给定键值的表元的前面或后面;③删除运算
·删除线性表的第i（0≤i≤n-1）个表元;
·删除线性表中具有给定键值的表元;④其他运算
·统计线性表中表元的个数;
·输出线性表各表元的值;
·复制线性表;
·线性表分析;
·线性表合并;
·线性表排序;
·按某种规则整理线性表。
（2）线性表的存储
有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链接存储。①线性表的顺序存储
线性表的顺序存储是最简单的存储方式。程序通常用一个足够大的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中。即线性表的第i个结点存储在数组的第i（0≤i≤n-1）个元素中，用数组元素的顺序存储来体现线性表中结点的先后次序关系。用数组存储线性表的最大优点是能直接访问线性表中的任一结点。
用数组存储线性表的缺点主要有两个:一是程序中的数组通常大小是固定的，可能会与线性表的结点可以任意增加和减少的要求相矛盾;二是执行线性表的结点插、删操作时要移动存于数组中的其他元素，使插和删操作不够简便。②线性表的链接存储
线性表链接存储是用链表存储线性表，最简单的用单链表。如从链表的第一个表元开始，将线性表的结点依次存储在链表的各表元中。即线性表的第i个结点存储在链表的第i（0≤i≤n-1）个表元中。链表的每个表元除要存储线性结点的信息外，还要有一个成分用来存储其后继结点的指针。单链表就是通过链接指针来体现线性表中结点的先后次序关系。每个链表还要有一个指向链表的第一个表元的指针，链表的最末一个表元的后继指针值为空。用链表存储线性表的优点是利用线性表的每个表元的后继指针就能完成插或删的操作，不需移动任何表元。其缺点也主要有两条:一是每个表元增加了一个后继指针成分，要花费更多的存储空间;二是不便随机地直接访问线性表的任一结点。
（3）线性表上的查找
线性表上的查找运算是指在线性表中查找某个链值的结点。根据线性表的存储形式和线性表本身的性质差异，有多种查找算法，如:顺序查找、二分法查找、分块查找、散列查找等。
（4）线性表的新结点插入顺序存储线性表的插入:
设线性表结点的类型为整型，插入之前有n个结点，把值为x的新结点插在线性表的第i（0≤i≤n）个位置上。
完成插入主要有以下几个步骤:
·检查插入要求的有关参数的合理性;
·把原来第n-1个结点至第i个结点依次往后移一个数组元素位置;
·把新结点放在第i个位置上;
·修正线性表的结点个数。
（5）栈
栈的工作原理是采用后进先出（LIFO）技术，栈顶由中央处理器中的栈指示器（SP）指出。在执行PUSH操作中SP减量，而在POP操作中SP增量。
下面从数据结构的角度，进一步说明栈的基本概念与操作。需要说明的是，其工作原理与前面所介绍的是一致的，不同的是脱离了硬件背景，例如，栈顶指针不是中央处理器的某个寄存器的内容，而是一个抽象的数据结构。
栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作。允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。由于元素是按后进先出的次序入栈和出栈的，所以栈又称后进先出表（Last In First Out），简称LIFO表。
栈的基本操作有:
①create（s） 建立一个空栈s。
②empty（s） 测试栈是否为空栈。
③full（s） 测试栈是否满。
④push（x，s） 将元素x插入栈s的栈顶。
⑤top（s） 取栈顶元素。
⑥pop（s） 删除栈顶元素。
由于栈是一种特殊的线性表，栈的各种操作实际上是线性表的操作的特殊情形，所以表示线性表的方法同样可以用来表示栈。
（6）队列
队列可看作是插入在一端进行，删除在另一端进行的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。在队列中，只能删除队头元素。队列的最后一个元素一定是最新入队的元素。因此队列又称先进先出表（First-In-First-Out）。
日常生活中排队购物就是队列应用的例子:新来的顾客排在队尾等待，排在队头的顾客购物后离开队伍。
队列的基本操作有:
①create（Q） 建立一个空队列。
②empty（Q） 测试队列是否为空队列。
③full（Q） 测试队列是否为满。④front（Q） 取队头元素。
⑤enq（X，Q） 向队列中插入一个
元素X。⑥enq（Q） 删除队头元素。
三、数组
线性表（包括栈和队列）都是线性结构，结构中的每个元素只是无结构的数据元素。我们对线性表作进一步的推广，使结构中的元素本身也可以是具有某种结构（如向量）的数据，从而引出了数组这一种新的数据结构。
（1）数组的定义和运算 
类似于线性表，一个二维数组（或称矩阵）可以看成是由m个行向量所组成的向量，也可以看成是由n个列向量所组成的向量。
对于数组的运算，主要有检索和存取数组中某个元素。

（2）数组的顺序存储结构
由于对数组一般不作插入和删除运算，因此，一旦数组被建立，则结构中的元素个数和元素之间的关系就不再发生变动。对这种情况采用顺序存储结构表示数组是比较恰当的。
由于计算机存储单元是一维的结构，而数组是多维的结构，因此就必须把多维结构映射为一维的结构，即把多维结构按一定次序排列成一维的。
四、树型结构
线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。然而，在计算机科学和计算机应用的各个领域中，存在着大量需要用更复杂的逻辑结构加以表示的问题。因此必须研究更复杂的逻辑结构及相应的数据结构。树形结构就是这些更复杂的结构中最重要的一类。
1.树的基本概念
树是一类重要的树形结构，其定义如下:树是n（n>0）个结点的有穷集合，满足:
（1）有且仅有一个称为根的结点;
（2）其余结点分为m（m≥0）个互不相交的非空集合，T 1 ，T 2 ，…，T m ，这些集合中的每一个都是一棵树，称为根的子树。
在树上，根结点没有直叫馨趋。对树上任一结点X来说，X是它的任一子树的根结点的惟一的直叫馨趋。为了讨论方便，我们引入树的若干习惯术语。树上任一结点所拥有的子树的数目称为该结点的度。度为0的结点称为叶子或终端结点，度大于0的结点称为非终端结点或分支点。一棵树中所有结点的度的最大值称为该树的度。若树中结点A是结点B的直叫馨趋，则称A为B的双亲或父结点，称B为A的孩子（即“子女”）或子结点。易知任何结点A的孩子B也就是A的一棵子树的根结点，父结点相同的结点互称为兄弟。一棵树上的任何结点（不包括根本身）称为根的子孙。反之若B是A的子孙，则称A是B的祖先。结点的层数（或深度）从根开始算起:根的层数为1，其余结点的层数为其双亲的层数加1。一棵树中所有结点层数的最大值称为该树的高度或深度。
树（及一切树形结构）是一种“分支层次”结构。所谓“分支”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支”;所谓“层次”是指树上所有结点可以按它们的层数划分不同的“层次”。在实际应用中，树中的一个结点可用来存储实际问题中的一个数据元素，而结点间的逻辑关系（即父结点与子结点之间的邻接关系）往往用来表示数据元素之间的某种重要的、必须加以表达的关系。
用图示法表示任何树形结构时，箭头的方向总是从上到下，即从父结点指向子结点，因此，可以简单地用连线代替箭头。
2.树的基本运算包括:
①求根ROOT（T），引用型运算，其结果是结点X在树T的根结点。
②求双亲PARENT（T，X），引用型运算，其结果是结点X在树T上的双亲结点;若X是树T的根或X不在T上，则结果为一特殊标志。
③求孩子CHILD（T，X，i），引用型运算，其结果是树T上的结点X的第i个孩子;若X不在T上或X没有第i个孩子，则结果为一特殊标志。
④建树CREATE（X，T 1 ，…，T k ），k≥1，加工型运算，其作用是建立一棵以X为根，以T 1 ，…，T k 为第1，…k棵子树的树。
⑤剪枝DELETE（T，X，i），加工型运算，其作用是删除树T上结点X的第i棵子树;若T无第i棵子树，则为空操作。
3.二*树
（1）二*树的基本概念
二*树是结点的有穷集合，它或者是空集，或者同时满足下述两个条件:
①有且仅有一个称为根的结点:
②其余结点分为两个互不相交的集合T 1 、T 2 ，T 1 与T 2 都是二*树，并且T 1 与T 2 有顺序关系（T 1 在T 2 之前），它们分别称为根的左子树和右子树。
二*树是一类与树不同的树形结构。它们的区别是:第一，二*树可以是空集，这种二*树称为空二*树;第二，二*树的任一结点都有两棵子树（当然，它们中的任何一个可以是空子树），并且这两棵子树之间有次序关系，也就是说，它们的位置不能交换。相应地，二*树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子。另外，二*树上任一结点的度定义为该结点的孩子数（即非空子树数）。除这个几个术语之外，树的其它术语也适用于二*树。
特别值得注意的是，由于二*树上任一结点的子树有左、右之分，因此即使一结点只有一棵非空子树，仍须区别它是该结点的左子树还是右子树，这是与树不同的。二*树的基本运算包括:
Ⅰ初始化INITLATE（BT），加工型运算，其作用是设置一棵空二*树BT=。
Ⅱ求根ROOT（BT），引用型运算，其结果是二*树BT的根结点;若BT为空二*树，运算结果为一特殊标志。Ⅲ求双亲PARENT（BT，X），引用型运算，其结果是结点X在二*树BT上的双亲;若X是BT的根或X根本不是BT上的结点，运算结果为一特殊标志。
Ⅳ求左孩子LCHILD（BT，X）和求右孩子RCHILD（BT，X），引用型运算，其结果分别为结点X在二*树BT上的左、右孩子;若X为BT的叶子或X不在BT上，运算结果为一特殊标志。Ⅴ建树CREAT（X，LBT，RBT），加工型运算，其作用是建立一棵以结点X为根，以二*树LBT、RBT分别为X的左、右子树的二*树。
Ⅵ剪枝DELLEFT（BT，X）和DELRIGHT（BT，X），加工型运算，其作用分别为删除二*树BT上结点X的左、右子树;若X无左或右子树，运算为空操作。

与其它数据结构相同，在实际应用中根据需要对基本运算适当增减。
（2）二*树的性质
在某些情况下，了解二*树的下列性质是有帮助的。
性质1 二*树第i（i≥1）层上至多有2 i-1 个结点。
性质2 深度为k（k≥1）的二*树至多有2 k -1个结点。
性质3 对任何二*树，若度数为2的结点数为n 2 ，则叶子数n 0 =n 2 +1。
有两种特殊形态的二*树在讨论问题时很有用，这就是满二*树和完全二*树。深度为k（k≥1）且有2 k -1个结点的二*树称为满二*树。由性质2知，满二*树上各层的结点数已达到了二*树可以容纳的最大值。如果在一棵深度为k（k≥1）的满二*树上删去第k层上最右边的连续j（0≤j<2 k- 1）个结点，就得到一棵深度为k的完全二*树。显然，满二*树也是完全二*树，但反之不然。
完全二*树有下述重要性质（其中［x］表示不大于x的最大整数）:性质4 具有n个结点的完全二*树的深度为［log 2 n］+1。
完全二*树另一个重要性质是对其结点的“按层编号”将得到很好的结果。所谓“按层编号”是指:将一棵树中的所有n个结点按从第一层到最大层、每层从左到右的顺序依次标记为1，2，…，n。
性质5 如果将一棵有n个结点的完全二*树按层编号，则对任一编号为i（1≤i≤n）的结点X有:
（1）若i=1，则结点X是根;若i>1，则X的双亲PARENT（X）的编号为［i/2］。
（2）若2i>n，则结点X无左孩子（且无右孩子）;否则，X的孩子LCHILD（X）的编号为2i。
（3）若2i+1>n，则结点X无右孩子，否则，X的右孩子RCHILD（X）的编号为2i+1。
4.二*树的存储结构
二*树通常有两类存储结构，顺序存储结构和链式存储结构。
（1）二*树的链式存储结构
二*树有不同的链式存储结构，其中最常用的是二*树链表与三*链表。二*树链表的结点形式如下: lchild data rchild
其中，data域称为数据域，用于存储二*树结点中的数据元素;lchild域称为左孩子指针域，用于存放指向本结点左孩子的指针（这个指针及指针域有时简称为左指针）。类似地，rchild域称为右孩子指针域，用于存放指向本结点右孩子的指针（简称右指针）。二*链表中的所有存储结点通过它们的左、右指针的链接而形成一个整体。此外，每个二*链表还必须有一个指向根结点的指针，该指针称为根指针。根指针具有标识二*链表的作用，对二*链表的访问只能从根指针开始。值得注意的是，二*链表中每个存储结点的每个指针域必须有一个值，这个值或者是指向该结点的一个孩子的指针，或者是空指针NULL。
若二*树为空，则root=NULL。若某结点的某个孩子不存在，则相应的指针为空。具有n个结点的二*树中，一共有2n个指针域，其中只有n-1个用来指向结点的左右孩子，其余的n+1个指针域为NULL。
二*树的链式存储结构操作方便，表达简明（二*树的逻辑关系---结点间的父子关系---在二*链表和三*链表中被直接表达成对应存储结点之间的指针），因而成为二*树最常用的存储结构。然而在某些情况下，二*树的顺序存储结构也很有用。
（2）二*树的顺序存储结构
二*树的顺序存储结构由一个一维数组构成，二*树上的结点按某种次序分别存入该数组的各个单元。显然，这里的关键在于结点的存储次序，这种次序应能反映结点之间的逻辑关系（父子关系），否则二*树的基本运算就难以实现。
由二*树的性质5可知，若对任一完全二*树上的所有结点按层编号，则结点编号之间的数值关系可以准确地反映结点之间的逻辑关系。因此，对于任何完全二*树来说，可以采用“以编号为地址”的策略将结点存入作为顺序存储结构的一维数组。具体地说就是:将编号为i的结点存入一维数组的第i个单元。
在这一存储结构中，由于一结点的存储位置（即下标）也就是它的编号，故结点间的逻辑关系可通过它们下标间的数值关系确定。
5.二*树的遍历
由于二*树的基本运
算在链式存储结构上的实现比较简单，无需详加讨论。下面研究二*树的一种较为复杂的重要运算---遍历及其在二*链表上的实现。
遍历一棵二*树就是按某种次序系统地“访问”二*树上的所有结点，使每个结点恰好被“访问”一次。所谓“访问”一个结点，是指对该结点的数据域进行某种处理，处理的内容依具体问题而定，通常比较简单。遍历运算的关键在于访问结点的“次序”，这种次序应保证二*树上的每个结点均被访问一次且仅一次。
由定义可知，一棵二*树由三部分组成:根、左子树和右子树。因此对二*树的遍历也可相应地分解成三项“子任务”:
①访问根根点;
②遍历左子树（即依次访问左子树上的全部结点）;
③遍历右子树（即依次访问右子树上的全部结点）。
因为左、右子树都是二*树（可以是空二*树），对它们的遍历可以按上述方法继续分解，直到每棵子树均为空二*树为止。由此可见，上述三项子任务之间的次序决定了遍历的次序。若以D、L、R分别表示这三项子任务，则人有六种可能的次序LR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”，即子任务②在子任务 ③之前完成，这样就只剩下前三种次序，按这三种次序进行的遍历分别称为先根遍历（或前序遍历）、中根（或中序）遍历、后根（或后序）遍历。

三种遍历方法的定义如下:
先根遍历 若需遍历的二*树为空，执行空操作;否则，依次执行下列操作:①访问根结点;
②先根遍历左子树;③先根遍历右子树。
中根遍历 若需遍历的二*树为空，执行空操作，否则，依次执行下列操作:①中根遍历左子树;②访问根结点;③中根遍右子树。
后根遍历 若需遍历的二*树为空，执行空操作，否则，依次执行下列操作;①后根遍历左子树。②后根遍历右子树。③访问根结点。
显然，上述三种遍历方法的区别在于执行子任务“访问根结点”的“时机”不同;最先（最后、在中间）执行此子任务，则为先根（后根、中根）遍历。
按某种遍历方法遍历一棵二*树，将得到该二*树上所有结点的访问序列。
6.树
树是一种常用的数据结构。为了适应各种应用问题的需要，多种不同的存储结构也相应地建立起来。下面介绍树的三种常用存储结构。
（1）孩子链表表示法
孩子链表表示法是树的一种链式存储结构。与二*树的二*链表存储方法类似，孩子链表表示法的基本思想是:树上的一个结点的内容（数据元素）以及指向该结点所有孩子的指针存储在一起以便于运算的实现。由于树上的结点的度（孩子数）没有限制，而且各个结点的度可能相差很大，一种自然的表示方法是为树上的每个结点X建立一个“孩子链表”，以便存储X中的数据元素和指向X的所有孩子的指针。一个孩子链表是一个带头结点的单链表，单链表的头结点含两个域:数据域和指针域。其中，数据域用于存储结点X中的数据元素;指针域用于存储指向该单链表中第一个表结点（首结点）的指针。为了检索方便，所有头结点组织成一个数组，称为表头数组。对每个结点X的孩子链表来说，其中的所有表结点也含两个域，孩子域（即数据域）和指针域。第i个表结点的孩子域存储X的第i个孩子在头结点数组中的下标值。
（2）孩子兄弟链表表示法
孩子兄弟链表中所有存储结点的形式相同，均含三个域:数据域---用于存储树上的结点中的数据元素;孩子域---用于存储指向本结点第一个孩子的指针;兄弟域---用于存放指向本结点下一个兄弟的指针。
值得注意的是，孩子兄弟链表的结构形式与二*链表完全相同;但存储结点中指针的含义不同。二*链表中存储结点的左、右指针分别指向左、右孩子;而孩子兄弟链表中存储结点的两个指针分别指向“长子”和“大弟”。在孩子兄弟链表表示法中，结点形式统一，结点间的联系比较简洁。同时，在这种存储结构上容易实现树形数据结构的大多数运算。
（3）双亲表示法
树上每个结点的孩子可以有任意多个，但双亲只有一个。因此，通过指向双亲的指针而将树中所有结点组织在一起形成一种存储结构是十分简法的。树的这种存储表示方法称为双亲表示法。在双亲表示法下，每个存储结点由两个域组成:数据域---用于存储树上结点中的数据元素;“指针”域---用于指示本结点之双亲所在的存储结点。值得注意的是，“指针”域的类型定义可以有两种选择。第一种是将其定义为高级语言（如C语句）中的指针类型。通过将存储结点中的指针域定义为高级语言中的指针类型，就得到各种链式存储结构，如单链表、二*链表、孩子链表等等。第二种选择是将“指针”域定义为整型、子界型等型。严格地说，无论选择上述哪种定义，得到的都是链式存储结构，因为在这两种定义之下，各存储结点之间的联结是通过“指针”完成的，而且这些指针反映了结点之间的逻辑关系。
为了区别这两种链式结构，通常将指针域定义为高级语言中的指针类型的各种链式存储结构（如单链表、二*链表等等）称为“动态链表”，相应的指针称为“动态指针”;将指针域定义为整型、子界型等类型的各种键式存储结构称为“静态链表”，相应的“指针”称为:“静态指针”。动态链表中的结点是通过高级语言中的标准过程例如C语言的库函数malloc（size）动态（即运行期间）生成的（动态链表由此得名），无需事先规定链表的容量，因此动态链表的大小是动态变化的。相反，静态链有的容量必须事先说明，因而其大小是固定的。然而，在某些情况下，特别是当结点数固定不变且可事先确定时，采用静态链表往往更加方便、直观。
静态双亲链表由一个一维数组树成。数组的每个分量包含两个域:数据域和双亲域。数据域用于存储树上一个结点中的数据元素;双亲域用于存放本结点的双亲结点在数组中的序号（下标值）。
7.树的遍历
与二*树类似，遍历是树的一种重要运算。树的主要遍历方法有以下三种。
（1）先根遍历若树非空，则
①访问根结点;
②依次先根遍历根的各个子树T 1 ，…，T m 。
（2）后根遍历若树非空，则
①依次先根遍历根的各个子树T 1 ，…，T m 。②访问根结点;
（3）层次遍历
①若树非空，访问根结点;
②若第1，…，i（i≥1）层结点已被访问，且第i+1层结点未访问，则从左到右依次访问第i+1层结点。
显然，按层次遍历所得的结点访问序列中，各结点的序号与按层编号所得的编号一致。
8.树与二*树之间的转换
一般树转换为二*树的基本思想是:将树中每个结点用两个链接表示就可以了，一个指向它最左边的孩子，另一个指向它右边的一个兄弟，从图形上看，具体步骤是:

①加线:在兄弟结点间直接加一虚线;
②抹线:对每个结点，除了其最左的一个孩子外，抹去该结点原来与其余孩子之间的边线;
③旋转:将新加上的虚线改为实线，并将虚线以及有关的实线顺时针旋转45度。
二*树还原为一般树的步骤是:
①加线:若某结点是一父结点的左孩子，则将该结点的右孩子以及沿着右链搜索到的所有右孩子结点都用线与那个父结点连接起来;
②抹线:抹去原二*树中所有结点与其右孩子的连线;
③旋转:将虚线及有关实线逆时针旋转约45度，并将几个结点按层次排列。
9.二*树与森林之间的转换
森林转换为二*树的步骤是:
①将森林中的每棵树转换为二*树;
②森林中第一棵树的根结点就是转换后二*树的根结点，依次将后一棵树作为前一棵树根结点的右子树。
二*树转换为森林的步骤是:
①森林第一棵树的根就是二*树的根;
②二*树的左子树转换为森林的第一棵树，二*树的右子树对应于森林中其余的树;③二*树右子树的根结点作为余下树中第一棵树的根结点……，以此类推。
五、图（一）图的概念
图是一种较线性表和树形结构更为复杂的数据结构。在线性表中每个数据元素只有一个（直接）前驱和后继，即各数据元素之间仅有线性关系。在树形结构中，数据元素之间有明显的层次关系，每一层中的数据元素只和上一层中的一个元素（即双亲结点）相关。而在图中，任意两个数据元素之间均有可能相关。
图（graph）是图型数据结构的简称。它是一种复杂的非线性数据结构。图在各个领域都有着广泛的应用。图的二元组定义为: 
G=（V，E） 其中，V是非空的顶点集合，即
V=｛v i |1≤i≤n，n≥1，v i ∈elemtype，n为顶点数｝ 
E是V上二元关系的集合，一般只讨论仅含一个二元关系的情况，且直接用E表示这个关系。这样，E就是V上顶点的序偶或无序对（每个无序对（x，y）是两个对称序偶<x，y>和<y，x>的简写形式）的集合。对于V上的每个顶点，在E中都允许有任意多个前驱和任意多个后继，即对每个顶点的前驱和后继个数均不加限制。回顾一下线性表和树的二元组定义，都是在其二元关系上规定了限制条件，线性表的限制条件是只允许每个结点有一个前驱和一个后继，树的限制条件是只允许每个结点有一个前驱。因此，图比线性表和树更具有广泛性，它包含线性表和树在内，线性表和树可以认为是图的简单情况。对于一个图G，若E是序偶的集合，则每个序偶对应图形中的一条有向边，若E是无序对的集合，则每个无序对对应图形中的一条无向边，所以可把E看作为边的集合。这样，图的二元组定义可叙述为:图的非空顶点集（vertexset）和边集（edgeset）所组成。针对图G，顶点集和边集可分别记为V（G）和E（G）。边集E（G）允许是空集，若是空集，图G中的顶点均为孤立顶点。对于一个图G，若边集E（G）为有向边的集合，则称此图为有向图（digraph），若边集E（G）为无向边的集合，则称此图为无向图（undigraph）。下图a和b分别为一个无向图G 1 和有向图G 2 ，图中每个顶点里的数字或字母为该顶点的符号、编号或关键字，每个图对应的顶点网络的例子（二）图的基本术语
1.端点和邻接点
在一个无向图中，若存在一条边（v i ，v j ），则称v i ，v j 为此边的两个端点，并称它们互为邻接点（adjacent），即v i 是v j 的一个邻接点，v j 也是v i 的一个邻接点。如在图G 1 中，以顶点v 1 为端点的四条边是（v 1 ，v 2 ），（v 1 ，v 3 ），（v 1 ，v 4 ），（v 1 ，v 5 ），v 1 的四个邻接点分别为v 2 ，v 3 ，v 4 ，v 5 ;以顶点v 3 为端点的两条边是（v 3 ，v 1 ）和（v 3 ，v 4 ），v 3 的两个邻接点分别为v 1 和v 4 。另外，一个顶点v i 和一条边（v i ，v j ）可分别简记为i和（i，j）。如边（v 2 ，v 3 ）和（v A ，v B ）可分别简记为（2，3）和（A，B）。
在一个有向图中，若存在一条边<v i ，v j >，则称此边是顶点v i 的一条出边（outedge），顶点v j 的一条入边（inedge）;称v i 为此边的起始端点，简称为起点或始点，v j 为此边的终止端点，简称终点;称v i 和v j 互为邻接点，并称v j 是v i 的出边邻接点，v i 是v j 的入边邻接点。如在图G 2 中，顶点v B 有两条入边<A，B>，<C，B>和一条出边<B，E>，v B 的两个入边邻接点为v A 和v C ，一个出边邻接点为v E 。

2.顶点的度、入度和出度
图中每个顶点的度（degree）被定义为以该顶点为一个端点的边的数目，记为D（v）。对有向图，顶点v的度又分为入度和出度，入度（indegree）是以该顶点为终点的入边数目，记为ID（v），出度（outdegree）是以该点为起点的出边数目，记为OD（v），顶点v的度就等于它的入度与出度之和，即D（v）=ID（v）+OD（v）。如在图G 1 中，顶点v 1 的度为4，v 2 的度为3;在图G 2 中，顶点v A 的度3，其中入度为0，出度为3，顶点v B 的度也为3，其中入度为2，出度为1。
若一个图中有n个顶点和e条边，则e=12∑ n i=1 D（v i ）。这很容易证明，因为每条边对应2度，所以边数e等于全部顶点度数之和的一半。
3.完全图、稠密图、稀疏图
若无向图中的每两个顶点之间都
存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。显然，若完全图是无向图，则图中包含有n（n-1）/2条边，若完全图是有向图，则图中包含有n（n-1）条边。当一个图接近完全图时，则称为稠密图，相反，当一个图含有较少的边数（即e<<n（n-1））时，则称为稀疏图。下图a就是一个具有五个顶点的无向完全图G 3 ，图b就是一个具有六个顶点的稀疏图G 4 。 
4.子图
设有两个图G=（V，E），G′=（V′，E′），若V′是V的子集，即V′〈V，，且E′是E的子集，即E′〈E，则称G′是G的子图。例如，由G 3 （见下图a）中的全部顶点和同v 1 相连的所有边可构成G 3 的一个子图，由G 3 中的顶点v 1 ，v 2 ，v 3 和它们之间的三条边可构成G 3 的另一个子图。 （a）G 3
（b）G 4
无向完全图和稀疏图
3
2
4
1
5
a
b
c
e
f
d
5.路径和回路
在一个图G中，从顶点v到顶点v′的一条路径（path）是一个顶点序列v i0 ，v i1 ，v i2 …，v im ，其中v=v i0 ，v′=v im ，若此图是无向图，则（v ij-1 ，v ij ）∈E（G），（1≤j≤m）;若此图是有向图，则<v ij-1 ，v ij >∈E（G），（1≤j≤m）。路径长度是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环（cycle），开始点与结束点相同的简单路径被称为简单回路或简单环。如在图G 4 （见上图b）中，从顶点a到顶点e的一条路径为v a ，v b ，v d ，v f ，v e ，其路径长度为4，此路径是一条简单路径;路径v b ，v d ，v f ，v b 为一条简单回路，其路径长度为3;路径v a ，v b ，v d ，v f ，v b 不是一条简单路径，因为其内部存在着回路。
6.连通图和连通分量
在无向图G中，若从顶点v i 到顶点v j 有路径，则称v i 和v j 是连通的。若图G中任意两个顶点都通，则称G为连通图，否则称为非连通图。无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。例如，前面给出的图G 1 和图G 3 都是连通图，下面给出的图a是一个非连通图，它包含有三个连通分量，分别重画
8.权和网
在一个图中，每条边可以标上具有某种含义的数值，此数值称为该边的权（weight）。例如，对于一个反映城市交通线路的图，边上的权可表示该条线路的长度或等级;对于一个反映电子线路的图，边上的权可表示两端点间的电阻、电流或电压;对于一个反映零件装配的图，边上的权可表示一个端点需要装配另一个端点的零件的数量;对于一个反映工程进度的图，边上的权可表示葱馨一子工程到后一子工程所需要的天数。边上带有权的图称为带权图，也称作网（network）。下图中的G 5 和G 6 就分别是一个无向带权图和有向带权图。（三）图的存储结构
图的存储结构又称为图的存储表示或图的表示。它有多种表示方法，这里主要介绍邻接矩阵、邻接表和边集数组三种。
（1）邻接矩阵
邻接矩阵（adjacency matrix）是表示顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，顶点序号依次为1，2，…，n，则G的邻接矩阵是具有如下定义的n阶方阵:A〔i，j〕=1 对于无向图，（v i ，v j ）（v j ，v i ）∈E（G）; 对于有向图，<V i ，V j >∈E（G）0 反之
若图G是一个带权图，则用邻接矩阵表示也很方便，只要把元素1换为相应边上的权值，把元素0换为∞或max即可。其中∞或max表示“无穷大”，实际存储时它要大于图G中所有边上的权值之和。

采用邻接矩阵表示图，便于查找图中任一条边或边上的权。如要查找边（v i ，v j ）或<v i ，v j >，则只要查找邻接矩阵中第i行第j列的元素A〔i，j〕是否非零（或非max）即可;若该元素非零（或非max），则表明此边存在，否则此边不存在。因邻接矩阵中的元素可以随机存取，所以其时间复杂性为O（1）。这种存储表示也便于查找图中任一顶点的度，对于无向图，顶点v i 的度就是邻接矩阵中第i行或第i列上非零（或非max）元素的个数;对于有向图，顶点v i 的度就是邻接矩阵中第i行上非零（或非max）元素的个数。由于求任一顶点的度需访问对应一行或一列中的所有元素，所以其时间复杂性为O（n）。从图的邻接矩阵中查找任一顶点的一个邻接点或所有邻接点同样也很方便。如要查找v i 的一个邻接点（对于无向图）或出边邻接点（对于有向图），则只要在第i行上查找出一个非零（或非max）元素，以该元素所在的列号j为序号的顶点v j 就是所求的一个邻接点或出边邻接点。一般算法要求是依次查找出一个顶点v i 的所有邻接点（对于有向图为出边邻接点或入边邻接点），此时需访问对应第i行或第i列上的所有元素，所以其时间复杂性为O（n）。
图的邻接矩阵存储需要占用n×n个存储单元，所以其空间复杂性为O（n 2 ）。这种存储结构用于表示稠密图能够充分利用存储空间，但若用于表示稀疏图，则使邻接矩阵变为稀疏矩阵，从而造成存储空间的严重浪费。
图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要一个具有n个单元的一维数组存储顶点信息（若顶点除编号外，无其它信息，则无须此数组），其中，第i个元素存储顶点v i 的信息。这两种数组的类型可定义为:const n=｛图的顶点数｝;e=｛图中的边数｝; 
type adjmatrix=array〔1..n，1..n〕of0..1;（下标类型也可为其它子域型或自定义型，若表示带权图，则成分类型应为权值所属类型） vexlist=array〔1..n〕of elemtype;
图的邻接矩阵表示，很容易在内存中生成。
（2）图的邻接表表示法
邻接表（adjacency list）是对图中的每个顶点建立一个邻接关系的单链表，并把它们的表头指针用向量存储的一种图的表示方法。为顶点v i 建立的邻接关系的单链表称作v i 邻接表。v i 邻接表中的每个结点用来存储以该顶点为端点或起点的一条边的信息，因而被称为边结点。v i 邻接表中的结点数，对于无向图来说，等于以v i 为一个端点的边的数目，亦即等于v i 的邻接点数或度数;对于有向图来说，等于v i 的出边数，亦即出边邻接点数或出度数。边结点的类型通常被定义为三个域:一是邻接点域（adjvex），用以存储顶点v i 的一个邻接顶点v j 的序号j;二是权域（weight），用以存储边（v i ，v j ）或<v i ，v j >上的权;三是链域（next），用以链接v i 邻接表中的下一个结点。在这三个域中，邻接点域和链域是必不可少的，权域只对带权图是必需的，对无权图，则可省去此域。对于每个顶点v i 的邻接表，需要设置一个表头结点，该结点除了包括v i 邻接表的表头指针域（link）外，通常还需要包含用于存储顶点v i 信息的值域（data），若顶点v i 的值就是该顶点的编号i，则此域应省略。若图G中有n个顶点，则就有n个表头结点，为了便于随机访问任一顶点的邻接表，需把这n个表头结点用一个向量（即一维数组）存储起来，其中第i个分量存储v i 邻接表的表头结点。这样图G就可以通过这个表头向量来存取。
图的邻接表表示不是唯一的，因为在每个顶点的邻接表中，各边结点的链接次序可以任意安排，其具体链接次序与边的输入次序和生成算法有关。
在图的邻接表中便于查找一个顶点的边（出边）或邻接点（出边邻接点），这只要首先从表头向量中取出对应的表头指针，然后从表头指针出发进行查找即可。由于每个顶点单链表的平均长度为e/n（对于有向图）或2e/n（对于无向图），所以此查找运算的时间复杂性为O（e/n）。但要从有向图的邻接表中查找一个顶点的入边或入边邻接点，那就不方便了，它需要扫描所有顶点邻接表中的边结点，因此其时间复杂性为O（n+e）。对于那些需要经常查找顶点入边或入边邻接点的运算，可以为此专门建立一个逆邻接表（contrary adjacency list），该表中顶点的单链表不是存储该顶点的所有出边信息，而是存储所有入边信息。
在有向图的邻接表中，求顶点的出边信息较方便，在逆邻接表中，求顶点的入边信息较方便，若把它们合起来构成一个十字邻接表（orthogonal adjacency list），则求顶点的出边信息和入边信息都将很方便。
在十字邻接表中，每个边结点对应图中的一条有向边，它包含五个域:边的起点域和终点域，边上的权域，入边链域和出边链域，其中入边链域用于指向同一个顶点的下一条入边结点，通过它把入边链接起来，出边链域用于指向同一个顶点的下一条出边结点，通过它把出边链接起来。十字链接表中的每个表头结点包括三个域:顶点值域、入边表的表头指针域和出边表的表头指针域。

在图的邻接表、逆邻接表和十字邻接表中，表头向量需要占用n个存储单元，所有边结点需要占用2e（对于无向图）或e（对于有向图）个存储单元，所以图的邻接表表示的空间复杂性为O（n+e）。这种存储结构用于表示稀疏图比较节省存储空间，因为只需要很少的边结点，若用于表示稠密图，则将占用较多的存储空间，同时也将增加在每个顶点邻接表中查找结点的时间。 6

十字邻接表
图的邻接表表示和图的邻接矩阵表示，虽然方法不同，但也存在着对应的关系。邻接表中每个顶点v i 的单链表对应邻接矩阵中的第i行，整个邻接表可看作是邻接矩阵的带行指针向量的链接存储;整个逆邻接表可看作是邻接矩阵的带列指针向量的链接存储;整个十字邻接表可看作是邻接矩阵的十字链接存储。我们知道，对于稀疏矩阵，若采用链接存储是比较节省存储空间的，所以稀疏图的邻接表表示比邻接矩阵表示要节省存储空间。前面图的例子中的无向图G 1 用邻接表法表示如下图a。用邻接表法表示有向图，根据需要可以保存每个结点的出边表（即以该结点为始点的边的表），也可以保存每个结点的入边表（即以该结点为终点的边的表）。前面图的例子中的有向图G 2 用邻接表法表示如下图b所示，其中图（1）是保存出边表的情况，图（2）是保存入边表的情况。 
（3）边集数组
边集数组（edgeset array）是利用一维数组存储图中所有边的一种图的表示方法。该数组中所含元素的个数要大于等于图中边的条数，每个元素用来存储一条边的起点、终点（对于无向图，可选定边的任一端点为起点或终点）和权（若有的话），各边在数组中的次序可任意安排，也可根据具体要求而定。边集数组只是存储图中的所有边的信息，若需要存储顶点信息，则还需要另外一个具有n个元素的一维数组。设图G中的顶点数为n，边数为e，且不需要存储顶点信息，则图的边集数组表示的有关类型定义和生成一个无向带权图的边集数组的算法描述如下: type degenode=record｛｝ fromvex，endvex:1..n; ｛边的起点和终点域，亦可定义为其它子域型或自定义型｝ weight:｛权值的类型，对无权图可省去此域｝end edgeset=array〔1..m 0 〕of edgenode; ｛定义边集数组类型，其中m 0 要大于等于图中的边数e｝ procedure crate3（GE）; ｛GE为具有edgeset类型的变参，表示一个边集数组｝ begin for k:=1to do （1）read（i，j，w）;｛读入一条边的信息｝ 
（2）GE〔k〕.fromvex:=i;GE〔k〕.endvex:=j;GE〔k〕.weight:=w ｛把读入的一条边写入边集数组的第k个单元｝ end;在边集数组中查找一条边或一个顶点的度都需要扫描整个数组，所以其时间复杂性为O（e）。边集数组适合那些对边依次进行处理的运算，不适合对顶点的运算和对任一条边的运算。边集数组表示通常包括一个边集数组和一个顶点数组，所以其空间复杂性为O（n+e）。从空间复杂性上讲，边集数组也适合表示稀疏图。图的邻接矩阵、邻接表示和边集数组表示各有利弊，具体应用时，要根据图的稠密和稀疏程度以及运算的要求进行选择。
（四）图的周游和生成树1.图的周游
从图中某一结点出 发，系统地访问图中所有结点，使每个结点恰被访问一次，这种运算称作图的周游（或遍历），通常有两种周游图的方法。深度优先周游:这种周游方法类似于树的先根次序周游。从图中某个结点V 0 出发，访问此结点，然后依次从V 0 的未被访问的邻接结点出发进行深度优先周游，直至图中所有和V 0 有路径相通的结点均被访问到。若此时图中尚有结点未被访问，则另选图中一个未被访问的结点作起始点，重复上述过程，直至图中所有结点都被访问到为止。例如，深度优先周游图c的有向图，得到的结点序列是:（a，b，c，f，d，e，g）。深度优先周游图d的无向图，得到的结点序列是V 1 ，V 2 ，V 4 ，V 8 ，
广度优先周游:这种周游方法类似于树的层次次序周游。从某个结点V 0 出发，访问此结点，然后依次访问与V 0 邻接的未被访问过的结点，然后再分别从这些结点出发进行广度优先周游，直至图中所有被访问过的结点的相邻结点都被访问到。若此时图中尚有结点未被访问，则另选图中一个未曾访问的结点作起始点，重复上述过程，直至图中所有结点都被访问到为止。例如，前面广度优先周游有向图c得到的结点序列是:a，b，d，e，f，c，g。前面广度优先周游无向图d得到的结点序列是:V 1 ，V 2 ，V 3 ，V 4 ，V 5 ，V 6 ，V 7 ，V 8 。
2.生成树
图的所有结点加上周游中经过的边所构成的子图称为图的生成树。前面图c的有向图的深度优先生成树和广度优先生成树分别如下图e（1）和（2）所示。图d的大肥猪先生成树和广度优先生成树分别如图f（3）和（4）所示。 b

图e有向图的生成树
（1）深度优先生成树
（2）广度优先生成树
（3）深度优先生成树
（4）广度优先生成树

图f无向图的生成树
3.最小生成树
图的生成树不是唯一的，从不同的结点出发进行周游可以得到不同的生成树。n个结点的生成树有n-1条边。对于网络，边是带权的，因此可以提出这样的问题，如何找一个网络的最小生成树，即各边权的总和为最小的生成树。这个问题很有实际意义。例如图2-9（a）的网络代表6个城市间的交通网，边上的权是公路的造价，现在要用公路把6个城市联系起来，这至少需要修筑5条公路，如何设计使得这5条公路总的造价最少呢?这就是找最小生成树的问题。可以用这样的方法来构造最小生成树:从任意一个结点开始，首先把这个结点包括在生成树里，然后在那些其一个端点已在生成树里，另一个端点还未在生成树里的边中，找权最小的一条边，并把这条边和其不在生成树里的那个端点包括进生成树里。如此进行下去，每次往生成树里加一个结点和一条权最小的边，直到把所有的结点都包括进生成树里。当有两条具有同样的最小权的边可供选择时，先哪一条都行，因此构造的最小生成树不是唯一的。例如下图图（b）和图（c）就是图（a）网络的两个不同的最小生成树。 V 5
网络的最小生成树
（五）图的遍历
图的遍历就是从指定的某个顶点（称为初始点）出发，按照一定的搜索方法，对图中的所有顶点各作一次访问的过程。图的遍历比树的遍历要复杂，因为从树根到达树中的每个结点只有一条路径，而从图的初始点到达图中的每个顶点可能存在着多条路径。当顺着图中的一条路径访问过某一顶点后，可能还会顺着另一条路径回到该顶点。为了避免重复访问图中的同一个顶点，必须记住每个顶点是否被访问过，为此可设置一个辅助数组visited〔1..n〕，它的每个元素的初值均为逻辑值假或数值0，表示未被访问过，一旦访问了顶点v i ，就把对应元素visited〔i〕置为逻辑值真或数值1，表明v i 已被访问过。根据搜索方法的不同，图的遍历有两种:一种叫做深度优先搜索遍历;另一种叫做广度优先搜索遍历。
1.深度优先搜索遍历
深度优先搜索（depth-first search）遍历类似于树的先根遍历，它是一个递归过程，可叙述为:首先访问一个顶点v i （一开始为初始点），并将其标记为已访问过，然后从v i 的一个未被访问过的邻接点（有向图的入边邻接点除外，下同）出发进行深度优先搜索遍历，当v i 的所有邻接点均被访问过时，则退回到上一个顶点v k ，从v k 另一个未被访问过的邻接点出发进行深度优先搜 1
2
4
6
3
5
7
G 7
索遍历。下面结合右图所示的无向图G 7 分析以v 1 作为初始点的深度优先搜索遍历的过程。
（1）访问顶点v 1 ，并将visited〔1〕置为真，表明v 1 已被访问过，接着从v 1 的一个未被访问过的邻接点v 2 （v 1 的三个邻接点v 2 ，v 3 和v 4 都未被访问过，假定取v 2 ）出发进行深度优先搜索遍历;
（2）访问顶点v 2 ，并将visited〔2〕置为真，表明v 2 已被访问过，接着从v 2 的一个未被访问过的邻接点v 5 （v 2 的四个邻接点中只有v 1 被访问过，其余三个邻接点v 5 ，v 6 ，v 7 均未被访问过，假定取v 5 ）出发进行深度优先搜索遍历;
（3）访问顶点v 5 ，并将visited〔5〕置为真，表明v 5 已被访问过，接着从v 5 的一个未被访问过的邻接点v 6 （只此一个）出发进行深度优先搜索遍历;
（4）访问顶点v 6 ，并将visited〔6〕置为真，表示v 6 已被访问过，接着因v 6 的两个邻接点v 2 和v 5 都被访问过，所以退回到上一个顶点v 5 ，又因v 5 的两个邻接点v 2 和v 6 都已被访问过，所以再退回到上一个顶点v 2 ，v 2 的四个邻接点中有三个已被访问过，此时只能从未被访问过的邻接点v 7 出发进行深度优先搜索遍历;
（5）访问顶点v 7 ，并将visited〔7〕置为真，表明v 7 已被访问过，接着从v 7 的一个未被访问过的邻接点v 3 （只此一个）出发进行深度优先搜索遍历;
（6）访问顶点v 3 ，并将visited〔3〕置为真，表明v 3 已被访问过，接着因v 3 的所有邻接点（即v 1 和v 7 ）都被访问过，所以退回到上一个顶点v 7 ，同理，由v 7 退回到v 2 ，由v 2 奶回到v 1 ，再从v 1 的一个未被访问过的邻接点v 4 （只此一个）出发进行深度优先搜索遍历;
（7）访问顶点v 4 ，并将visited〔4〕置为真，表明v 4 已被访问过，接着因v 4 的所有邻接点（仅有一个）都被访问过，所以退回到上一个顶点v 1 ，又因v 1 的所有邻接点都已被访问过，所以再退回，实际上就结束了对G 7 的深度优先搜索遍历的过程，返回到调用此算法的主程序中去。从以上对大肥猪先搜索遍历的过程分析可行，从初始点v 1 出发，访问G 7 中各顶点的次序为:v 1 ，v 2 ，v 5 ，v 6 ，v 7 ，v 3 ，v 4 。假定GA和GL分别表示图G的邻接矩阵和邻接表visited（1..n）为保存顶点访问标记的辅助数组（元素初值均为false），并假定它们在算法中均为全程量，下面分别以邻接矩阵和邻接表作为图的存储结构，给出相应的深度优先搜索遍历的算法描述。 procedure dfs1（i） ｛从初始点v i 出发深度优先搜索遍历邻接知阵GA表示的图｝ begin （1）write（i）;｛访问顶点v i ，以打印该顶点的序号代之｝ （2）visited〔i〕:=true;｛标记v i 已被访问过｝ （3）for j:=1to n do｛依次搜索v i 的邻接点｝ if（GA〔i，j〕=1）and（not visited〔j〕） then dfs1（j）｛若v i 的一个邻接点v j 未被访问过，则从v j 出发进行递归调用｝ end; procedure dfs2（i） ｛从初始点v i 出发深度优先搜索遍历邻接表GL表示的图｝ begin （1）write（i）; （2）visited〔i〕:=true; （3）p:=GL〔i〕.link;｛取v i 邻接表的表头指针｝ （4）while p<>nil do｛依次搜索v i 的邻接点｝ （Ⅰ）j:=^p.adjvex;｛j为v i 的一个邻接点的序号｝ （Ⅱ）if not visited〔j〕 then dfs2（j）;｛如果v i 的一个邻接点v j 没有被访问过，则从v j 出发进行递归调用｝ （Ⅲ）p:=p^.next;｛使p指向v i 的下一个邻接点所对应的边结点｝ end;上图的G 7 所对应的邻接矩阵和邻接表分别如图a和b所示，请读者结合此图分析上面的两个算法，看从顶点v 2 出发得到的深度优先搜索遍历的顶点序列是否分别为以下序列。序列1:v 2 ，v 1 ，v 3 ，v 7 ，v 4 ，v 5 ，v 6 序列2:v 2 ，v 7 ，v 3 ，v 1 ，v 4 ，v 6 ，v 5 所对应的邻接矩阵和邻接表