《数据结构考研课程总结.ppt》由会员分享，可在线阅读，更多相关《数据结构考研课程总结.ppt（365页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构,主讲 刘铁铭 单位工院一系二教 Tel: 31946,2020/11/11,数据结构,1,讲课安排： 串讲全书内容 典型习题分析 前年、去年考题分析,2020/11/11,数据结构,2,第一章 概 论,2020/11/11,数据结构,3,2020/11/11,数据结构,4,2020/11/11,数据结构,5,逻辑结构：(有时直接称为数据结构） 线性结构：线性表、栈、队列、串(最多只有一个直接前趋和一个直接后继) 非线性结构：树 、图、多维数组、广义表 说明： 1、逻辑结构与数据元素本身的形式、内容无关 2、逻辑结构与数据元素的相对位置无关 3、逻辑结构与所含结点个数无关,2020/1
2、1/11,数据结构,6,存储结构： 顺序存储方法：数据元素在内存中按序连续存储， 结点间的逻辑关系由存储单元的邻接关系来体现 链接存储方法：用指针指出其直接后继结点的存储位置， 结点间的逻辑关系由存储单元的邻接关系来体现 索引存储方法：数据元素连续存放，再设一个索引表（有序），索引表由索引项组成，每个索引项由关键字和地址构成 分为稠密索引和稀疏索引 散列存储方法：确定散列函数后，根据结点的关键字直接 计算出该结点的存储地址。,2020/11/11,数据结构,7,关系： 逻辑结构是从逻辑关系上描述数据，与存储无关，是独立于计算机的。 逻辑结构是从具体问题抽象出来的数学模型 存储结构是逻辑结构用计
3、算机语言的实现（亦称映象） 数据的运算是定义在数据的逻辑结构上的一个运算的集合 运算的实现与存储结构密切相关 逻辑结构与存储结构是多对多的关系,2020/11/11,数据结构,8,例：一个学生成绩表： 是一个数据结构 每行是一个结点（或记录），由学号、姓名、各科成绩 及平均成绩等数据项组成。 逻辑关系：线性结构 存储结构： 表的运算：,2020/11/11,数据结构,9,2020/11/11,数据结构,10,2020/11/11,数据结构,11,2020/11/11,数据结构,12,2020/11/11,数据结构,13,第一章 概 论,三、（渐进）时间复杂度(O(f(n) 当问题的规模n趋向无
4、穷大时，时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度，简称时间复杂度 四、最坏时间复杂度 依据数据集中可能出现的最坏情况估算出的时间复杂度称为最坏时间复杂度。 五、平均时间复杂度 在假设数据集的分布是等概率的条件下，估算出的时间复杂度称为平均时间复杂度。 例：顺序查找,2020/11/11,数据结构,14,五、空间复杂度S(n)： 算法所耗费的存储空间，仍是问题规模n的函数。,第一章 概 论,2020/11/11,数据结构,15,第一章 概 论,2020/11/11,数据结构,16,第二章 线性表,本章要学习的主要内容 1、线性表的逻辑结构及基本运算 2、线性表的顺序存储结构 3、
5、线性表的链式存储结构：单链表、循环链表、双链表、静态链表 4、顺序表和链表的比较,2020/11/11,数据结构,17,2020/11/11,数据结构,18,2020/11/11,数据结构,19,2020/11/11,数据结构,20,2020/11/11,数据结构,21,2020/11/11,数据结构,22,2020/11/11,数据结构,23,2020/11/11,数据结构,24,2020/11/11,数据结构,25,2020/11/11,数据结构,26,2020/11/11,数据结构,27,2020/11/11,数据结构,28,2020/11/11,数据结构,29,2020/11/11,数
6、据结构,30,2020/11/11,数据结构,31,2.3.2 单链表上的基本运算（实现）,Linklist *CREATLISTR1() char ch; linklist *head,*s,*r; head=malloc(sizeof(linklist); r=head; ch=getchar(); while(ch!=“$”) s=malloc(sizeof(linklist); s-data=ch; r-next=s; r=s; ch=getchar(); r-next=NULL; return head; ,2020/11/11,数据结构,32,2020/11/11,数据结构,33,
7、按值查找即在链表中查找是否有值等于给定值key的结点。若有则返回首次找到的其值为key的结点的指针，否则返回NULL。,算法描述如下： linklist *locate(head,key) linklist *head; datatye key; linklist *p; p=head next;,在等概率的情况下，该算法的平均时间复杂度亦为O(n),（2）按值查找 LOCATE（head，key）,2.3.2 单链表上的基本运算（实现）,while (p!=NULL) if (p data!=key) p=p next; else break ; return p; ,2020/11/11,
8、数据结构,34,3.插入运算,（1）后插操作: 在指针p所指结点之后插入,（2）前插操作: 在指针p所指结点之前插入,时间复杂度度O(1),平均时间复杂度 O(n),先从头指针起, 顺链找到*p的前趋结点*q.,2020/11/11,数据结构,35,x,3.插入运算:,将前插操作转变为后插操作,a,2020/11/11,数据结构,36,4.删除运算,时间复杂度 O(1),删除指定结点的直接后继,r=p-next; p-next=r-next; free(r);,删除指定结点,时间复杂度O(n),链表的优点:在链表上实现插入、删除运算无须移动结点，仅须修改指针,2020/11/11,数据结构,3
9、7,2020/11/11,数据结构,38,2020/11/11,数据结构,39,DELETENODE（p） /*删除双链表结点*p */ dlinklist *p; p-prior-next=p-next; p-next-prior= p -prior; free(p); ,2020/11/11,数据结构,40,2020/11/11,数据结构,41,2.3.5 静态链表,静态链表与动态链表的区别,2020/11/11,数据结构,42,2、静态链表存储结构描述如下：define maxsize 1024 typedef int datatype; typedef int cursor ; typ
10、edef struct datatype data; 数据域 cursor next; 游标 node; node nodepoolmaxsize; 存储池 cursor av; 游标变量,2020/11/11,数据结构,43,2020/11/11,数据结构,44,2020/11/11,数据结构,45,4、节点的分配与回收,GETNODE( ):将表av上的第一个结点 取出，并把该结点的位置付给p Cursor GETNODE( ) cursor p; if(av=NULL) p=NULL; else p=av; av=nodepoolav.next; return p; ,FREENODE(
11、p)将p所指的结点插入到表av的头上。 FREENODE(p) nodepoolp.next=av; av=p ,2020/11/11,数据结构,46,2020/11/11,数据结构,47,2020/11/11,数据结构,48,2020/11/11,数据结构,49,2020/11/11,数据结构,50,2020/11/11,数据结构,51,2020/11/11,数据结构,52,2020/11/11,数据结构,53,2020/11/11,数据结构,54,2020/11/11,数据结构,55,4链栈上基本运算的实现： 1） 进栈 PUSHLSTACK(top,x),2020/11/11,数据结构,
12、56,2） 退栈 *POPLSTACK(top,datap),2020/11/11,数据结构,57,3.2 栈的应用举例,1. 文字编辑器 2. 函数的递归调用（p47),2020/11/11,数据结构,58,2020/11/11,数据结构,59,3队列的基本运算： （1）SETNULL（Q）置队空 （2）EMPTY（Q）判队空 （3）FRONT（Q）取队头元素,队中元素保持不变 （4）ENQUEUE（Q,x) 将元素x入队 （5）DEQUEUE（Q）出队,函数返回原队头元素,2020/11/11,数据结构,60,2020/11/11,数据结构,61,2020/11/11,数据结构,62,20
13、20/11/11,数据结构,63,解决“假上溢”的方法有两种：,2020/11/11,数据结构,64,采用循环队列后，进行入队和出队运算时，头、尾指针加1操作应如下进行： 出队： sq front=(sq front+1)% maxsize; 入队： sq rear=(sq rear+1)% maxsize;,循环队列如何判断队空和队满?,方法一：引入标志flag 若 (sq front=sq rear) struct linknode *next; linkstring; linkstring *s;,如果结点大小不为1， 则此处应说明一个字 符数组。,链串存储结构描述如下：,2020/11
14、/11,数据结构,77,2020/11/11,数据结构,78,2020/11/11,数据结构,79,2020/11/11,数据结构,80,1. 朴素的匹配算法,基本思想：初始时，从S的第一个字符开始将T的第一个字符与其进行比较，若相等，则继续逐个比较后续字符，如匹配成功，则返回子串在S中的位置，否则，将T向右移动一个字符位置，从T的第一个字符开始与S中第二个字符进行比较，并在相等的情况下逐个比较后续字符，进行第二趟匹配，成功则返回子串在S中的位置，否则，T再向右移动一个字符位置，进行第三趟匹配，如此反复，或匹配成功，或当T右移到无法与S继续进行比较时，匹配失败。,2020/11/11,数据结构
15、,81,设S=“ababcabcacbab” T=“abcac”,i指针回溯的位置为：i=i-j+1（i的值为1）,1. 朴素的匹配算法,2020/11/11,数据结构,82,设S=“ababcabcacbab” T=“abcac”,i指针回溯的位置为：i=i-j+1（i的值为2）,2020/11/11,数据结构,83,设S=“ababcabcacbab” T=“abcac”,i指针回溯的位置为：i=i-j+1（i的值为3）,2020/11/11,数据结构,84,设S=“ababcabcacbab” T=“abcac”,i指针回溯的位置为：i=i-j+1（i的值为4）,2020/11/11,数
16、据结构,85,设S=“ababcabcacbab” T=“abcac”,i指针回溯的位置为：i=i-j+1（i的值为5）,2020/11/11,数据结构,86,设S=“ababcabcacbab” T=“abcac”,返回子串的位置为：i-j+1=6（串的起始位置从1开始算起）,2020/11/11,数据结构,87,int index(s,t) seqstring *s,*t; int i=0,j=0; while (iscurlen) ,朴素的模式匹配算法描述如下：,2020/11/11,数据结构,88,2020/11/11,数据结构,89,2020/11/11,数据结构,90,2020/1
17、1/11,数据结构,91,2020/11/11,数据结构,92,2020/11/11,数据结构,93,2020/11/11,数据结构,94,2020/11/11,数据结构,95,3)确定aij与sk的对应关系 a: 若i=j 则 k=i*(i+1)/2+j b: 若 ij 则 k=j*(j+1)/2+i(这是由对称性质决定的）,注意：进行压缩存储后，没有改变原采用二维数组存储时能进行随机访问的特性。,综合a、b，令I=max(i,j), J=min(i,j)，则k=I*(I+1)/2+J,loc(aij)=loc(sak)=loc(sa0)+k*d =loc(sa0)+(I*(I+1)/2+J
18、)*d,a00 a10 a11 a20 a21 a22 aij a n-1,0 a n-1,1 an-1,2 a n-1,n-1,2020/11/11,数据结构,96,2.三角矩阵（方阵）,2020/11/11,数据结构,97,2020/11/11,数据结构,98,i*n-(i-1) *i /2,2020/11/11,数据结构,99,2020/11/11,数据结构,100,2020/11/11,数据结构,101,2020/11/11,数据结构,102,2）稀疏矩阵用三元组表实现压缩存储时的存储结构描述,#define SMAX 16 typedef struct int i,j; dataty
19、pe v; node; typedef struct int m,n,t； node dataSMAX; spmatrix; spmatrix *a;,定义三元组结构,定义三元组表结构,2020/11/11,数据结构,103,3) 运算： 稀疏矩阵采用三元组表实现存储后，其矩阵运算的实现比采用二维数组存储时要复杂。,2020/11/11,数据结构,104,2020/11/11,数据结构,105,2020/11/11,数据结构,106,2020/11/11,数据结构,107,十字链表,2020/11/11,数据结构,109,建立十字链表的算法分为两步： 1.建立表头结点的循环链表 2.依次读入非
20、零元素的三元组，每读入一个三元组，生成一个表结点，并将其插入相应行、列链表中的正确位置上。,2020/11/11,数据结构,110,2020/11/11,数据结构,111,2020/11/11,数据结构,112,2020/11/11,数据结构,113,2020/11/11,数据结构,114,5.3 广义表的存储p83,1、单链表示法（模仿单链表结构）,2、双链表示法（类似于第六章的二叉链表）,2020/11/11,数据结构,115,第六章 树,树形结构是一种重要的非线性结构，在我们的客观世界和现实生活中大量存在。,树形结构：结点之间有分支，并且具有层次关系的结构,2020/11/11,数据结构
21、,116,2020/11/11,数据结构,117,2020/11/11,数据结构,118,2020/11/11,数据结构,119,2020/11/11,数据结构,120,2020/11/11,数据结构,121,2020/11/11,数据结构,122,6.2 二 叉 树,6.2.1 二叉树的概念,一、二叉树的定义： 二叉树(Binary Tree)是n(n=0)个结点的有限集，它或者是空集(n=0)或者由一个根结点和两棵互不相交的，分别称为根的左子树和右子树的二叉树组成。 可以看出，二叉树的定义和树的定义一样，均为递归定义。,2020/11/11,数据结构,123,2020/11/11,数据结构
22、,124,6.2.2 二叉树的性质,性质1：二叉树第i层上的结点数目最多为2i-1 (i=1) 性质2：深度为k的二叉树至多有2k-1个结点(k=1) 性质3：任意二叉树中，若叶结点的个数为n0,度为2的结点数为n2，则n0=n2+1。,2020/11/11,数据结构,125,2020/11/11,数据结构,126,两种特殊形态的二叉树：满二叉树和完全二叉树 深度为k且有2 k-1个结点的二叉树称为满二叉树。, 对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左至 右。, 深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，则称之为
23、完全二叉树。,2020/11/11,数据结构,127,2020/11/11,数据结构,128,2020/11/11,数据结构,129,2020/11/11,数据结构,130,2020/11/11,数据结构,131,2020/11/11,数据结构,132,2020/11/11,数据结构,133,2020/11/11,数据结构,134,2020/11/11,数据结构,135,2020/11/11,数据结构,136,2020/11/11,数据结构,137,2020/11/11,数据结构,138,算法描述： preorder (t ) bitree *t; if (t) printf(“t%c”,td
24、ata); preorder(t lchild); preorder(t rchild); ,2020/11/11,数据结构,139,三种遍历算法的： 1）printf()在算法中的位置不同 2）执行时所“走”的路线是一样的。每个结点经过三次。 3）访问结点的时机不同得到不同的遍历次序。 递归算法看似简单，但执行过程相当复杂。P97,2020/11/11,数据结构,140,2020/11/11,数据结构,141,第一次经过的结点:,第二次经过的结点:,第三次经过的结点:,a,b,d,e,c,f,d,b,a,c,e,f,d,b,e,c,f,a,2020/11/11,数据结构,142,2020/1
25、1/11,数据结构,143,typedef bitree *datatype;typedef struct node datatype data; struct node *next; linkstack; inorder(t) bitree *t; linkstack * top; top=NIL; do while (t!=NIL) top=pushlstack(top,t); t=t lchild; if (top!=NIL) top=poplstack(top, ,算法描述如下：,2020/11/11,数据结构,145,lorder(t) bitree *t;sequeue *sq;
26、/*sq为循环队列指针*/ bitree *x setnull(sq); if (t!=NULL) enqueue(sq,t); while (!empty(sq) x=dequeue(sq); printf(%dt,x data); if (x lchild!=NIL) enqueue(sq, x lchild); if (x rchild!=NIL) enqueue(sq, x rchild); ,6.4 线索二叉树,问题 单单依靠二叉树并不能直接得到结点在任一序列中的前趋和后继,这种信息只有在动态遍历中才能得到.所以某次遍历得到的信息,下次再用时,仍要重新遍历.,一、如何保存在遍历过程中
27、得到的信息?,2020/11/11,数据结构,147,利用已有的指针域存放:,利用二叉链表上的n1个空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针，由此得到的二叉链表称为线索链表，相应地采用这种存储结构的二叉树称为线索二叉树。,线索链表中结点的结构：,typedef struct node int ltag,rtag; datatype data; struct node *lchild,*rchild; bithptr; bithptr *p;,2020/11/11,数据结构,148,线索化(建立某次序线索二叉树的步骤2，步骤1类似于二叉链表的建立过程）:将二叉树以某种次序遍历
28、使其变为线索二叉树的过程称为线索化。具体地体现在将二叉链表变为线索链表。,2020/11/11,数据结构,149,2020/11/11,数据结构,150,2020/11/11,数据结构,151,2020/11/11,数据结构,152,2020/11/11,数据结构,153,2020/11/11,数据结构,154,2020/11/11,数据结构,155,2020/11/11,数据结构,156,2020/11/11,数据结构,157,2、 遍历线索二叉树,遍历二叉树：指按某种路径对树中结点访问且仅访问一次。,遍历线索二叉树：从某次序下的开始结点出发，反复找到该结点在该次序下的后继，直至终端结点。,
29、算法要点：,（1）如果线索二叉树非空，则做（2），否则结束。（2）找到某次序下的开始结点。 （3）访问该结点。 （4）找到该结点在该次序下的后继。 （5）不是空则转（3），否则结束,2020/11/11,数据结构,158,总结：1）遍历线索二叉树对中序和前序线索树，很容易实现。但后序不好实现。因为后序后继不能直接找到。 2)比二叉树遍历算法简单易理解，且无需设栈。 3）若一棵二叉树要经常进行遍历运算，或经常查找结点在某种指定次序下的前趋和后继，则选用线索二叉树。,2020/11/11,数据结构,159,3、线索二叉树的插入,线索二叉树的优点：查找和遍历优于非线索树。,线索二叉树的缺点：插入和删
30、除不仅要修改指针，还要修改线索。,线索二叉树的插入和删除也分为前序，中序和后序，,2020/11/11,数据结构,160,2020/11/11,数据结构,161,2020/11/11,数据结构,162,2020/11/11,数据结构,163,2020/11/11,数据结构,164,2020/11/11,数据结构,165,2020/11/11,数据结构,166,2020/11/11,数据结构,167,3.孩子兄弟链表表示法,在存储结点信息的同时,附加两个分别指向该结点最左孩子和右邻兄弟的指针域。该方法实际上是用二叉链表实现树的储存。,2020/11/11,数据结构,168,2020/11/11,
31、数据结构,169,2020/11/11,数据结构,170,2020/11/11,数据结构,171,特点：1)前序遍历森林得到的序列与前序遍历对应二叉树得到的序列相同。 2)后序遍历森林得到的序列与中序遍历对应二叉树得到的序列相同。,2020/11/11,数据结构,172,2020/11/11,数据结构,173,2020/11/11,数据结构,174,2、哈夫曼算法已知w1,w2,wn这n个权值后，如何构造哈夫曼树？,1）哈夫曼算法思想(1)根据给定的n个权值w1,w2,wn构造n棵只有根结点的树 (2) 从中选两棵根结点权值最小的树进行合并 ，增加一个新结点作为新树的根，树的数目减少一棵。 (
32、3) 重复(2),直到F只含一棵二叉树为止，这棵二叉树便是哈夫曼树。,(10,9,5,6),哈夫曼树的特点 哈夫曼树中只有0度和2度结点，不可能有1度结点。 具有n个叶结点的哈夫曼树所含结点数必为2n-1。 具有n个叶结点的哈夫曼树的最大高度为n。 哈夫曼树的形式不是唯一的，但wpl值是唯一的。 哈夫曼树不一定是朝一个方向的。,2020/11/11,数据结构,177,2020/11/11,数据结构,178,构造最优 (平均码长最短的)前缀码的方法如下：,（1）以字符集中每个字符出现的概率为权值，构造哈夫曼树。 （2）在哈夫曼树中每个分支结点的左分支上标上0，右分支上标上1。 （3）把从根到每个
33、叶结点的路径上的所有0或1标号连接起来作为叶结点所代表的字符的编码。,2020/11/11,数据结构,179,图是一种复杂的非线性结构。线性结构、树形结构中 对结点而言，存在前趋和后继的概念，图中的结点（通常称为顶点）是否也有前趋和后继呢？不能一概而论。,图G由两个集合V和E组成，记为G=(V,E),其中V为顶点的有穷非空集合，E为V中顶点偶对(即边)的集合。图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集，若E(G)为空，则图G只有顶点而没有边。,第七章 图,有向图:图G中的每一条边都是有方向的， 。 无向图: 图中的每一条边都是无方向的。 (vi,vj),2020/11/1
34、1,数据结构,180,简单图:以下我们讨论的图是满足下列两条件的简单图：,（1）不含顶点到自身的边，即若（Vi ，Vj ）或 Vi ，Vj E（G） 则 ViVj （2）不允许一条边在图中重复出现 具有上述要求的图，其顶点数 n 和边数 e 满足下列关系: 若G为无向图 0 e n（n-1）/2 若G为有向图 0 e n（n-1）,2020/11/11,数据结构,181,恰好有 n(n-1)/2 条边的无向图称为无向完全图； 恰好有 n(n-1) 边的有向图称为有向完全图。,若 (vi,vj) 是一条无向边，则称顶点 vi 和 vj 互为邻结点(Adjacent)，(vi,vj) 与顶点 vi
35、 和 vj 相关联(Incident)。若 是一条有向边，则称顶点 vi 邻接到 vj,顶点 vj 邻接于 vi, 与顶点 vi 和 vj 相关联。,2020/11/11,数据结构,182,度、入度和出度的概念： 无向图中顶点v的度为关联于该顶点的边的数目，记为D(v) 有向图中把以顶点v为终点的边的数目称为v的入度，记为ID(v) 把以顶点v为始点的边的数目称为v的出度,记为OD(v) 顶点的度定义为入度与出度之和，即D(v)=ID(v)+OD(v)。,子图的概念:设G=(V,E)是一个图，若V是V的子集，E是E的子集且E中的边所关联的顶点均在V中，则G=(V,E)也是一个图，并称其为G的子
36、图。,V=v0,v1,E=(v0,v2), G=(V,E)不是图,也不可能是子图。,第七章 图,2020/11/11,数据结构,184,2020/11/11,数据结构,185,2020/11/11,数据结构,189,2、 邻接矩阵存储结构描述： #define n . /* 图中顶点个数 */ #define e . /* 图中边(弧)条数 */ typedef char vextype; /* 顶点数据类型 */ typedef float adjtype;/* 权值类型 */ typedef struct vextype vexsn; /* 数组vexs 用于存储顶点数据 */ adjty
37、pe arcsnn; /* arcs 为邻接矩阵 */ graph; 若图中顶点信息仅为编号, 则仅需存储一个邻接矩阵即可表示图。采用邻接矩阵表示法实现图的存储，空间复杂度为O(n2)。,2020/11/11,数据结构,192,typedef strcutvextype vertex; edgenode *link; vexnode; /*顶点表结点结构*/ vexnode gan;,2、邻接表存储结构描述： typedef struct node int adjvex; struct node *next edgenode; /*边表结点结构*/,2020/11/11,数据结构,193,20
38、20/11/11,数据结构,194,2020/11/11,数据结构,195,7)总结,第七章 图,2020/11/11,数据结构,197,定义 图的遍历是指从图的某个顶点出发，沿着某条搜索路径对图中所有顶点访问且仅访问一次。,7.3 图的遍历,一. 图遍历运算的基本概念,2020/11/11,数据结构,198,特点：遍历过程中尽可能地先对纵深方向进行搜索,2020/11/11,数据结构,199,DFSL(i) int i; int j; edgenode *p; printf(“node:%cn,gli.vertex); visitedi=TRUE; p=gli.link;/*取vi的边表头指
39、针*/ while(p!=NULL)/*依次搜索vi的邻接点*/ if (!visitedp-adjvex)/*从vi的未曾访问过的邻接点出发进行深度优先搜索*/ DFSL(p-adjvex); p=p-next; /*找vi的下一邻接点*/ ,以邻接表为存储结构的深度优先算法:,2020/11/11,数据结构,200,7.3 图的遍历,DFS序列不唯一,它与遍历算法，图的存储结构以及初始出发点有关。,3.算法分析,对于具有n个顶点、e条边的连通图：,对图进行深度优先搜索得到的顶点序列称为深度优先搜索序列，简称为DFS序列。,注意,2020/11/11,数据结构,201,7.3 图的遍历,三.
40、 连通图的广度优先搜索遍历(Breadth First Search),1. BFS基本思想 从图G中任一顶点vi开始，首先访问顶点vi，接着依次访问vi的所有邻接点w0,w1,wt，然后再依次访问w0,w1,wt邻接的所有未被访问过的顶点，依次类推，直到图中所有和vi有路径相通的顶点都被访问过为止。,特点：尽可能地先对横向进行搜索。,BFS算法,符合先进先出性质。在算法实现过程中，引入队列作为辅助存储结构，存储已被访问的顶点。,2.算法实现:,2020/11/11,数据结构,202,BFSL(int k) int i; edgenode *p; setnull(q); printf(%cn,
41、glk.vertex); visitedk=true; enqueue(q,k); while (! empty(q) i=dequeue(q); p=gli.link; while(p!=null) if(!visitedpadjvex) printf(%cn,glpadjvex.vertex); visitedpadjvex=true; enqueue(q, padjvex); p=pnext; ,/* 从vk出发广度优先搜索图,图G用邻接表表示 */,/* 初始将队列q置空 */,/* 访问出发点vk并置访问标志 */,/* 已访问的顶点序号入队 */,/* 队头元素序号出队列 */,/
42、*取vi邻接表的头指针 */,/* 访问vi未访问的邻接点 */,/* 已访问的顶点序号入队 */,/* 找vi的下一个邻接点*/,2020/11/11,数据结构,203,7.3 图的遍历,对图进行广度优先搜索得到的顶点序列称为广度优先搜索序列，简称为 BFS序列。,两种遍历方法比较：,BFS序列不唯一,BFS序列与遍历算法，图的存储结构以及初始出发点有关。,3.算法分析,对于具有n个顶点、e条边的连通图：,二者对顶点的搜索次序不同,两种遍历方法实现的手段不同,注意,2020/11/11,数据结构,204,7.3 图的遍历,四.非连通图的遍历,非连通图具有两个或两个以上的连通分量, 当从某个顶
43、点vi开始对其进行深度或广度优先搜索只能遍历包含顶点vi的连通分量。,非连通图的遍历须多次调用深度或广度优先搜索算法。,2020/11/11,数据结构,205,7.3 图的遍历,非连通图遍历算法描述： TRAVER( ) int i; for (i=0;in;i+) visitedi=false; for (i=0;in;i+) if(!visitedi) DFS(i); ,遍历各个连通分量,初始访问标志,深度优先搜索遍历非连通图算法,BFSL(i);,广度优先搜索遍历非连通图算法,如果图是连通的,则算法TRAVER只调用一次DFS(或BFS)；,如果图包含n个连通分量,则算法TRAVER调用
44、n次DFS(或BFS)；,2020/11/11,数据结构,206,7.4 生成树和最小生成树,1）定义：具有n个顶点的无向连通图G，其生成树为包含有n个顶点和n-1条边的无向连通子图，或生成树是连通图G的一个极小连通子图。,1。无向连通图的生成树的定义,2）特点： a.无向连通图的生成树通常是不唯一的 b.生成树满足连通性且边数最小,3）无向非连通图没有生成树，但其各个连通分量有生成树，各个连通分量的生成树形成一个森林，称为无向非连通图的生成森林。,第七章 图,2020/11/11,数据结构,209,2020/11/11,数据结构,210,Prim算法思想：假设G=(V,E)为无向连通网，生成
45、的最小生成树T=(U,TE)。求T（实际上求TE）的步骤为：1）初始化U=u0， TE= 2）在所有uU，v V-U的边(u,v) 中找一条权值最小的边(u0,v0)并入集合TE，同时v0并入U。 3）若U=V，算法结束。否则重复2）,5。如何求无向连通网的最小生成树。,prim算法的时间复杂度为O(n2),与无向连通网中顶点数n有关，与边无关，因此该算法适合稠密连通网。,2020/11/11,数据结构,211,Kruskal算法的初略描述： G=(V,E) ,T=(V, ); while(T中所含边数n-1) 从E中选取当前权值最小边(u,v); 从E中删去边(u,v); if (u,v)并
46、入T之后不产生回路) 将边(u,v)并入T中; ,2020/11/11,数据结构,212,2020/11/11,数据结构,213,二、对给定的有向网G=(V,E)和源点v，如何求单源最短路径？Dijkstra算法,1、Dijkstra算法思想：从给定的源点开始，按路径长度递增的顺序，逐步产生源点到其余各顶点的最短路径。,2、算法思想的具体实现：,2020/11/11,数据结构,214,1) 基本原理：设置一个顶点集合S，S中的所有顶点其最短路径已经求出，初始时S=v，则尚未求出最短路径的顶点集为V-S。另外，设置一个数组d ，若顶点vi的最短路径已求出，则di存放的是最短路径长度，否则di存放
47、的是从顶点v经S 中的顶点到vi的所有路径中最短路径的长度，并称其为vi的距离。初始时 wi 若为G中的边 di= 若不是G中的边,设vj为V-S中距离最短的顶点，可以证明（1）dj为vj的最短路径的长度；（2）顶点vj为V-S中最短路径长度最短的顶点。,2020/11/11,数据结构,215,调整方法：对V-S中任意顶点vj，若djdk+,则将dk+的值赋给dj,否则，dj的值不变。,2）Djkstra算法的粗略描述： S=v; 初始化V-S中各顶点的距离值； while(S中的顶点数n) 从V-S中选取距离值最小的顶点vj; S=S+vj; 调整V-S中各顶点的距离值； ,2020/11/
48、11,数据结构,216,2020/11/11,数据结构,217,定义一个nn的方阵序列：A(-1)， A(0) ， A(1) ， A(k) ， A(n-1) 其中: A(-1)ij=cij A(k) ij=MinA(k-1) ij, A(k-1) ik+ A(k-1) kj 0=k=n-1 由上述公式可知， A(0)ij是从顶点vi到vj的中间顶点序号不大于0的最短路径； A(k) ij是从顶点vi到vj的中间顶点序号不大于k的最短路径；A(n-1) ij就是从顶点vi到vj的最短路径。,2）实现原理：定义一个nn的方阵序列：,2020/11/11,数据结构,218,3）具体实现 a) Floyd算法在具体实现时仅使用一个nn的方阵A，初始时A= cij,通过在A上进行n次迭代求得A(n-1) 。 由于是在同一个矩阵A中迭代，所以 A(k) ij A(k-1) ik+ A(k-1) kj是由Aij A ik+ A kj实现的。因此要使迭代正确，必须保证： Aik A(k-1) ik， Akj A(k-1