信息学竞赛辅导2-2非线性结构之树图课件

数据结构

之非线性结构数据结构数组堆栈队列树图数据结构就是计算机存储、组织数据的方式。

线性结构：每一个数据元素通常只有一个前驱（除第一个元素外）和一个后驱（除最后一个元素外）。非线性结构：至少存在一个结点（数据元素）有多于一个前驱或后驱的数据结构称为非线性结构。具有特征的数据结构有两种：树、图一、树的概念1.树的定义树是n(n>0)个结点的有限集，这个集合满足以下条件：（1）有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；（2）除根外，其余的每个结点都有且仅有一个前驱；（3）除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后驱（儿子结点）；2.结点的分类结点一般分成三类：⑴根结点：没有前驱的结点。在树中有且仅有一个根结点。如上图（b）中的r；⑵分支结点：除根结点外，有后驱的结点称为分支结点。如上图（b）中的a，b，c，x，t，d，i。分支结点亦是其子树的根；⑶叶结点：没有后驱的结点称为树叶。如上图（b）中的w，h，e，f，s，m，o，n，j，u为叶结点。由树的定义可知，树叶本身也是其父结点的子树。

根结点到每一个分支结点或叶结点的路径是唯一的。例如上图（b）中，从根r到结点i的唯一路径为rcti。

3.有关度的定义⑴结点的度：一个结点的子树数目称为该结点的度。在上图（b）中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。

⑵树的度：所有结点中最大的度称为该树的度。图（b）中的树的度为3。

4.树的深度（高度）树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的后件在第二层，其余各层依次类推。即若某个结点在第k层，则该结点的后件均处在第k+1层。图（b）中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。图（b）中树的深度为5。

5.森林所谓森林，是指若干棵互不相交的树的集合。如图（b）去掉根结点r，其原来的三棵子树Ta，Tb，Tc的集合{Ta，Tb，Tc}就为森林，这三棵子树的具体形态如图（c）。

6.有序树和无序树按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。⑵动态的多重链表

由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n为树的度)个指针域共n+1个域组成，其表示方法如下：

Constn=树的度；

Typetreetype=↑node；

node=recorddata：datatype；{数据域}next：array[1‥n]oftreetype；{指向各儿子的指针域}end；

Varroot：treetype；二叉树的概念

二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后件，且其子树有左右之分（次序不能任意颠倒）。1.二叉树的递归定义和基本形态

二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：（1）有一个特定的结点称为根；（2）余下的结点分为互不相交的子集L和R，其中R是根的左子树；L是根的右子树；L和R又是二叉树；由上述定义可以看出，二叉树和树是两个不同的概念（1）树的每一个结点可以有任意多个后件，而二叉树中每个结点的后件不能超过2；（2）树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。

二叉树与树的不同二叉树的五种基本形态

2.二叉树的两个特殊形态⑴满二叉树：如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。（例如图(a)）可以验证具有n个叶结点的满二叉树共有2n-1个结点。⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如图(b)）2.二叉树的两个特殊形态⑴满二叉树：

如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。（例如图(a)）可以验证具有n个叶结点的满二叉树共有2n-1个结点。⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如图(b)）3.二叉树的三个主要性质

性质1：在二叉树的第i（≥1）层上，最多有2i-1个结点证明?采用数学归纳法证明：当i=1时只有一个根结点，即2i-1=20=1，结论成立。假设第k(i=k)层上最多有2k-1个结点，考虑i=k+1。由归纳假设，在二叉树第k层上最多有2k-1个结点，而每一个结点最多有两个子结点。因此在第k+1层上最多有2×2k-1=2(k+1)-1=2i，结论成立。综上所述，性质1成立。性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。证明：设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然n=n0+n1+n2（1）由于二叉树中除了根结点外，其余每个结点都有且仅有一个前件。设b为二叉树的前件个数，n=b+1（2）所有这些前件同时又为度为1和度为2的结点的后件。因此又有b=n1+2n2(3)除v0没有前件外，v1、v2、v3、v4、v5都有一个前件，b=5。而v1和v2为v0的后件，v3为v1的后件，v4和v5为v2的后件，因此b=b=n1+2n2=1+2*2=5。我们将（3）代入（2）得出n=n1+2n2+1(4)比较（1）和（4），得出n0=n2+1,即叶子数比度为2的结点数多1二叉树的存储结构将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括⑴一个数据域（data）；⑵三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。满二叉树和完全二叉树一般采用顺序存储结构

