基本数据结构14图a

1、讲师：尹成QQ:77025077博客:http:/ 传智播客传智播客http:/高薪就业高薪就业第2页上堂课内容回顾上堂课内容回顾特点：特点：“左小右大左小右大”，中序遍历可得从小到大顺序，中序遍历可得从小到大顺序搜索：同子树根结点比较，同找到，小向左，大向右！搜索：同子树根结点比较，同找到，小向左，大向右！插入：搜索父结点（相应子树空）插入：搜索父结点（相应子树空）,小插左，大插右！小插左，大插右！删除：无左子树，右子树替代删除结点删除：无左子树，右子树替代删除结点 有左子树，有左子树，(1)左子树替代删除结点，右子树左子树替代删除结点，右子树接到左子树最右下结点。（接到左子树最右下结点。（

2、2）改进：左子树最右下）改进：左子树最右下结点结点t替代删除结点，并将替代删除结点，并将t的左子树挂到其父节点的的左子树挂到其父节点的右子树上。右子树上。452453122890第3页(1) (1) 哈夫曼树是：哈夫曼树是：WPL WPL 最小的树。最小的树。WPL = WPL = wklk wklk k=1k=1n n(2) Huffman(2) Huffman算法的思路：算法的思路：权值大的结点用短路径，权值小的结点用长路径。权值大的结点用短路径，权值小的结点用长路径。(3)(3)构造构造HuffmanHuffman树的步骤：对权值的合并、删除与替换树的步骤：对权值的合并、删除与替换(4)

3、 Huffman(4) Huffman编码规则：左编码规则：左“0” “0” 右右“1”“1”，是一种前，是一种前缀码缀码也称为最小冗余编码、紧致码等，它是数据压缩学的也称为最小冗余编码、紧致码等，它是数据压缩学的基础。基础。第4页哈夫曼树相关算法哈夫曼树相关算法1. 1. 建立建立huffmanhuffman树：树：结点信息、父结点指针、权值、左右孩子指针。结点信息、父结点指针、权值、左右孩子指针。对权值的合并、删除与替换对权值的合并、删除与替换3. Huffman3. Huffman译码译码 2. Huffman2. Huffman编码：编码： 左左“0” “0” 右右“1”“1”，从叶子

4、结点开始，从叶子结点开始， Huffman Huffman编码是一种前缀码也称为最小冗余编码、紧致码，等编码是一种前缀码也称为最小冗余编码、紧致码，等等，它是数据压缩学的基础。等，它是数据压缩学的基础。看实际程序注解和演示！看实际程序注解和演示！第5页建立哈夫曼树建立哈夫曼树eleparent weightlchildrchild前面 n个，原始数据（n个子树）后面 n1个，新生成子树typedef char datatype;typedef struct node datatype name; folat weight; int parent, lchild, rchild; huftree

