第3章 非线性数据结构

第3章非线性数据结构3.1树及其基本概念3.2二叉树

3.3二叉树的遍历3.4树的存储结构和遍历3.5树、森林与二叉树的转换3.6霍夫曼树及其应用3.7图及其基本概念3.8图的存储结构3.9图的遍历3.10图的连通性及最小生成树本章小节习题

老祖宗儿子孙子曾孙

定义：树是由n(n≥0)个结点组成的有限集合T。其中有且仅有一个结点称为根结点，其余结点可分为m(m≥0)个互不相交的有限集合T1，T2，……Ti

…

Tm，每个Ti本身又是一棵树，称为根结点的子树。树的定义是递归的！

基本术语

结点（node）：树中元素。

结点的度(degree)：结点拥有的子树数。树形数据结构是结点之间有分支，有层次的非线性数据结构。一棵树中最大的结点度数为树的度。张源张明张亮张丽张林张维张平张华张群张晶张磊图3-1树型结构3.1树及其基本概念

双亲（parents）：孩子结点的上层结点称为这些结点的双亲。

兄弟（sibling）：同一双亲的孩子。

结点的层次（level）：从根结点开始算起，根为第一层，根的直接后继结点为第二层，依次类推。

深度（depth）：树中结点的最大层次数。

有序树：树中结点在同一层中按从左到右有序排列，不能互换的称为有序树。

森林：m(m≥0)棵互不相交的树的集合。

孩子(child)：除根结点外，每个结点都是其前趋结点的孩子。

叶子(leaf)：度为0的结点。

在计算机中表示一棵树时，就隐含着一种确定的相对次序，所以后面我们讨论的都是有序树。3.2.1二叉树的定义及其性质二叉树是n(n≥0)个结点的有限集合，它或为空树或是由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。二叉树也是递归定义的！二叉树的特点：(1)每个结点最多有两棵子树(2)有左右之分。ABEFABEF两棵不同的二叉树3.2二叉树图3-2二叉树的五种基本形态

1二叉树的定义例3-1

画出具有3个结点的树和二叉树的所有不同形态。图3-3有3个结点的所有树的不同形态图3-43个结点的所有二叉树的不同形态

(2)图3-3有3个结点的所有树的不同形态解：(1)具有3个结点的树有2种不同的形态，如图3-3所示。注意：树和二叉树的区别主要是二叉树的结点的子树要区分左子树和右子树，即使在结点只有一个子树的情况下，也要明确指出该子树是左子树还是右子树。2二叉树的性质

性质一：二叉树的第i层上至多有2i-1(i≥1)个结点。

性质二：深度为k的二叉树上至多含有2k-1个结点。

性质三：在任意的二叉树T中，若有n0个叶子结点，n2个度为2的结点，则必有:n0=n2+1。性质三证明：综合这二者关系可得性质三另一方面，度为1的结点有1个孩子，度为2的结点有2个孩子。故二叉树中孩子结点总数为：n1+2n2，又二叉树中只有根结点不是任何结点的孩子，故总结点数为n=n1+2n2+1；设ni表示度数为i的结点，则总结点数n为：n=n0+n1+n2；

几种特殊形式的二叉树

满二叉树:深度为k的二叉树的,并且含有2k-1个结点。特点：每一层的结点数都是最大结点数图3-6深度为4的满二叉树

完全二叉树：对满二叉树的结点进行连续编号：从根结点起，自上而下逐层从左到右给每个结点编一个从1开始的顺序号。图3-6就成为图3-7。图3-7深度为4的满二叉树深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的编号从1到n的结点一一对应时，称之为完全二叉树。如图3-8所示是一棵深度为4的完全二叉树。图3-8深度为4的完全二叉树特点：(1)叶子只可能在层次最大的两层上出现。

(2)最下面一层的结点都集中在该层最左边的若干位置上。思考：深度为h的完全二叉树的结点数目不少于？2h-1

