简单的数据结构

数据结构为了编写一个“好”的程序，必须分析待处理的对象特性以及各处理对象之间存在的关系.这就需要学习“数据结构”。因此，简单地说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。在信息学奥赛中需要学习线性表、树、图三种数据结构，在后面我们将一一介绍.4.1栈线性表是最常用且比较简单的一种数据结构，它是由有限个数据元素组成的有序集合，每个数据元素有一个数据项或者含多个数据项.例如我们前面所学过的数组是线性的数据结构.下面介绍的栈是一种线性表，但是对它的插人和删除等操作都限制在表的同一端进行，即栈顶，而另一端则称为是栈底.打个形象地比喻，用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆.取走时，只能从上面一件一件取.堆和取都在顶部进行，底部一般是不动的.所以，栈也称为后进先出表（LIFO表）.通常栈可以用顺序的方式存储，分配一块连续的存储区域来存放栈中的数据项，即用定长为N的数组S来表示，并用一个变量TOP指向当前栈顶（如图4-1-1）.若TOP=0，表示栈空，T0P=N时栈满.我们一般把插人操作称为进栈（PUSH），此时TOP加1，删除操作则称为出栈（POP），则TOP减1.当TOP<0时为下溢.用Pascal语言来模拟栈的定义和操作.1栈的定义：CONSTN栈数据项的上限TYPEstack=array[1..n]ofstype；{styp代表数据项类型}VARs：stack；2进栈过程push（s，x，top）——往栈S中压人一个值为X的数据项procedurepush(vars:stack；x：stype；vartop：integer)；BEGINiftop=0thenwrite’underflow’)else