Constm=树中结点数上限；

Typenode=record{结点类型}data：datatype；{数据值}prt，lch，rch：0‥m；{父结点、左儿子、右儿子编号}end；

treetype=array[1‥m]ofnode；{二叉树的顺序表类型}VarTree：treetype；{二叉树}

二叉树的遍历1、二叉树的遍历二叉树遍历的定义：按照一定的规律不重复地访问(或取出结点中的信息，或对结点作其它的处理)二叉树中的每一个结点。二叉树遍历的顺序：如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、LRD、DLR、DRL、RDL、RLD。若再限定先左后右的次序，则只剩下三种组合：LDR（中序遍历）、LRD（后序遍历）、DLR（前序遍历）。⑴前序遍历前序遍历的规则如下：若二叉树为空，则退出。否则⑴访问处理根结点；⑵前序遍历左子树；⑶前序遍历右子树；前序序列：abdehicfg特点：由左而右逐条访问由根出发的树支（回溯法的基础）⑵中序遍历中序遍历的规则：若二叉树为空，则退出；否则⑴中序遍历左子树；⑵访问处理根结点；⑶中序遍历右子树；中序序列：dbheiafcg

⑶后序遍历后序遍历的规则如下：若二叉树为空，则退出；否则⑴后序遍历左子树；⑵后序遍历右子树；⑶访问处理根结点；

后序序列：dhiebfgca特点：可统计任一个结点为根的子树的情况（例如子树的权和，最优策略的选择（博弈数））2、普遍有序树的遍历

⑴先根次序遍历树规则：若树为空，则退出；否则先根访问树的根结点，然后先根遍历根的每棵子树

先根序列：rawxdhebfcstimonju当普遍有序树转化为二叉树时，可借用二叉树的前序遍历实现普遍有序树的先根遍历。⑵后根次序遍历树规则：若树为空，则退出；否则先依次后根遍历每棵子树，然后访问根结点。当普遍有序树转化为二叉树时，可借用二叉树的中序遍历实现普遍有序树的后根遍历。后根序列：

whdexafbsmonijtucr

按照先根次序和后根次序遍历普遍有序树

输入一棵普通有序树，输出该树的先根次序和后根次序。输入：顶点个数n（1≤n≤200）以下含n行，其中第i行（1≤i≤n）的元素依次为结点i的数据值ai。以后各元素为结点i的儿子序列，以0结束。若ai后仅含一个0，则说明结点i为叶子。对应的输入信息为18’r’2340’a’560’b’70’c’89100’w’0’x’11120’f’0’s’13140’t’000’u’0’’d’150’e’0’i’1617180’j’0’h’0’m’0’o’0’h’0fillchar（tree，sizeof（tree），0）；{二叉树初始化}readln(n)；{读入普通有序树的结点个数}fori←1tondo{依次读入普通有序树中每个结点的信息}beginread(tree[i]．data)；

read(j)；{读结点i的第一个儿子序号j}

ifj<>0then{若结点j非叶子}begintree[i]．lch←j；tree[j]．prt←i；{结点j作为结点i的左儿子}p←j；{从结点j出发转换其它兄弟结点}repeat

read(j)；{读结点i的下一个儿子序号j}ifj<>0thenbegintree[p]．rch←j；tree[j]．prt←p；{结点j作为结点p的右儿子}p←j；

end；{then}untilj=0；{直至处理完结点i的所有儿子信息}end；{then}writeln；{准备输入结点i+1的儿子信息}end；{for}

Dataprtlchrch1’r’0202’a’1533’b’2744’c’3805’w’2066’x’51107’f’3008’s’4099’t’801010’u’90011’d’6151212’e’110013’i’8161414’j’130015’h’110016’m’1301717’o’1601818’n’1700主程序输入普通有序树并转换成二叉树tree；preorder(1)；{对二叉树tree进行前序遍历}inorder(1)；{对二叉树tree进行中序遍历}

根据两种遍历顺序确定树结构

遍历二叉树有三种规则：

前序遍历：根—左子树—右子树；

中序遍历：左子树—根—右子树；

后序遍历：左子树—右子树—根；

