数据结构基本知识

1、数据结构基础知识 熟识数据结构相关的概念、知识内容 熟记数据结构的基本操作及相应的代码实现 理解数据结构的逻辑结构，能根据题目要求选择合适的数据结构 掌握基本操作及数据结构的基本应用，熟练基本应用的程序设计一、栈一、栈1、栈的定义、栈的定义 栈是一种线性表栈是一种线性表，对它的，对它的插入和删除插入和删除都限制地表的都限制地表的同一同一端端进行。这一端叫做栈的进行。这一端叫做栈的“顶顶”，另一端则叫做栈的，另一端则叫做栈的“底底”。 特点:后进先出后进先出(LIFO)、或者先进后出（、或者先进后出（FILO） 通常栈可以用顺序的方式存储(数组)，分配一块连续的存储区域存放栈中的表目，并用一个变

2、量t指向当前栈顶（如下图）。假设栈中表目数的上限为假设栈中表目数的上限为m，所有表目都具有同一类型，所有表目都具有同一类型stype，则可以用下列方式定义栈：，则可以用下列方式定义栈： Const m=栈表目数的上限；栈表目数的上限；Var s： array1m of stype ；栈栈 t： integer； 栈顶指针，初始值为栈顶指针，初始值为注意：注意：不一定进栈结束后才出栈，进出栈可交叉进行。不一定进栈结束后才出栈，进出栈可交叉进行。2、栈的基本操作、栈的基本操作栈的基本操作包括初始化（栈的基本操作包括初始化（init）、进栈（）、进栈（push）、出栈）、出栈（pop）和读取栈顶元素

3、（）和读取栈顶元素（top）四种。）四种。1） 过程过程init(s,t)procedure init; begin t:=0; end;2)、过程、过程push(x)往栈往栈s中压入一个值为中压入一个值为x的数据：的数据： procedure push（ x：stype)； begin tt+1； stx； x入栈入栈 end；Push3)、函数、函数pop从栈中弹出一个表目从栈中弹出一个表目 function pop ：stype； begin popst； 栈顶元素出栈栈顶元素出栈 tt-1； 指针下移指针下移 end；pop4)、函数、函数top读栈顶元素读栈顶元素 function

4、top ：stype； begin if t=0 then writeln (stack empty) else topst； 返回栈顶元素返回栈顶元素 end；top【竞赛试题】【竞赛试题】 以下哪一个不是栈的基本运算以下哪一个不是栈的基本运算( C) (NOIP7)A)删除栈顶元素删除栈顶元素 B)删除栈底的元素删除栈底的元素 C)判断栈是否为空判断栈是否为空 D)将栈置为空栈将栈置为空栈一个栈的输入顺序为一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的，下列序列中可能是栈的输出序列是输出序列是 ( BCD )。 (A)54312 (B)2415 (C)21543 (D)1253

5、若已知一个栈的入栈顺序是若已知一个栈的入栈顺序是1，2，3，n，其输出序，其输出序列为列为P1，P2，P3，Pn，若，若P1是是n，则，则Pi是是(C ) (NOIP7)A)i B)n-1 C)n-i+1 D)不确定不确定n-i+1 栈的排列遵循先进后（即后进先出）出的原则 因为P1是n，是出栈的第一个数字，说明在n之前进栈的数字都没有出栈，所以这个顺序是确定的。还可以知道，最后出栈的一定是数字1，也就是Pn。代入这个式子，是正确的。 4、设有一个顺序栈、设有一个顺序栈S，元素，元素S1, S2, S3, S4, S5, S6依次依次进栈，如果进栈，如果6个元素的出栈顺序为个元素的出栈顺序为S