性质四：具有n个结点的完全二叉树的深度为证明：假设深度为k，则根据性质22k−1−1＜n≤2k−1或2k−1≤n＜2k于是k−1≤lbn＜k

因为k是整数所以

如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第n层，每层从左到右)，则对任一结点i(1≤i≤n)，有

(1)如果i=1，则i是二叉树的根，无双亲；如果i>1，则其双亲是结点。

(2)如果2i>n，则结点i无左孩子；否则其左孩子是2i。

(3)如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。证明从略。

性质五：

平衡二叉树特点：左子树与右子树的深度之差的绝对值不超过1，且左、右子树也都是平衡二叉树。例3-2

图3-9中有两棵二叉树，试判定其是否是平衡二叉树？图3-9两棵二叉树3.2.2二叉树的存储结构1二叉树的顺序存储结构

为实现顺序存储，必须把二叉树中所有结点按照一定的次序组成一个线性序列，使得结点在这个序列中的相互位置能反映出结点之间的逻辑关系。

对于完全二叉树，从树根起，自上层到下层，每层从左到右的给结点进行编号，就能得到一个反映整棵二叉树结构的线性序列。

对于完全二叉树，按图3-8中的编号顺序存储，就能得到一个足以反映整个二叉树结构的线性序列。将完全二叉树中所有结点按编号顺序依次存储到一组连续的存储单元(即向量)中，既不浪费内存，又可用地址公式确定其结点的位置。但对于一般的二叉树，顺序分配造成内存浪费，图3-8所示的完全二叉树，其顺序存储结构如图3-10(a)所示。

图3-8深度为4的完全二叉树图3-10二叉树的顺序存储结构在最坏情况下，一个深度为k且只有k个结点的单支树(树中无度为2的结点)却需要2k–1个存储单元。浪费很大。所以，一般用链表来表示二叉树。