由于前序遍历的第一个字符和后序遍历的最后一个字符为根，中序遍历中位于根左方的子串和位于根右方的子串分别反映了左子树和右子树的结构，因此二叉树的形态可以由其中序与后序或者前序与中序唯一确定。但无法反映左子树和右子树结构的前序遍历与后序遍历却不能做到这一点，因此这两个遍历顺序可对应多种二叉树的形态。

由二叉树的中序遍历顺序与后序遍历顺序确定前序遍历顺序

由二叉树的遍历规则可以看出，后序遍历的最后一个字符为根，中序遍历中位于该字符左侧的子串为左子树中序遍历的结果；中序遍历中位于该字符右侧的子串为右子树中序遍历的结果。设中序遍历s’=s1’…sk’…sn’

后序遍历s”=s1”……sn”

显然，后序遍历中的sn”为二叉树的根。按照前序遍历的规则输出sn”。在中序遍历中与sn”相同的字符为sk’。若k>1，说明左子树存在，位于sk’左侧的子串s1’…sk-1’为左子树中序遍历的结果，后序遍历中的前缀s1”…sk-1”为左子树后序遍历的结果；若k<n，说明右子树存在，位于sk’右侧的子串为右子树中序遍历的结果；后序遍历中的sk”…sn-1”为右子树后序遍历的结果。按照按照前序遍历的规则分别递归二叉树的左子树和右子树。

中序遍历s’=’dbeafc’

后序遍历s”=’debfca’

对应的前序遍历为s=’abdecf’。proceduresolve1(s1，s2:string)；{计算和输出中序遍历s1和后序遍历s2对应的前序遍历}vark:integer；beginiflength(s2)=1{若当前子树仅剩一个节点，则输出}then输出s2elsebegink←pos(s2[length(s2)]，s1)；{在中序遍历中寻找子树根}

输出子树根s1[k]；

ifk>1{若左子树存在，则递归遍历左子树}thensolve1(copy(s1，1，k-1)，copy(s2，1，k-1))；

ifk<length(s1){若右子树存在，则递归遍历右子树}thensolve1(copy(s1，k+1，length(s1)-k)，copy(s2，k，length(s2)-k))；

end；{else}end；{solve1}由二叉树的中序遍历顺序与前序遍历顺序确定后序遍历顺序设

predstr=’abcd’midstr=’bcad’

前序遍历的首字符是树的根例如上述前序序列中的’a’。我们根据该字符在中序序列中的位置i将中序序列一分为二，左端序列(即第1～i-1个字符)为左子树中序遍历的结果，例如上述中序序列中的’bc’；右端序列(即第i+1个字符～尾字符)为右子树中序遍历的结果，例如上述中序序列中的’d’；前序序列的第2～i个字符为左子树的前序遍历的结果，例如上述前序遍历中的’bc’；前序序列的第i+1至尾部的字符为右子树前序遍历的结果。例如上述前序遍历中的’d’。再运用上述方法继续分别求解左子树和右子树。如此反复，直至对应的二叉树求出为止。显然，这一求解过程是递归的。根据上述思想，我们设计一个递归过程solve2。该过程输入的值参为前序序列s2和中序序列s1两个字串，计算和输出s1和s2对应的后序遍历。proceduresolve2(s1，s2:string)；{计算和输出中序遍历s1和前序遍历s2对应的后序遍历}vark:integer；beginiflength(s2)=1{若当前子树仅剩一个节点，则输出}then输出s2elsebegink←pos(s2[1]，s1)；{在中序遍历中寻找子树根} ifk>1{若左子树存在，则递归遍历左子树}thensolve2(copy(s1，1，k-1)，copy(s2，2，k-1))；

ifk<length(s1){若右子树存在，则递归遍历右子树} thensolve2(copy(s1，k+1，length(s1)-k)，copy(s2，k+1，length(s2)-k))；

end；{else}

输出子树根s1[k]（或者输出子树根s2[1]）；

最优二叉树

全校学生的成绩由百分制转换成五等分制，在五个等次以上的分布不均匀，分布规律如下表：百分制分数范围0～5960～6970～7980～8990～100分布情况%515403010现有10000个数据。下图分别列出两种判定转化过程：