BEGINBEGINtop:=top+1s[top]:=xENDEND出栈函数pop(s,top)——从栈中弹出一个数据项functionpop(vars：stack；vartop：integer):stype；BEGINiftop=0thenwriteln(’underflow’)elseBEGINpop:=s[top；top:=top-1ENDEND读数函数stop(s,top)——读栈顶的数据项functionstop(vars:stackt：integer)：stypeBEGINiftop=0thenwriteln(’stackempty’)elsestop:=s[top；END栈的用途极为广泛，在源程序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈.从历届初赛可以看出，栈也是属于比较容易出题的知识点，选择题、解答题等题型都有可能出现.例、设输入元素为1、2、3、P和A，输人次序为123PA，如图4.1.2所示，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？高级语言变量名的定义规则：以字母开头，字母与数字的组合.由于必须以字母开头，所以，第一个可能出现的字母是P，那么必然要求123已经先后入栈，这样便可得到以P开头的、并且123按逆序排列的(即321)、同时A位于P后任一位置的变量名序列.此外，还需要考虑以A开头的可能情况，这只有一种情形:AP321.所以AP321，PA321，P3A21，P32A1，P321A可以作为高级语言的变量名.例、 中缀表达式A-（B+C/D）*E的后缀形式是什么？中缀形式：即一般情况下的表达方式，将运算符写于参与运算的操作数的中间，操作数依原序列排。后缀形式：式中不再引人括号，运算符放在参与运算的操作数之后，操作数的排列依原序列，所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规则）.所以利用椎栈的特性，可以得出本题的答案是ABCD/+E*-。前缀表达式：同后缀表达式一样，不包含括号，运算符放在两个运算对象的前，如一A*+B/CDE。【练习题】单项选择题1、 设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈，出栈顺序为b，d，c，f，e，a那么栈容量至少应该是（ ）。A.6 B.5 C.4 D.3 E.22、 一个栈的入栈序列为a，b，c，d，e，则栈的不可能输出序列为（）A、edcba B、decbaC、dceabD、abcde3.设栈的输人序列为1、2、3、 、n，输出序列为al、a2、 、an，若存在1<=k<=n使得ak=n，则当k<=i<=n时，ai为（）.A.n-i+1 B.n-（i-k） C不确定4、 设栈的输入序列是（1、2、3、4），则（）不可能是其出栈序列.A.1243 B.2134C.1432 D.4312E.32145、 已知一算术表达式的中缀形式为A+B*C—D/E，其后缀形式为ABC*+DE/一，其前缀形式为（）.A.-A+B*C/DEB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE6、 设栈的输入序列是1、2、…、n，若输出序列的第一个元素是n，则第i个输出元素是（）入不确定 B.n-i+lC.i D.n-i4.2队列队列是限定在一端进行插入，另一端进行删除的特殊线性表。正像排队买东西，排在前面人买完东西后离开队伍（删除），而后来的人总是排在队伍末尾（插入）.通常把队列的删除和插分别称为出队和人队.允许出队的一端称为队首，允许人队的一端称为队尾.所有需要进队数据项，只能从队尾进人，队列中的数据项只能从队首离去.由于总是先入队的元素先出队（排队的人先买完东西），这种

表也称为“先进先出"(FIFO)表.队列可以用数组Q[1„m]来存储，数组的上界m即是队列所容许的最大容量.在队列的算中需设两个指针：head队首指针，指向实际队头元素的前一个位置tail队尾指针，指向实际队尾元素所在的位置队列中拥有的元素个数为：L=tail—head.一般情况下，两个指针的初值设为O,这时队列为空，没有元素.用Pascal用Pascal语言模拟队列的定义和操作.1.队列的定义CONSTm耿列元素的上限;TYPE｛队列的类型定义｝equeue=array[1..m]ofqtype；｛队列的类型定义｝VARq：equeue；headtail：integer；2.人队过程add(q，x，taxi)｛队列｝｛队首指针与队尾指针｝在队列的尾端插入元素xprocedureadd(varq：equeue；x：qtype；vattail：integer)；BEGIN｛队列满上溢｝iftail：mthenwriteln(’overflow’)｛队列满上溢｝elseBEGINtail:=tail+l；q[tail]:=x；ENDEND；3.出队过程del(q，y，head，tail) 取出q队列的队首元素Yproceduredel(varqequeue；Vary：qtype；Varhead，tail：integer)；BEGINifhead=tailthenwriteln(’underflow’) ｛歹0表空下溢｝elseBEGINhead:=head+1;y:=q[head];ENDEND对循环队列的操作要区别于一般队列：初始时队列空，队首指针和队尾指针均指向存储空间的最后一个位置，即head=tail：m.TOC\o"1-5"\h\z入队运算时，尾指针进一，即 -[tail:=tail+l；iftail=m+1thentail:=1这两条语句可用一条语句替代：tail:=tailmodm+1 '■ ■-出队运算时，首指针进一，即 "-I-head:=head+1；ifhead=m+1thenhead:=1这两条语句可用一条语句替代：head:=headmodm+1队列空时，head=tail队列满时，head=tailmodm+1为了区分队列空和队列满，改用“队尾指针追上队首指针’’这一特征作为队列满标志.这种处理方法的缺点是浪费队列空间的一个存储单元.所以，我们重新得到另外两种循环队列的运算.1.人队过程add(q，x，taxi) 在队列的尾端插入元素xprocedureadd(vatq：equeue；x：qtype；vartajl：integer)；VARt：integer；BEGINt:=tailmodm+1；ift=headthenwriteln('full')elseBEGINtai：l=t；q[tail]:=xENDEND2.出队过程del（q，y，head，tail） 取出q队列的队首元素yproceduredel（varq：equeue；vary：qtype；varhead：integer）；BEGINifhead二tailwriteln（'empty’）elseBEGINhead:=headmodm+1y:=q[head]；ENDEND【练习题】单项选择题：1.若用一个大小为6的数组来实现循环队列，且当一和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？A.1和5 B.邪4TOC\o"1-5"\h\zC.4和2 D.和12.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）.A.6 B.4C.3 D.23.如右图所示的循环队列中元素数目是（）.其中仙* :、'tail=32指向队尾元素，head=15指向队首元素的前 /一个空位置，队列空间m=60.A.42 B.16C.17 D.414.3树前两节学习的栈和队列属于线性结构.在这种结构中，数据元素的逻辑位置之间呈线性关系，每一个数据元素通常只有一个前件（除第一个元素外）和一个后件（除最后一个元素外）.在实际生活中，可以用线性结构描述数据元素之间逻辑关系的问题是很广泛的，但也有很多问题不能依靠线性结构来解决，例如家谱、行政组织机构等都是非线性的数据结构.其中树就是一种非线性的数据结构.一）树的递归定义为树（Tree）是n（n、O）个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1有且仅有一个特定的称为根（Root）的结点；

（2其余的结点可分为m（m》0）个互不相交的子集，T1,T2,…，Tm,其中每个子集本身又是一棵树，并称其为根的子树（Subtree）.比如在现实生活中，有如下血统关系的家族可用树形图（图4-3-1）表示：张源有三个孩子张明、张亮和张丽；张明有两个孩子张林和张维；张亮有三个孩子张平和张群；张丽有两个孩子张晶和张磊.以上表示很像一棵倒画的树.其中“树根”是张源，树的“分支点”是张明、张亮和张平，该家族的其余成员均是“树叶”，而树枝（即图中的线段）则描述了家族成员之间的关系.显然，以张源为根的树是一个大家庭.它可以分成张明、张亮和张丽为根的三个小家庭；每个小家庭又都是一个树形结构.以下介绍几个关于树的基本概念.度.一个结点的子树数目称为该结点的度.所有结点中最大的度称为该树的度.如图4-3-2,结点i的度为3,结点t的度为2，结点b的度为1.显然，所有树叶的度为0，该树的度为3.2.树的层次和高度.树是分层次的，结点所在的层次是从根算起的，根节点在第一层，根的后件在第二层，其余各层依此类推.树中最大的层次称为树的深度，亦称高度.如图中，树共有5层，树的高度为5.3.森林.若十棵互不相交的树的集合。如图去掉根结点r,其原来的三棵子树的集合即为森林。（二）二叉树二叉树（BinaryTree）是树形结构的一个重要类型.许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二又树的存储结构及其算法都较为简单，因此二又树显得特别重要.但是值得特别注意的是：二叉树并非是树的特殊情形，它们是两种不同的数据结构.下面给出二叉树的递归定义：二叉树是n（n>0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成.二叉树的五种基本形态如图4-3-3所示.二叉树具有以下重要性质：性质1二叉树第i层上的结点数目最多为2i-i(iNl):性质2深度为k的二叉树至多有2k-1个结点(k\1).，性质3在任意一棵二叉树中，若终端结点的个数为n0,度为2的结点数为n2,

则n0=n2+1.例、有n个结点的二叉树，已知叶结点个数为n0,写出求度为1的结点的个数nl的计算公式；若此树是深度为k的完全二叉树，写出n为最小的公式；若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式.(1祀度为2的结点个数为n2，则n=n0+n1+n2 ①又因为除了根结点以外，其余结点均由父结点射出，所以n=l+nl+2②12由①②两式得n1=n+1-2n0当树是深度为k的完全二叉树时，n的最小值n.=2k-1min当二叉树中仅有度为0和度为2的结点时，n=n0+n2.n=2n2+1所以：n0=n2+1n=2n0-1满二叉树和完全二叉树是二叉树的两种特殊情形.1.满二叉树(FullBinaryuTree)一棵深度为k且有2k-1个结点的二叉树称为满二叉树.满二叉树的特点：每一层上的结点数都达到最大值.即对给定的高度，它是具有最多结点数的二叉树.满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上.可以验证具有n个叶结点的满二叉树共有2n-1个结点.如图(a)是一个深度为4的满二叉树.2.完全二叉树(CompleteBinaryTree)若一棵二叉树至多只有最下面的两层上结点的度数可以小于2,并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树.特点：满二叉树是完全二叉树，完全二叉树不一定是满二叉树.在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树.在完全二又树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点.如图(b)是一棵完全二叉树.0)满二叉树 .(b)完全二又树，性质4 具有n个结点的完全二叉树的深度为[lgn或11g(n+1)]证明：设所求完全二叉树的深度为k.由完全二叉树定义可得：深度为k得完全二叉树的前k—l层是深度为k一1的满二叉树，一共有2k-1-1个结点.由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：n>2k-1-1.另一方面，由性质2可得：n^2k一'1，艮即 k-1-2<n^2k一'1由此可推出：2k-1^n<2k，取对数后有：k-1^lgn<k又因k一1和k是相邻的两个整数，故有k-1=[lgn]，由此即得：k=[lgn]+l例、 已知一棵完全二叉树共有892个结点，试求：(1)树的高度(2)叶子结点数(3)单支结点数(4)最后一个非终端结点的序号【解答】(1)已知深度为k的二叉树至多有2k-1个结点(kN1)，由于29-l<892<210-1所以树的高度为l0.(2对完全二叉树来说，度为1的结点只能是0或1.由n=n0+nl+n2和n0=n2++1设nl=0，则有：892=n0+0+n2=n2+1+n2=2n2+1，因得到的n2不为整数而出错；设n1=1，则有：892：n0+1+n2：n2+l+1+n2=2n2+2，得到0n2=445，代入n0=n2+1则最后得到n0=446，故叶子结点数为446.由(2)可知单支结点数为1.对有n个结点的完全二又树，最后一个树叶结点，即序号为n的叶结点其双亲结点n/2，即为最后一个非终端结点，也即序号为向下取整(892/2)=446.此外，由(2)可知:n2=44，n1=1；则最后一个非终端结点的序号为：445+1=446。(三)二叉树的遍历所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次访问。访问结点所做的操作依赖具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础.1遍历方案从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成.因此，在任一给定结点上，可以按某种次序执行三个操作：(1访问结点本身(N);遍历该结点的左子树(L)；遍历该结点的右子树(R).以上三种操作有六种执行次序：NLRLNR、LRN、NRL、RNL、RLN.注意：前三种次序与后三种次序对称，故只讨论先左后右的前三种次序.2三种遍历的命名根据访问结点操作发生位置命名：NLR：前序遍历(PreorderTraversal亦称(先序遍历))——访问结点的操作发生在遍历其左右子树之前.LNR：中序遍历(InorderTraversal)——访问结点的操作发生在遍历其左右子树之中(间).LRN：后序遍历(PostorderTraversal)——访问结点的操作发生在遍历其左右子树之后.由于被访问的结点必是某子树的根，所以N(Node)、L(Leftsubtree)和R(Rightsubtree)又可解释为根、根的左子树和根的右子树.NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历.

3.遍历算法.为了叙述方便，我们以如下图为例解释三种遍历的方法.①中序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：遍历左子树;访问根结点；遍历右子树.按照以上算法，可以得到图中二叉树的中序序列为dbheiafcg.先序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：访问根结点；遍历左子树；遍历右子树.如上例中二又树可以得到前序序列为abdehicfg.后序遍历得递归算法定义：若二叉树非空，则依次执行如下操作：遍历左子树；遍历右子树；访问根结点.如上例中二叉树可以得到后序序列为dhiebfgca.例、有二叉树中序序列为ABCEFGHD，后序序列为：ABFHGEDC.请画出此二叉树，并求前序序列.根据后序序列知根节点为C因此左子树：中序序列为AB后序序列为AB右子树：中序序列为EFGHD后序序列为FHGED依次推得该二叉树的结构图.前序序列为：CBADEGFH.【练习题】一、选择题一棵非空二叉树的前序遍历序列和后序遍历序列正好相反，则该二叉树一定满足.A.所有结点均无左孩子 B所有的结点均无右孩子C.只有一个叶子结点 D是任意一棵二叉树一棵完全二叉树上有1001个结点，其中叶子结点的个数是.A.250 B.500C.254 D.505E.以上答案都不对设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为.A.k+1B.2kC.2k-l D.2k+1设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点.TOC\o"1-5"\h\zA.13 B.12C.26 D.25将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是 .A.4 B.5C.6 D.7设树T的高度为4,其中度为1、2、3和4的结点个数分别为4、2、l、1，则T中的叶子数为.A.5 B.6C.7 D.8某二叉树中序序列为abcdefg，后序序列为bdcafge，则前序序列是 .A.egfacbdB.eacbdgfC.eagcfbdD.以上答案都不对在一棵度为3的树中，度为3的结点个数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点个数为.TOC\o"1-5"\h\zA.4 B.5C.6 D.7在一棵具有K层的满三叉树中，结点总数为.A.(3k-1)/2 B.3k-lC.(3k-1)/3 D.3k满二叉树的叶结点为N，则它的结点总数为.A.NB.2NC.2N-1D.2N+1E.2 N-1二、问题解答已知，按中序遍历二叉树的结果为：abc.问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树.一棵树的前序遍历为：ABDECFGHI，中序遍历为：DBEAFCHIG，求后序遍历。4.4图图（Graph）是一种复杂的非线性结构.在人工智能、工程、数学、物理、化学、生物和计算机科学等领域中，图结构有着广泛的应用.奥林匹克信息学竞赛的许多试题，亦需要用图来描述数据元素间的联系.图G由两个集合V和E组成，记为：G=（V，E），其中：V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集.通常，也将图G的顶点集和边集分别记为V（C）和E（G）.E（G）可以是空集.若E（G）为空，则图G只有顶点而没有边.（一）有向图和无向图1有向图若图G中的每条边都是有方向的，则称G为有向图（Digraptl）.在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示.有向边也称为弧（Arc），边的始点称为弧尾（Tail），终点称为弧头（Head）.例如＜vi，七＞表示一条有向边，vi是边的始点（起点），v是边的终点.因此，＜Vi,七＞和＜七，Vi＞是两条不同的有向边.下面（a）图中G1是一个有向图.图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为：v（G1）={v1，v2，v3}E（G1）={＜V，v＞，＜v，v＞，＜v，v＞}l2 2l 2 3J2无向图若图G中的每条边都是没有方向的，则称G为无向图（Undigraph）.无向图中的边均是顶点的无序对，无序对通常用圆括号表示.例如无序对（七，七）和（v.,vi）表示同一条边.下面4-4-1（b）中的G2和图4-4-1（c）中的G3均是无向图，它们的顶点集和边集分别为：V（G2）={vl，v2，v3，v4}E（G）={（V，V），（v，v），（v，v），（v，v），（v，v），（V，V）}TOC\o"1-5"\h\zl2 1 3 l4 2 3 24 34,）V（G）={v，V，v，v，v，v，v}l2 3 4 5 6 /E（G）={（V，v），（V，v），（V，v），（v，v），（v，v），（V，V）}3 l2 l3 2 4 2 5 3 6 3 /3图G的顶点数n和边数e的关系(1若G是无向图，则O忍e忍n(n—1)/2恰有n(n—■1)/2条边的无向图称无向完全图(Undireet—edCompleteGraph)(2若G是有向图，则O^e^n(n—1).恰有n(n—1)条边的有向图称为有向完全图(DirectedCompleteGraph).注意：完全图具有最多的边数.任意一对顶点间均有边相连.例如上面图4-4-1(b)的G2就是具有4个顶点的无向完全图.图的边和顶点的关系无向边和顶点关系若(Vj,v.)是一条无向边，则称顶点vi和V.互为邻接点(Adjacent),或称vi和V.相接连；并称(Vj,v.)依附或关联(Incident)于顶点vj和v.,或称(v^v.)与顶点vi和v.相关联.例如图4-4-1(b)G2中：①与顶点vi相邻接的顶点是v,v和V；②关联于顶点V的边是(v,v),(v,v)和(v,v)2 3 4 2 1 2 23/ 2^4^2有向边和顶点关系若＜vi?v.＞是一条有向边，则称顶点vi邻接到v.,顶点vi邻接于顶点v.；并称边＜七，v.＞关联于vi和v.或称＜匕，V.〉与顶点vi和v.相关联.例如在图4-4-1(a)Gl中，关联于顶点v2的孤是＜vl，v2＞,＜v2,vi＞和＜v2，v3＞.3.顶点的度(Degree)无向图中顶点v的度(Degree)无向图中顶点v的度(Degree)是关联于该顶点的边的数目，记为D(v).例如图4-4-l(b)G2中顶点vl的度为3.(2)有向图顶点v的度(InDegree)有向图中，以顶点v为终点的边的数目称为v的人度(Indegree)，记为ID(v).例如在图4-4-l(a)G1中顶点^的入度为1.有向图中，以顶点v为始点的边的数目，称为v的出度(Outdegree),记为OD(v).例如在图4-4-1(a)Gl中顶点v2的出度为所以在有向图中，顶点v的度定义为该顶点的人度和出度之和，即D(v)=ID(v)+OD(v).例如在图4-4-1(a)G1中顶点v2的人度为l,出度为2,则度为3.从上述我们可以得知，无论有向图还是无向图，顶点数n、边数e和度数之间有如下关系:子图设G=(V,E)是一个图，若v’是V的子集，E’是E的子集，且E’中的边所关联的顶点均在V’中，则G’=(V’，E’)也是一个图，并称其为G的子图(Subgraph).例如图4-4-2(a)给出了有向图G1的若干子图；图4-4-2(b)•J m卜居1■叫给出了无向图G2的若干个子图.再比如，设V’={v〔，v2，v3}，E’={(v〔，v2)，(v2，v4)}，显然，V’属于V(G2)，E’属于E(G2)，但因为E’中序偶对(v2,v4)所关联的顶点v4不在V’中，所以(V’，E’)不是图，也就不可能是G2的子图.四)路径(Path)1无向图的路径在无向图G中，若存在一个顶点序列vp，v^’vi2，…，vim，vq，使得(vp，VC，El，vi2)，…，Em，七)均属于E(G)，则称顶点vp到vq存在一条路径(Path).2有向图的路径在有向图G中，路径也是有向的，它由E(G)中的有向边＜vp，vii＞，＜笔1，％＞，…，＜服七＞组成.3路径长度路径长度定义为该路径上边的数目.4简单路径若一条路径上除了vp和vq可以相同外，其余顶点均不相同，则称此路径为一条简单路径.例如在图G2中顶点序列vi，v2,v3,v4是一条从顶点vi到顶点v4的长度为3的简单路径.例如在图G2中，顶点序列vi，v2，v4，vi，v3是一条从顶点vi到顶点v3的长度为4的路径，但不是简单路径；5简单回路或简单环(Cycle)

起点和终点相同(vp=vq)的简单路径称为简单回路或简单环(cycle).例如图G2中，顶点序列v/v2,v4,v1是一个长度为3的简单环.例如图4-4-1中有向图G1中，顶点序列vi，v2,vi是一长度为2的有向简单环.6有根图和图的根在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根.连通图和连通分量1.顶定间的连通性在无向图G中，若从顶点v±到顶点七有路径(当然从V到匕也一定有路径)，则称七和七是连通的.2连通图若V(G)中任意两个不同的顶点v±和七都连通(即有路径)，则称G为连通图(Con-nectedGraph).例如图4-4-1中G2和G3是连通图.连通分量无向图G的极大连通子图称为G的连通分量(connectedComponent).注意：任何连通图分量只有一个，即是其自身；另外非连通的无向图有多个连通分量.例如图4-4-3中的G4是非连通图.它有两个连通分量Hl和H2.阳口14.屯向中专■丘的季if酒同匚图44-3具有两个分量的非连通图G4强连通图和强连通分量1强连通图有向图G中，若对于V(G)中任意两个不同的顶点v±和七，都存在从七到v以及从v到七的路径，则称G是强连通图. ''2强连通分量有向图的极大强连通子图称为G的强连通分量.强连通图只有一个强连通分量，即是其自身.非强连通的有向图有多个强连通分量.例如图4-4-4中的G1不是强连通图，因为v3到v2没有路径，但它有两个强连通分量，如图4-4-5所示.

A-a"r,「i璀"疑*叶屈JI： ty■o六）图的存储结构图的存储方法有很多，我们这里只介绍图的邻接矩阵表示法.在图的邻接矩阵表示法中：用邻接矩阵表示顶点间的相邻关系；用一个顺序表来存储顶点信息.设G：（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵，其规模为nXn：,r..7 [L：砒知.队例如图4-4-6中无向图G5和有向图G6的邻接矩阵分别为A1和A2.例58G是一个非连通无向图，共有28条边，则该图至少有个顶点.8个顶点的完全图共有28条边，再加一个孤立顶点使G成为非连通的.其他情况，由于点未充分利用必定多于9个.所以答案是9.（七）图的遍历给出一个图G和其中任意一个结点V0，从V0出发系统地访问G中所有结点，每一个结点被访问一次，这就叫图的遍历.遍历图的结果是按访问顺序将结点排成一个线性序列.通常有两种遍历方法：深度优先搜索和广度优先搜索，他们对

无向图和有向图都适用.1深度优先搜索深度优先搜索类似于树的前序遍历，是树的前序遍历的推广.假设初始时所有结点未曾被访问，深度优先搜索从某个结点V0出发，然后依次访问从V0的未被访问的邻接点出发深度