2二叉树的链式存储结构二叉链表lchilddatarchild结点结构的直观形式1：链表中每个结点由数据域(data)、左指针域(lchild)及右指针(rchild)构成。这种存储结构又称为二叉链表。结点的结构1：图3-11二叉树及其二叉链表存储结构(a）ABCDEFA^BDE^^F^^C^^root(b）为便于找到结点的双亲，还可增加一个指向其双亲的指针域(parent)。由这种结点结构所得的二叉树存储结构称为三叉链表。lchilddataparentrchild结点的结构2：结点结构的直观形式2：图3-12二叉树及三叉链表存储结构(a)ABCDEF三叉链表(b)3.3二叉树的遍历

遍历二叉树就是按一定的次序，系统地访问树中的所有结点，使每个结点恰好被访问一次。所谓访问结点，其含义是很广的，可以理解为对结点的增、删、修改等各种运算的抽象。在本节讨论中，假定访问结点即为输出结点数据域值。二叉树的遍历是最重要和最基本的运算，二叉树的许多操作都是以遍历为基础的。

遍历的含义：指沿某条搜索路线，依次访问数据结构中的全部结点，而且每个结点只被访问一次。二叉树的遍历：是指依次遍历根结点、左子树及右子树。对于线性结构来说，因此只需从开始结点顺序扫描每个结点即可。但是二叉树为非线性结构，每个结点最多可有两个后继，因此必须人为设定遍历路径！以D，L，R分别表示访问根结点、遍历左子树，遍历右子树DLR，LDR，LRD，DRL，RDL，RLD排列组合{DLR，LDR，LRD

}规定先左后右三种基本遍历方法：DLR：先序遍历LDR：中序遍历LRD：后序遍历二叉链表的C语言描述如下：structtnode{ intdata; structtnode*lchild,*rchild; }typedefstructtnodeTNODE;算法3-1

先序遍历根结点指针为bt的二叉树。voidpreorder(TNODE*bt) { if(bt!=NULL) { printf(''%d\n'',bt->data); preorder(bt->lchild); preorder(bt->rchild); } }根据先序遍历的定义，先序遍历二叉树的递归算法如下：算法3-2

中序遍历根结点指针为bt的二叉树。voidinorder(TNODE*bt) { if(bt!=NULL) { inorder(bt->lchild); printf(''%d\n'',bt->data); inorder(bt->rchild); } }根据中序遍历的定义，中序遍历二叉树的递归算法如下：算法3-3

后序遍历根结点指针为bt的二叉树。voidpostorder(TNODE*bt) { if(bt!=NULL) { postorder(bt->lchild); postorder(bt->rchild); printf(''%d\n'',bt->data); }}

根据后序遍历的定义，后序遍历二叉树的递归算法如下：ABECFGD中序遍历结果：CBDAEGFLDRLDRLDRCnilnilBLDRDnilnilALDRELDRFLDRGnilnilnilnil先序遍历结果：后序遍历结果：ABCDEFGCDBGFEA下面重点以中序遍历为例，讨论二叉树的遍历算法。

算法3-4

中序遍历bt所指二叉树，s为存储二叉树结点指针的工作栈。

Step1.[初始化]置堆栈s为空，设置临时指针变量p(bt→p)；

Step2.[判定p==NULL]若p==NULL，则执行Step4；上述示例给出了中序遍历的非递归算法思路：利用一个辅助堆栈S，可以写出中序遍历二叉树的非递归算法。

Step3.[P进栈]将p指针入栈，然后置p=p->lchild，返回Step2；

Step4.[取栈顶元素，并退栈]若栈s为空，则算法结束，否则，将栈顶元素置指针变量P；

Step5.[访问结点p]访问结点P，然后置p=p->rchild，并返回Step2。

#defineNm /*m为二叉树的结点个数*/voidinorderf(TNODE*pt) { TNODE*p; TNODE*s[N]; inttop=−1;//Step1. p=bt;//Step1.

while((p!=NULL)||(top!=−1))//Step2.

如果设定栈s采用顺序存储结构，则可给出C语言描述如下。{ while(p!=NULL)//Step3.

{top++; s[top]=p; p=p->lchild;} if(top!=−1)//Step4.

{p=s[top];//Step5.

top−−; p=p->rchild;}}}

printf(''%d\n'',p->data);//先序遍历

分析此算法的运算量，假定二叉树T有n个结点，每个结点都要入栈和出栈一次。因此，入栈和出栈都要执行n次，对结点的访问当然也需执行n次。这样，中序遍历二叉树算法的时间复杂度为O(n)。

例3-4如图3-12所示的二叉树表示下述表达式：a+b*c−e/f

试写出它的三种遍历序列。

解：先序遍历二叉树，按访问结点的先后次序将结点排列起来，可得先序遍历序列为：−+a*bc/ef中序遍历序列为：

a+b*c−e/f后序遍历序列为：

abc*+ef/−

从表达式来看，以上三个序列恰好为表达式的前缀表示(波兰式)、中缀表示和后缀表示(逆波兰式)。图3-12二叉树

3.4树的存储结构和遍历

树在计算机内存储，可以用顺序存储方式、也可以用链式存储方式，这主要取决于要对树结构进行什么运算。二叉树的链式存储结构（1）从结点指针域的个数是否固定来区分：定长结点和不定长结点；树的链式分配（2）从一个结点的各指针域存放的指针值的性质来区分：指向其所有孩子的多重链表和指向长子(最左边的孩子)及次弟(右邻的兄弟)的二叉链表。

二叉链表表示法又称二叉树表示法，或孩子兄弟表示法。即以二叉链表作为树的存储结构。链表中结点的两个指针域分别指向该结点的第一个孩子和下一个兄弟结点。

1．二叉链表表示法childdatabrother图3-13是一棵树，该树的二叉链表如图3-14所示。利用这种存储结构便于实现各种树的操作，首先易于实现找结点孩子等的操作，如果再为每个结点增设一个PARENT域，则同样能方便地实现求某结点双亲的操作。二叉链表结点的直观表示：图3-13树图3-14图3-13中树的二叉链表

(2)后序遍历树：先从左到右依次后根遍历每棵子树，然后访问根结点。如后序遍历图3-13所示的树，得到的结点序列为：DGHIEBFCA。

2．树的遍历次序：先序遍历树和后序遍历树(1)先序遍历树：先访问树的根结点，然后从左到右依次先序遍历根的每棵子树。如先序遍历图3-13所示的树，得到的结点序列为：ABDEGHICF。3.5树、森林与二叉树的转换

由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。图3-15树与二叉树的对应关系

步骤：

(1)加线：亲兄弟之间加一虚连线。

(2)抹线：抹掉(除最左一个孩子外)该结点到其余孩子之间的连线。

(3)旋转：新加上去的虚线改实线且均向右斜(rchild)，原有的连线均向左斜(lchild)。1．一般树转换为二叉树

例3-5将图3-16(a)所示的一般树转换为二叉树。

解：转换过程如图3-16(a)、(b)、(c)、(d)所示(a)(b)(c)(d)加线抹线旋转图3-16一般树转换为二叉树的操作过程(a)一般树；(b)加线后；(c)抹线后；(d)旋转后

步骤：

(1)将各棵树分别转换为二叉树。

(2)按给出森林中树的次序，依次将后一棵二叉树作为前一棵二叉树根结点的右子树，则第一棵树的根结点是转换后二叉树的根。2．森林转换为二叉树森林是树的有限集合，利用树的转换思想，可以实现森林到二叉树的转换。

例3-6将图3-17(a)的森林转换成二叉树

解：转换过程如图3-17(b)、(c)所示。(a)

例3-6将图3-17(a)的森林转换成二叉树(a)森林(b)各棵数对应的二叉树(c)转换成的二叉树图3-17森林转换成对应的二叉树的过程思考：将如下二叉树转换成森林？转换结果唯一吗？

结点间的路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数称为这两个结点之间的路径长度。霍夫曼树(HuffmanTree)，又称最优树，是一类带权路径长度最短的树。1．树的路径长度和带权路径长度

树的路径长度：从树根到树中每一个结点的路径长度之和称为树的路径长度，一般记作PL。3.6霍夫曼树及其应用如图3-18所示的两棵二叉树，其路径长度分别计算如下：

(a) PL=0+1+1+2+2+2+2+3=13(b) PL=0+1+1+2+2+2+3=11

容易知道，对于有n个结点的所有二叉树而言，满二叉树或者完全二叉树具有最小的路径长度。我们把路径长度的概念推广到带权的路径长度(WeightedPathLength)。注意：只有叶子节点有权值则它们的带权路径长度分别为

(a) WPL=2*2+4*2+6*2+8*2=40(b) WPL=4*2+6*3+8*3+2*1=52(c) WPL=8*1+6*2+4*3+2*3=38

由此可见，带权路径长度最小的二叉树不一定是完全二叉树。通常，在带权路径长度最小的二叉树中，权值越大的终端结点离二叉树的根越近。

给定：一组权值{W1，W2，…，Wn}

构造：一棵有n个叶子结点的最小带权路径长度的二叉树，即霍夫曼树或者最优二叉树，相应的算法称为霍夫曼算法。2．霍夫曼树和霍夫曼编码(1)给定的权值为{W1，W2，…，Wn}，据此生成森林F={T1，T2，…，Tn}(2)在F中选取两棵根结点的权值最小和次小的二叉树作为左、右子树构造一棵新的二叉树，新二叉树根结点的权值为其左、右子树根结点的权值之和。

(3)在F中删除这两棵权值最小和次小的二叉树，同时将新生成的二叉树并入森林F中。

(4)重复(2)和(3)，直到F中只有一棵二叉树为止。例如，给定一组权值{2，7，4，8}，图3-20给出了构造相应霍夫曼树的过程。图3-20霍夫曼树的构造过程

霍夫曼树应用：信息编码，判定过程，排序过程（1）信息编码中权值可看成是某个符号出现的频率；（2）判定过程中，权值可看成是某类数据出现的频率；（3）排序过程中，权值可看成是已排好次序而待合并的序列的长度等。不等长二进制前缀编码：

在信息通信中，以字符传送为主。众所周知，字符集中的每个字符使用的频率是不等的。如果能让使用频率较高的字符的编码尽可能短，这样就可以缩短整个信息通信过程中所需传送的二进制编码序列的长度，从而达到节省通信资源的目的。

问题：设D={d1，d2，…，dn}为需要编码的字符集合。又设Wi为di在文本中出现的次数，现要求对D进行二进制编码。

解决方法：以Wi为权值构造霍夫曼树。在生成的霍夫曼树中，令所有的左分支取编码为0，令所有的右分支取编码为1，将从根结点出发到叶子结点的路径上各左、右分支的编码顺序排列就得到了该叶子结点所对应的字符的二进制前缀编码，也称为霍夫曼编码。

例给出下面一个文本：

CASTCATSSATATATASA

则有D={C，A，S，T}、W={2，7，4，5}，得到D中每个字符的二进制前缀编码为

C：110 S：111 A：0T：10霍夫曼树

可以看出，出现次数最多的字符，其编码位数最少。相应文本的编码为

110011110110010111 111010 010 0 1001110

21543图3-22无向图（1）图：是由顶点集合和顶点间关系组成，记作G=（V，R）。V为顶点集合，V={v1，v2，…，vn}。R是两个顶点之间的关系的集合。（2）无向图：当图中顶点之间关系为无序时，称为无向图。

特点：(Vi,Vj)=(Vj,Vi)，称为边。无向图记作G（V，E）。V=（v1，v2，v3，v4，v5）E={(v1,v2)，(v1,v3)，(v1,v4)，(v2,v3)，(v3,v5)}对图3-22：3.7图及其基本概念1324图3-23有向图（3）有向图：当图中顶点之间关系为有序时，称为有向图。V=（v1，v2，v3，v4）E={<v1,v2>，<v1,v3>，<v3,v4>，<v4,v1>}图中有序对<Vi,Vj>称为弧，其中Vi为弧尾(起始点)，Vj为弧头(终点)。此时<Vi,Vj>≠

<Vj,Vi>

。有向图记作G（V，A）。3.7图及其基本概念（4）子图：设有两个图GA和GB，且满足

V(GB)V(GA)E(GB)E(GA)则称GB是GA的子图。如图3-24所示。

图3-24图与子图

（5）带权图：无向图中每条边附一个对应的数（权），该图为带权图。

图3-25带权图(网)（6）路径：图中一个顶点的序列称路径。如v到v'的路径为(V=Vi0，Vi1，Vi2，…，Vin=V')，<Vi0,Vi1><Vi1,Vi2>…<Vin−1,Vin>都属于集合E。路径上弧的数目称为该路径的长度。