若按照上图(a)的判定过程进行转换，则有80%的数据至少要进行3次比较才能得出结果。完成10000个数据转换的比较次数k=10000*（1*5%+2*15%+3*40%+4*(30%+10%)）=31500次。若按照上图(b)的判定过程进行转换，则有20%的数据需要进行3次比较才能得出结果，而有80%的数据至多仅需要进行2次比较就可得出结果。完成10000个数据转换的比较次数k=10000*（2*（10%+30%+40%）+3*（5%+15%））=22000次现在的问题是，如果给出n（1≤n≤1000000）个学生的百分制成绩，要将它们转换成五分制成绩，至少要经过多少次比较。其中每个等次成绩的最少比较多少次输入：n和w1w2w3w4w5(五个等次的成绩分布规律)输出：最少比较次数和5个整数，分别为每个等次成绩的最少比较次数最优二叉树的定义在具有n个带权叶结点的二叉树中，使所有叶结点的带权路径长度之和（即二叉树的带权路径长度）为最小的二叉树，称为最优二叉树（又称最优搜索树或哈夫曼树），即最优二叉树使

（wk—第k个叶结点的权值；pk—第k个叶结点的带权路径长度）达到最小。例如下图为三棵二叉树，它们都有5个叶结点a、b、c、d，e其权值分别为7、5、2、4、6。(b)所示的二叉树的带权路径长度和最小，为最优二叉树。

最优二叉树的构造方法

假定给出n个结点ki(i=1‥n)，其权值分别为wi(i=1‥n)。要构造以此n个结点为叶结点的最优二叉树，其构造方法如下：首先，将给定的n个结点构成n棵二叉树的集合F={T1，T2，……，Tn}。其中每棵二叉树Ti中只有一个权值为wi的根结点ki，其左、右子树均为空。然后做以下两步⑴在F中选取根结点权值最小的两棵二叉树作为左右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和；⑵在F中删除这两棵二叉树，同时将新得到的二叉树加入F中；重复⑴、⑵，直到在F中只含有一棵二叉树为止。这棵二叉树便是最优二叉树。例如：给定五个结点k1，k2，k3，k4，k5，其权值分别为16、2、18、16、23。构造最优二叉树的过程如下：最优二叉树的数据类型定义

在最优二叉树中非叶结点的度均为2，为满二叉树，因此采用顺序存储结构为宜。如果带权叶结点数为n个，则最优二叉树的结点数为2n-1个。Constn=叶结点数的上限；

m=2*n-1；{最优二叉树的结点数}Typenode=record{结点类型}data：integer；{权值}prt，lch，rch,lth：0‥m；{父指针、左、右指针和路径长度}end；

wtype=array[1‥n]ofinteger；{n个叶结点权值的类型}treetype=array[1‥m]ofnode；{最优二叉树的数组类型}Vartree：treetype；{其中tree[1‥n]为叶结点，tree[n+1‥2n-1]为中间结点，根为tree[2n-1]}

构造最优二叉树的算法procedurehufm(w：wtype；vartree：treetype；varbt：integer)；

functionmin(h：integer)：integer；{在前h个结点中选择父指针为0且权值最小的结点min}beginml←∞；

forp←1tohdoif(tree[p]．prt=0)and(m1>tree[p]．data)thenbegini←p；m1←tree[p]．data；

end；{then}min←i；

end；{min}

beginfillchar(tree，sizeof(tree)，0)；{构造初始集合F}fori←1tondoread(tree[i]．Data)；

fork←n+1tomdo{构造最优二叉树}begin{计算k为根的左儿子和右儿子}i←min(k-1)；

tree[i]．prt←k；

tree[k]．lch←i；

j←min(k-1)；tree[j]．prt←k；tree[k]．rch←j；

tree[k]．data←tree[i]．data+tree[j]．data；end；{for}bt←m；

end；{hufm}计算每一个叶结点的路径长度procedureht(t:integer);{通过前序遍历计算每一个叶结点的路径长度}beginift=m{若结点t为根，则路径长度为0；否则结点t的路径长度为其父结点的路径长度+1}thentree[t].lth←0elsetree[t].lth←tree[tree[t].prt].lth+1；iftree[t].lch<>0thenbeginht(tree[t].lch)；ht(tree[t].rch)；end；{then}{分别递归左右子树}end；{ht}由此可见，叶结点t（1≤t≤5）的带权路径长度即为tree[t].lth*tree[t].data。