6、2, S3, S4, S6, S5, S1，则顺序栈的容量至少应为多少？，则顺序栈的容量至少应为多少？A3 B) 4 C) 5 D) 65、向顺序栈中压入新元素时，应当（、向顺序栈中压入新元素时，应当（ A ）。）。A先移动栈顶指针，再存入元素先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针先存入元素，再移动栈顶指针C先后次序无关紧要先后次序无关紧要 D同时进行同时进行二、队列二、队列 1 队列的定义队列的定义 所谓队列，就是允许所谓队列，就是允许在一端进行插入，在另一端进行删除的线性表。在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针允许插入的一端

7、称为队尾，通常用一个队尾指针w指向队尾元素，即指向队尾元素，即w总总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针指针t指向排头元素。初始时指向排头元素。初始时t=w=0（如下图）。 3265419队列头队列头 t队列尾队列尾 w当他当他tw时时,队列空队列空队列数组队列数组a下标：下标： 1 2 3 4 5 6 7我们按照如下方式定义队列：Const m=队列元素的上限；Type equeue=array1m of qtype； 队列的类型定义Var q：equeue； 队列 t，w：integer； 队尾

8、指针和队首指针2、队列的基本运算、队列的基本运算队列的运算主要有两种：入队（aDD）和出队（DEL）1、过程、过程ADD(x)在队列在队列q的尾端插入元素的尾端插入元素x procedure ADD( x：qtyper)； begin 后移队尾指针并插入元素x w:=w+1； qwx； end；ADD2、函数、函数DEL取出取出q队列的队首元素队列的队首元素 function DEL； begin 取出队首元素并后移队首指针 del:=qt； t:=t+1; end；DEL【竞赛试题】【竞赛试题】已知队列（已知队列（1313，2 2，1111，3434，4141，7777，5 5，7 7，18

9、18，2626，1515），），第一个进入队列的元素是第一个进入队列的元素是1313，则第五个出队列的元素是，则第五个出队列的元素是（ B B ）。）。(NOIP9)(NOIP9) A A） 5 B5 B） 41 C41 C） 77 D77 D） 13 E13 E） 1818设栈设栈S S和队列和队列Q Q的初始状态为空，元素的初始状态为空，元素e e 1 1 ，e e 2 2 ，e e 3 3 ，e e 4 4 ，e e 5 5 ，e e 6 6依次通过栈依次通过栈S S，一个元素出栈后即进入队列，一个元素出栈后即进入队列Q Q，若出队，若出队的顺序为的顺序为e e 2 2 ，e e 4 4

10、 ，e e 3 3 ，e e 6 6 ，e e 5 5 ，e e 1 1 ，则栈，则栈S S的容量至少的容量至少应该为（应该为（ B B ）。）。(NOIP8)(NOIP8) A A）2 B2 B）3 C3 C）4 D4 D）5 5 栈、队列属于线性结构。在这种结构中，不管其存储方式（顺序和链式）如何，数据元素的逻辑位置之间呈线性关系，即每一个数据元素通常只有一个前驱（除第一个元素外）和一个后继（除最后一个元素外）。 但也有很多问题数据元素间的逻辑关系不能用线性结构明确、方便地描述出来。一般来说，至少存在一个至少存在一个结点结点（数据元素）（数据元素）有多于一个前驱或后继的数据结构称为有多于一

11、个前驱或后继的数据结构称为非线非线性结构性结构。具有非线性结构特征的数据结构有两种 树，树，图图三、树三、树一）、一）、.树的概念树的概念1、树的定义、树的定义 树是一种常见的非线性的数据结构。树的递归定义如下：树是一种常见的非线性的数据结构。树的递归定义如下： 树是树是n(n0)个结点的有限集，这个集合满足以下条件：个结点的有限集，这个集合满足以下条件： 有且仅有一个结点没有前驱（父亲结点），该结点称为有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；树的根； 除根外，其余的每个结点除根外，其余的每个结点都有且仅有一个前驱都有且仅有一个前驱； 除根外，每一个结点都通过除根外，每一个结点