在无向图中，若每一对顶点之间都有路径，则称此图为连通图。在有向图中，若每一对顶点u和v之间都存在v到u及u到v的路径，则称此图为强连通图。（7）邻接点：在无向图中，如果边(u,v)∈E，则u和v互为邻结点，即u是v的邻结点，v也是u的邻结点。在有向图中，如果弧<u,v>∈E，则v是u的邻结点。称u邻接到v，或顶点v邻接自顶点u。(8)顶点的度：在无向图中，顶点的度就是和该顶点相关联的边的数目，记为TD(V)。如图3-22中，TD(V3)=3。21543图3-221324图3-23入度、出度：在有向图中，以某顶点为尾的（初始点）的弧的数目称为该顶点的出度；而以该顶点为头（终端点）的弧的数目称为该顶点的入度。图3-23中，ID(V3)=1,OD(V3)=1,TD(V3)=ID(V3)+OD(V3)=2。1324图3-233.8图的存储结构

要求：掌握邻接矩阵表示法和邻接表表示法。

需在计算机中存储：（1）图的顶点的集合；（2）顶点之间的联系，即边或弧的集合。3.8.1邻接矩阵

（1）用一维数组存放图中所有顶点的信息；（2）用一个二维数组来存放数据元素之间的关系的信息(即边或弧的集合E)。这个二维数组称之为邻接矩阵。解决办法：