题解readln(n)；{输入要求转换的百分制成绩数}fori←1to5doreadln(wi)；{输入五个等次的成绩分布规律}hufm(w，tree，bt)；{计算最优二叉树tree和根序号bt}ht(bt)；{计算每个等次成绩的比较次数}writeln(n*tree[bt].data)；{输出n个数据的最少比较次数}fori←1to5dowriten*tree[i].lth*tree[i].data）；{输出每个等次成绩的比较次数}题1：计算最近公共祖先输入二叉树的两个顶点，输出它们的最近公共祖先。输入:顶点数n及其根rt(1≤n≤1000)以下n行，其中第I行为顶点I的左右儿子序号

ab输出:a和b的最近公共祖先算法分析

首先从顶点a出发，沿父指针将a至根的路径上的所有顶点设访问标志。然后从b顶点出发，沿父指针追溯到第1个已访问的顶点b，该顶点即为a和b的最近公共祖先。设constmax=1000;varn,rt,a,b,i:integer;{顶点数为n，根为rt}l,r,pt:array[0..max]ofinteger;{左儿子序列、右儿子序列和父指针序列，其中顶点I的左儿子为l[i]、右儿子为r[i]、父指针为pt[i]}vt:array[1..max]ofboolean;{访问序列，其中vt[i]为顶点I的访问标志}readln(f,n,rt);{输入顶点数及其根}fori:=1tondobeginreadln(l[i],r[i]);{输入顶点I的左右儿子}ifi=rtthenpt[rt]:=0elsept[l[i]]:=i;pt[r[i]]:=iend;readln(a,b);{输入两个顶点}whilea*b<>0do{反复计算，直至终止标志}beginfillchar(vt,sizeof(vt),0);{将a至根的路径上的所有顶点设访问标志}repeatvt[a]:=true;a:=pt[a]untila=0;whilenotvt[b]dob:=pt[b];{从b顶点出发，沿父指针追溯第1个已访问的顶点b，该顶点即为a和b的最近公共祖先}writeln(b);图论基础

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

⑴无向图：在图G=（V，E）中，如果对于任意的a，b∈V，当(a，b)∈E时，必有（b，a）∈E（即关系R对称），对称此图为无向图。在一无向图中用不带箭头的边连接两个有关联的结点。在具有n个结点的无向图中，边的最大数目为：而边数达到最大值的图称为无向完全图。在无向图中一个结点相连的边数称为该结点的度。

图(A)V={1,2,3,4}E={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}⑵有向图：如果对于任意的a，b∈V，当(a，b)∈E时，(b，a)∈E未必成立，则称此图为有向图。在有向图中，通常用带箭头的边连接两个有关联的结点（方向由前件指向后件）。例如图（b）为有向图。有向图中一个结点的后件个数称为该结点的出度，其前件个数称为该结点的入度。一个结点的入度和出度之和称为该结点的度。图中结点的最大度数称为图的度。例如下图(b)）中结点1的出度和入度分别为1，结点1和结点1度都为2。整个图的度为2。

图(B)V={1,2,3}E={<1,2>,<2,1>,<2,3>}１、

路径和连通集在图G=（V，E）中，如果对于结点a，b，存在满足下述条件的结点序列x1……xk(k>1)

⑴x1=a，xk=b

⑵(xi，xi+1)∈Ei=1‥k-1则称结点序列x1=a，x2，…，xk=b为结点a到结点b的一条路径，而路径上边的数目k-1称为该路径的长度，并称结点集合{x1，…，xk}为连通集。{V1,v2,v5,v4}2、简单路径和回路如果一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同，则称此路径为一条简单路径。图(a)中v1→v2→v3是一条简单路径，v1→v3→v4→v1→v3不是简单路径。x1=xk的简单路径称为回路（也称为环）。例如图(b)中，v1→v2→v1为一条回路。二、图的存储结构图的相邻矩阵表示法相邻矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的相邻矩阵是如下定义的二维数组a，其规模为n*ntypemaxn=顶点数的上限；vara：array[1..maxn，1..maxn]ofinteger；

f：arrayarray[1..maxn]ofboolean；{顶点的访问标志序列}上图中的图G1和图G2对应的相邻矩阵分别为：01110

10111

11010

11101

01010相邻矩阵的特点：1)无向图的相邻矩阵是对称的，而有向图则不是。

2)相邻矩阵方便度数的计算。用相邻矩阵表示图:

(1)容易判定任意两个结点之间是否有边相联;

(2)并容易求得各个结点的度数。