12、都通过唯一唯一的路径连到根上（否则的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（以外，路径上的每一个结点都是前一个结点的后继（儿子结儿子结点）；点）；由上述定义可知，由上述定义可知，树结构没有封闭的回路树结构没有封闭的回路。 树可以只有根结点2 2、结点的分类、结点的分类 结点一般分成三类根结点：根结点：没有父亲的结点。在树中有且仅有一个根结点。分支结点：分支结点：除根结点外，有孩子的结点称为分支结点。b，c，x，t，d，i。分支结点亦是其子树的根；叶结点：叶结点：没有孩

13、子的结点称为树叶。w，h，e，f，s，m，o，n，j，u为叶结点。根结点到每一个分支结点或叶结点的路径是唯一的。从根r到结点i的唯一路径为rcti。3 3、有关度的定义、有关度的定义 结点的度：结点的度：一个结点的子树数目称为该结点的度（区分图中结点的度）。图中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。 树的度：树的度：所有结点中最大的度称为该树的度(宽度）。图中树的度为3。4 4、树的、树的深度深度（高度）（高度） 树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的所有结点构成

14、兄弟关系。（e和i也是兄弟关系） 树中最大的层次称为树的深度，亦称高度。图中树的深度为5。5 5、森林、森林 所谓森林，是指若干棵互不相交的树的集合。如图去掉根结点r，其原来的三棵子树Ta，Tb，Tc的集合Ta，Tb，Tc就为森林，这三棵子树的具体形态如图（c）。6 6、有序树和无序树、有序树和无序树 按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。有序树有序树树中任意节点的子结点之间有顺序关系，这种树称为有序树无序树无序树树中任意节点的子结点之间没有顺序关系，这种树称为无序

15、树,也称为自由树， 三）、二叉树的概念三）、二叉树的概念 二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个孩子，且其子树有左右之分（二叉树是有序树，次序不能任意颠倒）。（二叉树可以每个节点只有一个孩子）1 1、二叉树的递归定义和基本形态、二叉树的递归定义和基本形态 二叉树是以结点为元素的有限集，二叉树是以结点为元素的有限集，它或者为空它或者为空，或者满足，或者满足以下条件：以下条件：有一个特定的结点称为根；有一个特定的结点称为根；余下的结点分为互不相交的子集余下的结点分为互不相交的子集L L和和R R，其中，其中L L是根的左子树；是根的左子树；R R是根的右子树；是根的右子树

16、；L L和和R R又是二叉树；又是二叉树；？ 二叉树是不是树？二叉树二叉树是不是树？二叉树树？树？由上述定义可以看出，二叉树和树是两个不同的概念树的每一个结点可以有任意多个后件，而二叉树中每个结点的后继不能超过2；树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。前面引入的有关树的一些基本术语对二叉树仍然适用。下图列出二叉树的五种基本形态：2 2、二叉树的两个特殊形态、二叉树的两个特殊形态满二叉树：满二叉树： 如果一棵深度为K的二叉树，共有2K-1个结点，即第I层有2I-1的结点，称为满二叉树。二叉树。(a)(a)完全二叉树：完全

17、二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(b)）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树3 3、二叉树的三个主要性质、二叉树的三个主要性质性质性质1 1：在二叉树的第i（1）层上，最多有2i-1个结点性质性质2 2：在深度为k(k1)的二叉树中最多有2k-1个结点。性质性质3 3：在任何二叉树中，叶子结点数总比度为2的结点多 1。n0=n2+1(NOIP9)一个高度为h 的二叉树最小元素数目（ C ）。 A） 2h+1 B） h C） 2h-1 D） 2h E） 2h-1(NO

18、IP8)按照二叉数的定义，具有3个结点的二叉树有（ C ）种。 A）3 B）4 C）5 D）6(NOIP8)设有一棵k叉树，其中只有度为0和k两种结点，设n 0 ，n k ，分别表示度为0和度为k的结点个数，试求出n 0 和n k之间的关系（n 0 = 数学表达式，数学表达式仅含n k 、k和数字）。(NOIP7).一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有(B )个结点 （带个数进去试试）A)2h-1 B)2h-1 C)2h+1 D)h+1(NOIP6)已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。 5种、给出一棵