邻接矩阵是表示顶点之间的邻接关系的矩阵。设G=(V，E)是有n(n≥1)个顶点的图，则G的邻接矩阵A是一个具有下列性质的n×n阶矩阵：若若若将顶点编号为1～Vtxnum，设弧上或边上无权值，则图的存储结构可以简化为用一个二维数组表示：

intadjmatrix[vtxnum][vtxnum]；

123451234512341234215431324图3-26图与邻接矩阵之间的转换借助于接矩阵，能够判定任意两个顶点之间是否有边（弧）相连，亦能求得各个顶点的度。（1）在无向图中，顶点的度是邻接矩阵中该点所在行（列）的元素之和；（2）在有向图中，顶点的出度是该顶点所在行的元素之和，顶点的入度是顶点所在列的元素之和。网的邻接矩阵可定义为：其中Wij是边(Vi,Vj)或弧<Vi,Vj>上的权值。

邻接表包括两个部分：一部分是链表；另一部分是向量。3.8.2邻接表

在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点包含了顶点Vi的所有邻接顶点。结点结构：

为便于邻接表操作，在每个单链表上附设一个头结点。头结点结构：邻接表中将每个单链表的头结点以顺序结构的形式存储，邻接表的存储结构可以用C语言描述如下：

#defineVTXUNM n