(对于无权无向图的相邻矩阵，第i行元素值的和就是Vi的度数；对于无权有向图的相邻矩阵，第i行元素值的和就是Vi的出度，第i列元素值的和就是Vi的入度；)对于有权无向图的相邻矩阵，第i行（或第i列）中元素值<>0的元素个数就是Vi的度数；对于有权有向图的相邻矩阵，第i行中元素值<>0的元素个数就是Vi的出度；第i列元素值<>0的元素个数就是Vi的入度。三、图的遍历给出一个图G和其中任意一个结点V0，从V0出发系统地访问G中所有结点，每一个结点被访问一次，这就叫图的遍历。

通常有两种遍历方法：⑴深度优先搜索dfs⑵广度优先搜索bfs

它们对无向图和有向图都适用。我们以相邻矩阵存储结构给出深度优先搜索和广度优先搜索的程序。1、深度优先搜索DFS

深度优先搜索类似于树的前序遍历，是树的前序遍历的推广。其搜索过程如下：假设初始时所有结点未曾被访问。深度优先搜索从某个结点V0出发，访问此结点。然后依次从V0的未被访问的邻接点出发深度优先遍历图，直至图中所有和V0有路径相连的结点都被访问到。若此时图中尚有结点未被访问，则另选一个未曾访问的结点作起始点，重复上述过程，直至图中所有结点都被访问为止。换句话说，深度优先搜索遍历图的过程是以V0为起始点，由左而右，依次访问由V0出发的每条路径。调用一次dfs(i)，可按深度优先搜索的顺序访问处理结点i所在的连通分支（或强连通分支），dfs(i)的时间复杂度为W（n2）。整个图按深度优先搜索顺序遍历的过程如下：2、广度优先搜索(宽度优先搜索）BFS

广度优先搜索类似于树的按层次遍历的过程，其搜索过程如下：假设从图中某结点v0出发，在访问了v0之后依次访问v0的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到。若此时图中尚有结点未被访问，则任选其中的一个作起始点，重复上述过程，直至图中所有结点都被访问到为止。换句话说，按广度优先顺序搜索遍历图的过程是以v0为起始点，由近及远，依次访问和v0有路径相连且路径长度为1，2，3……的结点。bfs(i)的时间复杂度为W（n2）。调用一次bfs(i)可按广度优先搜索的顺序访问处理结点i所在的连通分支（或强连通分支）。整个图按广度优先搜索顺序遍历的过程如下： 1、写出图的深度优先搜索(DFS)算法和广度优先搜索(BFS)算法。programdfsbfs(input,output);constn=8;vara:array[1..n,1..n]ofinteger;{图的邻接矩阵}visited,come:array[1..n]ofinteger;{访问标志}queue:array[1..n]ofinteger;{队列}t:array[1..n]ofchar;{结点信息}i,head,tail:integer;procedureinit;vari,j,e,k:integer;beginfori:=1tondoread(t[i]);{顶点信息}fillchar(a,sizeof(a),0);read(e);{边数}fork:=1toedo{读入边的点信息,建立邻接矩阵}beginread(i,j);a[i,j]:=1;a[j,i]:=1;end;end;proceduredfs(i:integer);varj:integer;beginwrite(t[i]);{输出结点信息}visited[i]:=1;{访问标志}forj:=1tondo{深度优先搜索i的邻接点}if(a[i,j]=1)and(visited[j]=0)thendfs(j);end;四、图的应用1、拓扑排序［士兵排队］

有n个士兵（<100），编号依次为1，2，3。。。。n，排队训练，现在指挥官要把这些士兵从高到矮依次排成行，但现在指挥官不能直接获得每个人的身高信息，只能获得”i比j高“这样的比较结果输入：第一行为一个整数n，表示士兵的个数，以下若干行，每行两个数i,j：表示i比j高。输出：一种合法的排队序列样例：输入：4122343输出：1243建立有向图，如果i比j高，建立一条由i指向j的有向边．J的入度加１．先找一个入度为０的结点，即没有比他高的结点输出，去掉该结点，同时把比他矮的结点的入度减１．再找入度为０的结点，依次类推．直到最后输出完毕．１２３４拓扑排序算法寻找入度为0的节点将找到的节点放入队列中，删除所有这个节点引出的边重复1，直至没有度为0的节点如果有节点不在队列中，则说明原图中有环，否则无环。12536473、生成树问题无向图的最小生成树（贪心思想）Prim算法，适用于点少的图K