19、二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA画出此二叉树。 D B GE A C HFID GE B HIF C AABDEGCFHI1、将一棵有100个结点的完全二叉树从根结点这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为 A 98 B 99 C 97 D 502、对二叉树从1进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的 编号，则可以采取 C 次序的遍历方法。A 先序 B中序 C后序 D从根开始的层次遍历3、有n个结点并且其高度为n的二叉树的数目是 A、n B

20、、 2n C、 2n-1 D、 2(n-1)4、有64个结点的完全二叉树的深度为（ ） A) 8 B) 7 C) 6 D) 5 四）、二叉树的遍历四）、二叉树的遍历 二叉树的遍历是不重复地访问二叉树中的每一个结点。在访问到每个结点时，可以取出结点中的信息，或对结点作其它的处理。 如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，限定先左后右的次序，三种组合 DLR、LDR、 LRD这三种遍历规则分别称为先（前）序遍历、中序遍历和后序遍历（以根为标准）。二叉树的存储采用动态的二重链表形式。根左右、左根右、左右根为了方便叙述，我们以下图为例解释三种遍历规则，并且分别以二叉链表和数组两种存

21、储结构给出三种遍历的程序。前序遍历前序遍历前序遍历的规则如下：若二叉树为空，则退出。否则 访问处理根结点； 前序遍历左子树； 前序遍历右子树； a b d e h i c f g中序遍历中序遍历中序遍历的规则如下： 若二叉树为空，则退出；否则 中序遍历左子树； 访问处理根结点； 中序遍历右子树；若中序遍历上图中的二叉树，可以得到如下的中序序列： d b h e i a f c g 后序遍历后序遍历后序遍历的规则如下： 若二叉树为空，则退出；否则 后序遍历左子树； 后序遍历右子树； 访问处理根结点； 若后序遍历上图中的二叉树，可以得到如下的后序序列 d h i e b f g c a五）、由五）

22、、由二叉树的两种遍历顺序确定树结构二叉树的两种遍历顺序确定树结构遍历二叉树（如下图）有三种规则： 前序遍历：根左子树右子树； 中序遍历：左子树根右子树； 后序遍历：左子树右子树根；2、(NOIP7)已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：中序遍历:CBGEAFHDIJ后序遍历:CGEBHFJIDA求该二叉树的先序遍历的顺序为：1、给出一棵二叉树的先序遍历：ABCDEFGH中序遍历：CBEDAGHF画出此二叉树并写出后序遍历结果。A B CDE F GHC B ED A GH F石子合并问题 有n堆石子,每堆有一个重量,每次把2堆石子合并成1堆,付出的代价为这两堆石子

23、的重量之和,如果把这n堆石子最后合并成1堆石子,怎样合并才能使付出的代价最小,求出最小的代价.六）、最优二叉树六）、最优二叉树(哈夫曼树哈夫曼树)显然图(D)所示的合并方法付出的代价最小:54 5*2+（2+4）*3+（6+7）*2=54例如n=5,重量 分别为7、5、2、4、6。246511671324 (D)L=6+11+13+24=541、最优二叉树的定义、最优二叉树的定义在具有n个带权叶结点的二叉树中，使所有叶结点的带权路径长度之和（即二叉树的带权路径长度）为最小的二叉树，称为最优二叉树（又称最优搜索树或哈夫曼树），即最优二叉树使（wk第k个叶结点的权值；pk第k个叶结点的带权路径长度