5、;整个哈夫曼树的存储结构：整个哈夫曼树的存储结构：2n-1个结点构成的静态链表个结点构成的静态链表下标0 122nnameabweight0.10.2parent000Lchild000rchild000第6页建树主要步骤：建树主要步骤：1. 2n-1 个结点初始化；2. 结点的合并，形成haffman树3. 注意：无删除与替换操作，原结点保留第7页初始状态（上）初始状态（上） 与最终状态（下）与最终状态（下） P210第8页初始状态（左）初始状态（左） 与最终状态（右）与最终状态（右）第9页 /*数据初始化* m=2*n-1; /总共需要的空间 HT=(HuffmanTree)malloc(

6、m+1)*sizeof(HTNode); /分配空间 /for(p=*HT,i=1;i=n;+p,+w) *p=wi-1.elem,wi-1. weight,0,0,0; for(i=1;i=n;+i) /结点、权值和指针初始化 HTi.elem=wi-1.elem; HTi.m_weight=wi-1.m_weight; HTi.parent=HTi.lchild=HTi.rchild=0; for( ;i=m;+i) /空结点初始化 隐含i初值n1 HTi.elem=0; HTi.m_weight=HTi.parent=HTi.lchild=HTi.rchild=0; 第10页 /*建立哈

7、夫曼树* for(i=n+1;i=m;+i) Select(*HT,i-1,&s1,&s2); /在HT1.i-1中选择parent为0且weight最小的两个结点，其序号分别为s1和s2/注意此处i是变化的，也就是HT数组中参与比较到的结点不断增多 HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.m_weight=HTs1.m_weight+HTs2.m_weight; /两结点权值相加新结点权值 合并合并第11页哈夫曼编哈夫曼编码码1. 找到n个结点的父结点2. 从父节点开始到叶子的路径记录下来就是编码，左0右

8、1, 注意是逆向编码，自底向上编码表的存储结编码表的存储结构构1. 静态顺序存储 2. 动态链式存储第12页 静态顺序存储typedef struct cnode char bitsleafnum+1; /编码字串，最大深度为叶子结点数目 int start; /记录起始点 char ch; /字符名称 hufcode;结构简单但浪费空间第13页 动态链式存储typedef char * huffmancode;HC= (HuffmanCode) malloc(n*sizeof(char*);HCi= (char *)malloc(n-start)*sizeof(char); 结构复杂但节约空

9、间huffmancode HC第14页 /*哈夫曼树编码* (*HC)=(HuffmanCode)malloc(n*sizeof(char*); /分配编码空间数组 char* HuffmanCode cd=(char *)malloc(n*sizeof(char); /分配求编码的工作空间 cdn-1=0; /编码结束符号 for(i=1;i=n;+i) /逐个字符求哈夫曼编码 start=n-1; /编码结束符位置 for(c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent) /从叶子到根逆向求编码 if(HTf.lchild=c) cd-start=0;

10、 else cd-start=1; (*HC)i= (char *)malloc(n-start)*sizeof(char); /为第i个字符分配编码空间 strcpy(*HC)i,&cdstart); 第15页c=i;f=HTi.parent; /从叶子到根逆向求编码while(f!=0) if(HTf.lchild=c) cd-start=0; /左0右1 else cd-start=1; c=f; f=HTf.parent;for(c=i,f=HTi.parent ; f!=0; c=f,f=HTf.parent)第16页哈夫曼译哈夫曼译码码1. 从根结点开始依次根据编码0或1向下搜索2

11、. 到达根结点，提取根结点的字符3. 继续下一个循环第17页2 23 35 56 6111110107 73232171728282121191940406060100100b bc ca ad de eg gf fh h0 00 00 00 00 01 11 11 11 11 11 11 10 00 000 bchg第18页例例3:3:设字符集为设字符集为2626个英文字母，其出现频度如下表所示。个英文字母，其出现频度如下表所示。注：若圆满实现了此方案，平时成绩奖励注：若圆满实现了此方案，平时成绩奖励5分！分！51481156357203251频度频度zyxwvu字符字符1161188238

12、0频度频度p21fq15gr47hsonmlkj字符字符5710332221364186频度频度idcba字符字符先建哈夫曼树，再利用此树对报文先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。进行编码和译码。要求编程实现要求编程实现：提示：为了避免在编程调试过程中输入数据过于麻烦，可采用文提示：为了避免在编程调试过程中输入数据过于麻烦，可采用文件存储编码字符及其权重，每次读入即可，或直接用数组存储。件存储编码字符及其权重，每次读入即可，或直接用数组存储。第19页1 1、定义和性质、定义和性质2 2、存储结构、存储结构3 3、遍历、遍历4

13、4、线索化：线索树、线索化：线索树顺序结构顺序结构链式结构链式结构二叉链表二叉链表三叉链表三叉链表先序线索树先序线索树中序线索树中序线索树后序线索树后序线索树先先序序遍遍历历中中序序遍遍历历遍历遍历存储结构存储结构遍历遍历双亲表示双亲表示孩子表示孩子表示孩子兄弟孩子兄弟先序遍历先序遍历后序遍历后序遍历中序遍历中序遍历后序遍历后序遍历先序遍历先序遍历哈夫曼树哈夫曼树哈夫曼编码哈夫曼编码二叉排序树二叉排序树查找插入删除查找插入删除第20页数据结构课程的内容数据结构课程的内容多对多多对多（m:n)第21页7.1 7.1 基本术语基本术语7.2 7.2 存储结构存储结构7.3 7.3 图的遍历图的遍历

14、7.4 7.4 图的其他运算图的其他运算7.5 7.5 图的应用图的应用第22页图：记为图：记为 G G( V, E ) ( V, E ) 其中：其中：V V 是是G G的顶点集合，是有穷非空集；的顶点集合，是有穷非空集； E E 是是G G的边集合，是有的边集合，是有穷集。穷集。问：当问：当E(G)E(G)为空时，图为空时，图G G存在否？存在否？答：还存在！但此时图答：还存在！但此时图G G只有顶点而没有边。只有顶点而没有边。有向图：有向图：无向图：无向图：完全图：完全图：图图G G中的每条边都是有方向的；中的每条边都是有方向的；图图G G中的每条边都是无方向的；中的每条边都是无方向的；图

15、图G G任意两个顶点都有一条边相连接；任意两个顶点都有一条边相连接；V=vertex E=edge第23页证明：第24页例：判断下列例：判断下列4 4种图形各属什么类型？种图形各属什么类型？无向无向无向图无向图(树树)有向图有向图有向有向G1G1的顶点集合为的顶点集合为V(G1)=0,1,2,3V(G1)=0,1,2,3边集合为边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)完全图完全图完全图完全图第25页稀疏图：边较少的图。通常边数n2子 图：设有两个图 G(V, E)

16、 和 G(V, E)。若 V V 且 E E, 则称 图G 是 图G 的子图。稠密图：边很多的图。无向图中，边数接近n(n-1)/2 ； 有向图中，边数接近n(n-1) 带权图：即边上带权的图。其中权是指每条边可以标带权图：即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。上具有某种含义的数值（即与边相关的数）。网网 络：络： 带权图带权图第26页简单路径：路径上各顶点路径上各顶点 v1,v2,.,vm v1,v2,.,vm 均不互相重复。均不互相重复。回 路：例：例：若路径上第一个顶点若路径上第一个顶点 v1 v1 与最后一个顶点与最后一个顶点vm vm 重合重合

17、，则称这样的路径为回路或环。，则称这样的路径为回路或环。路径：路径长度：第27页例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5(路径上结点数-1)简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1第28页弧头和弧尾：有向边(u, v)称为弧，边的始点u叫弧尾，终点v叫弧头 顶点顶点v的度是与它相关联的边的条数。记作的度是与它相关联的边的条数。记作TD(v)。 在有向图中在有向图中, 顶点的度等于该顶

18、点的入度与出度之和。顶点的度等于该顶点的入度与出度之和。 顶点顶点 v 的入度是以的入度是以 v 为终点的有向边的条数为终点的有向边的条数, 记作记作 ID(v); 顶点顶点 v 的出度是以的出度是以 v 为始点的有向边的条数为始点的有向边的条数, 记作记作 OD(v)。邻接顶点：若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点度、入度和出度：问：当有向图中仅问：当有向图中仅1 1个顶点的入度为个顶点的入度为0,0,其余顶点的其余顶点的入度均为入度均为1 1，此时是何形状？，此时是何形状？答：是树！而且是一棵有向树！答：是树！而且是一棵有向树！第29页生成树：生成树：

19、V1V2V4V5V3V7V6V8例V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8第30页连连 通通 图：图：强连通图：强连通图：有两类图形有两类图形不在本章讨不在本章讨论之列：论之列：连通图245136强连通图356245136非连通图连通分量第31页ADT Graph 数据对象数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。数据关系数据关系R：R=VR；VR=|v,wV 且且 P(v,w), 表示从表示从v到到w的弧，的弧， 谓词谓词P(v,w)定义了弧定义了弧的意义或信息的意义或信息基本操作基本操作P： CreatGr

20、aph ( &G, V,VR); 初始条件：初始条件：V是图的顶点集，是图的顶点集，VR是图中弧的集合。是图中弧的集合。 操作结果：按操作结果：按V和和VR的定义构造图的定义构造图G。 InsertVex ( &G, v); 初始条件：图初始条件：图G存在，存在，v和图中顶点有相同特征。和图中顶点有相同特征。 操作结果：在图操作结果：在图G中添加新顶点。中添加新顶点。 （参见（参见P156-257）注意：注意：V V 的大的大小写含义不同小写含义不同！第32页图的特点：非线性结构（图的特点：非线性结构（m :n m :n ） 邻接表邻接表 邻接多重表邻接多重表 十字链表十字链表设计为邻接矩设计

21、为邻接矩阵阵链式存储结构：链式存储结构：顺序存储结构：顺序存储结构： 无！无！（多个顶点，无序可言）（多个顶点，无序可言）但可用数组描述元素间关系。但可用数组描述元素间关系。可用多重链表可用多重链表重点介绍：重点介绍：第33页 , ),( , , .否否则则或或者者如如果果01AEjiEjijiEdgev1v2v3v5v4v4A邻接矩阵：A.Edge =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1

22、0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0顶点表：第34页例例2 2 ：有向图的邻接矩阵：有向图的邻接矩阵素之和素之和, ,即：即：TD(Vi)=OD( Vi ) + ID( Vi )TD(Vi)=OD( Vi ) + ID( Vi )v1v2v3v4邻接矩阵：A.Edge =( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：在有向图的邻接矩阵中，注：在有向图的邻接矩阵中， 第第i i行含义：以结点行含义：以结点vivi为尾的弧为尾的弧( (即出度边）；即出度边）； 第第i i列含义：以结点列

23、含义：以结点vivi为头的弧为头的弧( (即入度边）。即入度边）。顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 第35页 容易实现图的操作，如：求某顶点的度、判断容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。顶点之间是否有边（弧）、找顶点的邻接点等等。 n n个顶点需要个顶点需要n n* *n n个单元存储边个单元存储边( (弧弧););空间效率空间效率为为O(n2)O(n2)。 对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。特别讨论特别讨论 ：网（即有权图）的邻接

24、矩阵：网（即有权图）的邻接矩阵定义为：定义为： A.Edge i j =Wij 或（或（vi, vj）VR 无边（弧）无边（弧）v1v2v3v4Nv5v65489755613以有向网为例以有向网为例：邻接矩阵： N.Edge =( v1 v2 v3 v4 v5 v6 )邻接矩阵法优点：邻接矩阵法优点：邻接矩阵法缺点：邻接矩阵法缺点：顶点表： 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 第36页注：用两个数组分别存储顶点表和邻接矩阵注：用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX /最大值最大值#define MAX_VE

25、RTEX_NUM 20 /假设的最大顶点数假设的最大顶点数Typedef enum DG, DN, AG,AN GraphKind; /有向有向/无向图，有向无向图，有向/无向网无向网Typedef struct ArcCell /弧（边）结点的定义弧（边）结点的定义 VRType adj; /顶点间关系，无权图取顶点间关系，无权图取1或或0；有权图取；有权图取权值类型权值类型 InfoType *info; /该弧相关信息的指针该弧相关信息的指针ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;图的邻接矩阵存储表示（参见教材图的邻接矩阵存储表

26、示（参见教材P161P161）对于对于n n个顶点的图或网，空间效率个顶点的图或网，空间效率=O(n2)=O(n2)第37页Typedef struct /图的定义图的定义 VertexType vexs MAX_VERTEX_NUM ; /顶点表，用一维向量即可顶点表，用一维向量即可AdjMatrix arcs; /邻接矩阵邻接矩阵Int Vernum, arcnum; /顶点总数，弧（边顶点总数，弧（边）总数）总数GraphKind kind; /图的种类标志图的种类标志 Mgraph;第38页adjvexinfonextarcdatafirstarc邻接点域，表邻接点域，表示示vi一个邻

27、接一个邻接点的位置点的位置链域，指向链域，指向vi下一个边下一个边或弧的结点或弧的结点数据域，与数据域，与边有关信息边有关信息（如权值）（如权值）数据域，存数据域，存储顶点储顶点vi 信信息息链域，指向链域，指向单链表的第单链表的第一个结点一个结点第39页v1v2v3v5v4v4邻接表0123413341420v1v2v3v4V4V3V2V12301邻接表邻接表(出边出边)V4V3V2V13020逆邻接表逆邻接表(入边入边)v1v2v3v4v5231420第40页8064125当邻接表当邻接表的存储结的存储结构形成后构形成后，图便唯，图便唯一确定！一确定！第41页分析分析1: 对于对于n个顶点

28、个顶点e条边的无向图，邻接表中除了条边的无向图，邻接表中除了n个头结点外个头结点外，只有，只有2e个表结点个表结点,空间效率为空间效率为O(n+2e)。若是稀疏图若是稀疏图(en2)，则比邻接矩阵表示法，则比邻接矩阵表示法O(n2)省空间。省空间。邻接表存储法的特点：邻接表存储法的特点：分析分析2:在有向图中，邻接表中除了在有向图中，邻接表中除了n个头结点外，只有个头结点外，只有e个表结点个表结点,空间效率为空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。若是稀疏图，则比邻接矩阵表示法合适。它其实是对邻接矩阵法的一种改进它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？怎样计算

29、无向图顶点的度？邻接表的缺点：邻接表的缺点：怎样计算有向图顶点的出度？怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点的入度？怎样计算有向图顶点怎样计算有向图顶点Vi的度：的度：需遍历全表需遍历全表邻接表的优点：邻接表的优点：TD(Vi)=TD(Vi)=单链表中链接的结点个数单链表中链接的结点个数OD(Vi)单链出边表中链接的结点数单链出边表中链接的结点数I D( Vi ) 邻接点为邻接点为Vi的弧个数的弧个数TD(Vi) = OD( Vi ) + I D( Vi )空间效率高；容易寻找顶点的邻接点；空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点

30、判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。对应的单链表，没有邻接矩阵方便。第42页讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1. 1. 联系：邻接表中每个链表对应于邻接矩阵中的一行，联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2. 2. 区别：区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号

31、无关）。( (考试怎么办？给定顺序）考试怎么办？给定顺序） 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(n2),O(n2),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3. 3. 用途：邻接矩阵多用于稠密图的存储（用途：邻接矩阵多用于稠密图的存储（e e接近接近n(n-n(n-1)/2)1)/2)；而邻接表多用于稀疏图的存储（；而邻接表多用于稀疏图的存储（en2)en2)第43页图的邻接表存储表示（参见教材图的邻接表存储表示（参见教材P163P163）#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数Typedef struct

32、 ArcNode int adjvex; /该弧所指向的顶点位置该弧所指向的顶点位置 struct ArcNode *nextarcs; /指向下一条弧的指针指向下一条弧的指针 InfoArc *info; /该弧相关信息的指针该弧相关信息的指针 ArcNode；Typedef struct VNode /顶点结构顶点结构 VertexType data; /顶点信息顶点信息 ArcNode * firstarc; /指向依附该顶点的第一条弧的指针指向依附该顶点的第一条弧的指针VNode, AdjList MAX_VERTEX_NUM ; Typedef struct /图结构图结构 AdjL

33、ist vertics ; /应包含邻接表应包含邻接表 int vexnum, arcnum; /应包含顶点总数和弧总数应包含顶点总数和弧总数 int kind; /还应说明图的种类（用标志）还应说明图的种类（用标志）ALGraph; /图结构图结构图的邻接表生成算法作为自测题。图的邻接表生成算法作为自测题。空间效率为空间效率为O(n+2e)O(n+2e)或或O(n+e)O(n+e)时间效率为时间效率为O(n+eO(n+e* *n)n)第44页一、深度优先搜索二、广度优先搜索 7.3 7.3 图的遍历图的遍历遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍遍历定义：从已给的连通图中某一顶

34、点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。的遍历，它是图的基本运算。遍历实质：找每个顶点的邻接点的过程。遍历实质：找每个顶点的邻接点的过程。图的遍历操作的特点：图中可能存在回路，且图的任一顶点都图的遍历操作的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。某些边又回到了曾经访问过的顶点。解决思路：可设置一个辅助数组解决思路：可设置一个辅助数组 visited n ，用

35、来标记每个被，用来标记每个被访问过的顶点。它的初始状态为访问过的顶点。它的初始状态为0，在图的遍历过程中，在图的遍历过程中，一旦某一个顶点一旦某一个顶点i 被访问，就立即改被访问，就立即改 visited i为为1，防止，防止它被多次访问。它被多次访问。图常用的遍历：图常用的遍历：怎样避免重复访问？怎样避免重复访问？第45页基本思想：基本思想：仿树的先序遍历过程。仿树的先序遍历过程。Depth_First Searchv1v2v3v8v7v6v4v5起点起点起点起点遍历步骤遍历步骤第46页深度优先搜索（遍历）步骤：深度优先搜索（遍历）步骤：详细归纳：详细归纳：在访问图中某一起始顶点在访问图中某

36、一起始顶点 v 后，由后，由 v 出发，访问它的任一邻接顶点出发，访问它的任一邻接顶点 w1；再从再从 w1 出发，访问与出发，访问与 w1邻接但还未被访问过的顶点邻接但还未被访问过的顶点 w2；然后再从然后再从 w2 出发，进行类似的访问，出发，进行类似的访问， 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。访问的邻接顶点。若有，则访问此顶点，之后再从此顶点出发，进行与前述类似的

37、访问；若有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；若没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶若没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。点都被访问过为止。简单归纳：简单归纳：访问起始点访问起始点 v;若若v的第的第1个邻接点没访问过，深度遍历此邻接点；个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找若当前邻接点已访问过，再找v的第的第2个邻接点重新遍历。个邻接点重新遍历。第47页V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍

38、历：V1 V2 V4 V8 V3 V6 V7 V51654327131791812752410深度遍历：V1 V2 V4 V3 V5 V6练习：第48页1 2 3 4 5 61 0 0 0 0 0 00 0 0 0 0 03 0 0 0 0 0 04 0 0 0 0 0 05 0 0 0 0 0 06 0 0 0 0 0 0000000123456010000100001000010101邻邻接接矩矩阵阵A辅助数组辅助数组 visited n visited n 起起点点开辅助数组开辅助数组 visited n！例：例：1 2 3 4 561 0000 0 0030 0 0040 0 0 05

39、 00 006 0 0 000第49页DFS1(A, n, v) visit（v）; visitedv=1; for( j=1; jlink; while (!p) v=p-data; if(! visitedv ) DFS2(list, v, p); p=p-link; 第54页（设图中有（设图中有 n 个顶点，个顶点，e 条边）条边）如果用邻接矩阵来表示图，遍历图中每一个顶点都要如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的从头扫描该顶点所在行，因此遍历全部顶点所需的时间为时间为O(n2)。如果用邻接表来表示图，虽然有如果用邻接表来表示图，虽然有

40、 2e 个表结点，但只个表结点，但只需扫描需扫描 e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n个头结个头结点的时间，因此遍历图的时间复杂度为点的时间，因此遍历图的时间复杂度为O(n+e)。结论：结论： 稠密图适于在邻接矩阵上进行深度遍历；稠密图适于在邻接矩阵上进行深度遍历； 稀疏图适于在邻接表上进行深度遍历。稀疏图适于在邻接表上进行深度遍历。第55页基本思想：基本思想：仿树的层次遍历过程。仿树的层次遍历过程。Breadth_First Searchv1v2v3v8v7v6v4v5起点起点遍历步骤遍历步骤起点起点第56页V1V2V4V5V3V7V6V8例例V1V2V4V5V3

41、V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7 V8 V5练习：第57页广度优先搜索（遍历）步骤：广度优先搜索（遍历）步骤：简单归纳：简单归纳：在访问了起始点在访问了起始点v之后，依次访问之后，依次访问 v的邻接点；的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；直到所有顶点都被访问过为止。直到所有顶点都被访问过为止。广度优先搜索是一种分层的搜索过程，每向前走一步广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其情况。因此，广度优先搜索不是一个递归的过程，其算