/*n为图中顶点个数的最大可能值*/structarcnode{ intadjvex; floatdata; structarcnode*nextarc;};typedefstructarcnodeARCNODE;structheadnode{ intvexdata; ARCNODE*firstarc; }adjlist[VTXUNM];/*顶点Vi的邻结点在图中的位置为整数*//*结点数据类型*//*将结点arcnode重新命名为ARCNODE*//*定义邻接表数组adjlist*/

对于图3-29中的图G4和图3-30中的图G5，其邻接表存储结构如图3-29(b)和图3-30(b)所示。图3-29有向带权图及其邻接表图3-30无向图及其邻接表

邻接表优点：容易找到任一顶点的第一个邻接点和下一个邻接点邻接表缺点：要判定任意两个顶点(Vi和Vj)之间是否有边或弧相连，则需搜索第i个或第j个链表，因此不及邻接矩阵方便。注意：（1）邻接表不惟一；（2）对于有向图，其邻接表中第i个单链表的结点个数就是此结点的出度；对于无向图，其邻接表中第i个单链表的结点个数就是此结点的度。3.9图

的

遍

历

和树的遍历类似，从图中某一顶点出发访问图中其余的顶点，使每个顶点都被访问且仅被访问一次，这个过程就叫做图的遍历(traversinggraph)。要求：能写图出的深度优先搜索和广度优先搜索的序列

同一顶点可能被访问多次，因此，在遍历图的过程中，必须记下每个已访问过的顶点。为此，设一个辅助数组visited[n]，它的初值为“假”或者零，一旦访问了顶点Vi，便置visited[i]为“真”或者为被访问时的次序号。

通常有两种遍历图的方法：（1）深度优先搜索；（2）广度优先搜索。

算法步骤：

(1)首先访问图G的指定起始点V0；

(2)从V0出发，访问一个与V0邻接的顶点W1后，再从W1出发，访问与W1邻接且未被访问过的顶点W2。从W2出发，重复上述过程，直到遇到一个所有与之邻接的顶点均被访问过的顶点为止；

1．深度优先搜索图的深度优先搜索遍历(depth-firstsearch)类似于树的先序遍历，是树的先序遍历的推广。

(3)沿着刚才访问的次序，反向回退到尚有未被访问过的邻接点的顶点，从该顶点出发，重复步骤(2)、(3)，直到所有被访问过的顶点的邻接点都已被访问过为止；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。326451987遍历结果：324916587