24、）达到最小。 kknkPWL12、最优二叉树的构造方法、最优二叉树的构造方法 假定给出n个结点ki(i=1n)，其权值分别为wi(i=1n)。要构造以此n个结点为叶结点的最优二叉树，其构造方法如下： 首先，将给定的n个结点构成n棵二叉树的集合F=T1，T2，Tn。其中每棵二叉树Ti中只有一个权值为wi的根结点ki，其左、右子树均为空。然后做以下两步 在F中选取根结点权值最小的两棵二叉树作为左右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和； 在F中删除这两棵二叉树，同时将新得到的二叉树加入F中；重复、，直到在F中只含有一棵二叉树为止。这棵二叉树便是最优二

25、叉树。 以上构造最优二叉树的方法称为哈夫曼哈夫曼（huffmann）算法。 例如：给定五个结点k1，k2，k3，k4，k5，其权值分别为16、2、18、16、23。构造最优二叉树的过程如下：构造初始集合F，F中各二叉树根结点的权值分别为16，2，18，16，23（如下图）： 以具有权值16及2的根结点的两棵二叉树为左、右子树，构造一棵根权值为18的新二叉树，并从F中删去这两棵二叉树（如下图）：以同样的方法，得到一个新二叉树的集合F，其根结点的权值分别为23，18，34（如下图）： 又得到一个新二叉树的集合F，其根结点的权值分别为34，41（如下图）：最后得到最优二叉树（如下图），其根结点的权值

26、为75，结点数为2*5-1=9。3、哈夫曼编码使用频率高的采用短的的编码,则总的编码长度便可减少.例如:在某通讯中只使用abcd四种字符,其出现频率分别为:0.4,0.3,0.2,0.1。请进行哈夫曼编码。使通讯码尽可能的短 并写出信息：bbdaac的编码。1.给定一个整数集合3，5，6，9，12，下列二叉树哪个是该整数集合对应的霍夫曼（Huffman）树。 （ ）2、已知如图所示的哈夫曼树，那么电文CDAA的编码是 A 110100 B 11011100 C 010110111 D 11111100 3、若以4，5，6，7,8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 A 、69 B

27、、 70 C 、 73 D、 68 四、四、 图的基本概念图的基本概念1、图的的定义、图的的定义 如果数据元素集合D中的各元素之间存在任意的前驱和后继关系R，则此数据结构G=（D，R）称为图。如果将数据元素抽象为结点，元素之间的先后关系用边表示，则图亦可以表示为G=（V，E），其中V是结点的有穷（非空）集合，E为边的集合。如果元素a是元素b的前驱，这种先后关系对应的边用(a，b)表示，即(a，b)E。图可以分为无向图和有向图两种形式。2、无向图和有向图、无向图和有向图 无向图无向图：在图G=（V，E）中，如果对于任意的a，bV，当(a，b)E时，必有（b，a）E（即关系R对称），对称此图为无向

28、图。在一无向图中用不带箭头的边连接两个有关联的结点。在具有n个结点的无向图中，边的最大数目为：而边数达到最大值的图称为无向完全图。在无向图中一个结点相连的边数称为该结点的度。 图(A) V=1,2,3,4 E=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)有向图：有向图：如果对于任意的a，bV，当(a，b)E时 ，(b，a)E未必成立，则称此图为有向图。在有向图中，通常用带箭头的边连接两个有关联的结点（方向由前件指向后件）。例如图（b）为有向图。有向图中一个结点的后件个数称为该结点的出度，其前件个数称为该结点的入度。一个结点的入度和出度之和称为该结点的度。图中结点的最大

29、度数称为图的度。例如下图 (b)）中结点1的出度和入度分别为1，结点1和结点1度都为2。整个图的度为2。 图(B) V=1,2,3 E=,2) 1(*nn4、 路径和连通集路径和连通集 在图G=（V，E）中，如果对于结点a，b，存在满足下述条件的结点序列x1xk(k1) x1=a，xk=b (xi，xi+1)E i=1k-1则称结点序列x1=a，x2，xk=b为结点a到结点b的一条路径，而路径上边的数目k-1称为该路径的长度，并称结点集合x1，xk为连通集。V1, v2, v5, v45、简单路径和回路、简单路径和回路如果一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同，则称此

30、路径为一条简单路径。图 ( a ) 中 v1 v2 v3是 一 条 简 单 路 径 ，v1v3v4v1v3不是简单路径。x1=xk的简单路径称为回路（也称为环）。例如图(b)中，v1v2v1为一条回路。3、图的存储结构、图的存储结构图的相邻矩阵表示法图的相邻矩阵表示法 相邻矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的相邻矩阵是如下定义的二维数组a，其规模为n*ntype maxn=顶点数的上限；var a：array1.maxn，1.maxnof integer； f：array array1.maxnof boolean； 顶点的访问标志序列上图中的图G1和

31、图G2对应的相邻矩阵分别为： 0100110100248020651146030853001000000010101010001000100 1 1 1 01 0 1 1 11 1 0 1 01 1 1 0 10 1 0 1 0相邻矩阵的特点： 1)无向图的相邻矩阵是对称的，而有向图则不是。无向图的相邻矩阵是对称的，而有向图则不是。 2)相邻矩阵方便度数的计算。相邻矩阵方便度数的计算。用相邻矩阵表示图: (1)容易判定任意两个结点之间是否有边相联; (2)并容易求得各个结点的度数。 (对于无权无向图的相邻矩阵，第i行元素值的和就是Vi的度数；对于无权有向图的相邻矩阵，第i行元素值的和就是Vi的

32、出度，第i列元素值的和就是Vi的入度；)对于有权无向图的相邻矩阵，第i行（或第i列）中元素值0的元素个数就是Vi的度数；对于有权有向图的相邻矩阵，第i行中元素值0的元素个数就是Vi的出度；第i列元素值0的元素个数就是Vi的入度。7、图的遍历图的遍历 给出一个图给出一个图G和其中任意一个结点和其中任意一个结点V0，从，从V0出发系出发系统地访问统地访问G中所有结点，每一个结点被访问一次，这就叫中所有结点，每一个结点被访问一次，这就叫图的遍历。图的遍历。 通常有两种遍历方法： 深度优先搜索dfs 广度优先搜索bfs 它们对无向图和有向图都适用。我们以相邻矩阵存储结构给出深度优先搜索和广度优先搜索的

33、程序。8、深度优先搜索、深度优先搜索DFS 深度优先搜索类似于树的前序遍历，是树的前序遍历的推广。其搜索过程如下： 假设初始时所有结点未曾被访问。深度优先搜索从某个结点V0出发，访问此结点。然后依次从V0的未被访问的邻接点出发深度优先遍历图，直至图中所有和V0有路径相连的结点都被访问到。若此时图中尚有结点未被访问，则另选一个未曾访问的结点作起始点，重复上述过程，直至图中所有结点都被访问为止。换句话说，深度优先搜索遍历图的过程是以深度优先搜索遍历图的过程是以V0为起始点，由左而右，依次访问由为起始点，由左而右，依次访问由V0出发的出发的每条路径每条路径。9、广度优先搜索、广度优先搜索(宽度优先搜

34、索）宽度优先搜索）BFS 广度优先搜索类似于树的按层次遍历的过程，其搜索过程如下： 假设从图中某结点v0出发，在访问了v0之后依次访问v0的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到。若此时图中尚有结点未被访问，则任选其中的一个作起始点，重复上述过程，直至图中所有结点都被访问到为止。换句话说，按广度按广度优先顺序搜索遍历图的过程是以优先顺序搜索遍历图的过程是以v0为起始点，由近及远，依次访为起始点，由近及远，依次访问和问和v0有路径相连且路径长度为有路径相连且路径长度为1，2，3的结点。的结点。10、图的应用、图的应用（一）、（一）、拓扑排序拓扑排序士兵排队士兵排队有有n n个士兵（个士兵（100100），编号依次为），编号依次为1 1，2 2，3 3 。n n，排，排队训练，现在指挥官要把这些士兵从高到矮依次排成行，但现队训练，现在指