显然，这个遍历过程是个递归过程。在设计具体算法时，首先要确定图的存储结构，下面以邻接表为例，讨论深度优先搜索法。

例3-7连通图G6的邻接表表示如图3-31所示，以顶点V1为始点，按深度优先搜索遍历图中所有顶点，写出顶点的遍历序列。图3-31G6及其邻接表解：访问序列为：V1→V2→V4→V8→V5→V6→V3→V7。下面给出dfs的算法。算法3-5

深度优先搜索的递归算法。#defineVTXUNM n/*n为图中顶点个数的最大可能值*/structarcnode{ intadjvex; floatdata; structarcnode*nextarc; };typedefstructarcnodeARCNODE;structheadnode{ intvexdata; ARCNODE*firstarc; };structheadnodeG[VTXUNM+1];intvisited[VTXUNM+1];/*访问标志数组*/voiddfs(structheadnodeG[],intv) { ARCNODE*p; printf(''%d->'',G[v].vexdata); visited[v]=1; p=G[v].firstarc; while(p!=NULL) /*当邻接点存在时*/ { if(visited[p->adjvex]==0) dfs(G,p->adjvex);/*从第v个顶点出发进行dfs*/p=p->nextarc;}};/*找下一邻接点*/

voidtraver(structheadnodeG[]) { intv; for(v=1;v<=VTXUNM;v++) visited[v]=0; for(v=1;v<=VTXUNM;v++) ifvisited[v]==0dfs(G,v);};/*对所有顶点进行dfs*//*访问标志数组初始值为0*/算法3-6

深度优先搜索的非递归算法（不要求）。

广度优先搜索(breadth-firstsearch)类似于树的按层次遍历的过程。

2．广度优先搜索算法逻辑：从图中某顶点V0出发，在访问了V0之后依次访问V0的各个未曾被访问过的邻接点，然后分别从这些邻接点出发广度优先搜索遍历图，直至图中所有已被访问的顶点的邻接点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至所有顶点都被访问到。

具体遍历步骤如下：

(1)访问V0。

(2)从V0出发，依次访问V0的未被访问过的邻接点W1，W2，…，Wt。然后依次从W1，W2，…，Wt出发，访问各自未被访问过的邻接点。

(3)重复步骤(2)，直到所有顶点的邻接点均被访问过为止。326451987第一层次第二层次第三层次起始访问点

解：遍历序列如下：V1→V2→V3→V4→V5→V6→V7→V8

例3-8

对连通图G6，从顶点V1出发，写出顶点的广度优先遍历序列。G6

注意，在bfs算法中，若W1在W2之前访问，则W1的邻接点也将在W2的邻接点之前访问，这里蕴涵了一个排队关系。在实现算法时，需设一个队列，每访问一个顶点后将其入队，然后将队头顶点出列，去访问与它邻接的所有顶点，重复上述过程，直至队空为止。访问Vi，置标志初始化队列Vi入队队空？队头元素V出队求V的邻接点WW存在？W访问过？访问W，置标志并入队求V的下一个邻接点结束YNYNNY广度优先搜索遍历算法流程：0123456789rearV3326451987V2V6V1V4V5V9V7V8front遍历次序：由广度优先搜索遍历的逻辑可见，先访问的顶点其邻接顶点也先被访问，因此在算法中需引进一个队列保存已访问过的顶点！算法3-7

广度优先遍历算法。#defineVTXUNM nvoidbfs(structheadnodeG[],intv) {intqueue[VTXUNM]; intrear=VTXUNM−1;front=VTXUNM−1; inti; ARCNODE*p; printf(''%d->'',G[v].vexdata);visited[v]=1; rear=(rear+1)%VTXUNM; queue[rear]=v; /*访问过的顶点进队列*/ while(rear!=front) {front=(front+1)%VTXUNM; v=queue[front]; p=G[v].firstarc; while(p!=NULL){if(visited[p->adjvex]==0){ printf(''%d->'',G[p->adjvex].vexdata); visited[p->adjvex]=1; rear=(rear+1)%VTXUNM; q