2022年数据结构知识点全面总结—.docx

《2022年数据结构知识点全面总结—.docx》由会员分享，可在线阅读，更多相关《2022年数据结构知识点全面总结—.docx（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 第1章 绪论 内容提要：数据结构争论的内容；操作对象 以及它们之间的关系和操作 ；针对非数值运算的程序设计问题,争论运算机的数据结构涵盖的内容：基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型；数据 全部能被运算机识别、储备和处理的符号的集合；数据元素 是数据的基本单位,具有完整确定的实际意义；数据对象 具有相同性质的数据元素的集合,是数据的一个子集；数据结构 是相互之间存在一种或多种特定关系的数据元素的集合,表示为：Data_Structure= （D, R）数据类型 是一个值的集合和定义在该值上的一组操作的总称；抽象数据

2、类型 由用户定义的一个数学模型与定义在该模型上的一组操作,它由基本的数据类型构成；算法的定义及五个特点；它是指令的有限序列,是一系列输入转换为输算法 是对特定问题求解步骤的一种描述,出的运算步骤；算法的基本特性：输入、输出、有穷性、确定性、可行性算法设计要求；正确性、可读性、健壮性、效率与低储备量需求算法分析；时间复杂度、空间复杂度、稳固性学习重点：数据结构的“ 三要素”：规律结构 、物理（储备）结构 及在 这种结构上所定义的操作（运算） ；名师归纳总结 用运算语句频度来估算算法的时间复杂度；第 1 页,共 29 页- - - - - - -精选学习资料 - - - - - - - - - 其

3、次章 线性表内容提要：线性表的规律结构定义,对线性表定义的操作；线性表的定义：用数据元素的有限序列表示线性表的储备结构：次序储备结构和链式储备结构；次序储备定义：把规律上 相邻 的数据元素储备在物理上 相邻 的储备单元中的储备结构；链式储备结构 : 其结点在储备器中的位置是随便的,即规律上 相邻 的数据元素在物理上 不一定相邻；通过 指针 来实现！线性表的操作在两种储备结构中的实现；数据结构的基本运算：修改、插入、删除、查找、排序1 修改通过数组的下标便可拜访某个特定元素并修改之；核心语句 : Vi=x; 次序表修改操作的时间效率是 O12 插入在线性表的第 i 个位置前插入一个元素实现步骤：

4、将第 n 至第 i 位的元素向后移动一个位置；将要插入的元素写到第 i 个位置；表长加 1；留意：事先应判定 : 插入位置 i 是否合法 .表是否已满 . 应当符合条件：1in+1 或 i=1, n+1 核心语句：for j=n; j=i; j- aj+1=a j ; a i =x; n+; 插入时的平均移动次数为：nn+1/2 （ n+1） n/2On 3 删除删除线性表的第 i 个位置上的元素 实现步骤：将第 i+1 至第 n 位的元素向前移动一个位置；表长减 1；留意：事先需要判定,删除位置 i 是否合法 . 1i n 或 i=1, n 应当符合条件：核心语句：for j=i+1; j=

5、n; j+ aj-1=aj; n-; 名师归纳总结 - - - - - - -第 2 页,共 29 页精选学习资料 - - - - - - - - - 次序表删除一元素的时间效率为 :T（n=n-1/2 On 次序表插入、删除算法的平均空间复杂度为 O1 单链表：（1）用单链表结构来存放26 个英文字母组成的线性表（a,b,c, , z）,请写出 C 语言程序；#include #include typedef struct node char data; struct node *next; node; node *p,*q,*head; /一般需要 3 个指针变量node 类型的长度就固定

6、了,int n ; / 数据元素的个数int m=sizeofnode; /* 结构类型定义好之后,每个m 求一次即可 */ void build /字母链表的生成；要一个个渐渐链入 int i; head=node*mallocm; p=head; /m=sizeofnode 前面已求出for i=1; idata=i+ a-1; / 第一个结点值为字符 a p-next=node*mallocm; /为后继结点“ 挖坑”！p=p-next ； /让指针变量 P 指向后一个结点p-data=i+ a-1; /最终一个元素要单独处理p-next=NULL ; /单链表尾结点的指针域要置空！ v

7、oid display /字母链表的输出 p=head; while p /当指针不空时循环（仅限于无头结点的情形） printf%c,p-data; p=p-next; /让指针不断“ 顺藤摸瓜” 名师归纳总结 - - - - - - -第 3 页,共 29 页精选学习资料 - - - - - - - - - （2）单链表的修改 或读取）思路：要修改第i 个数据元素,必需从头指针起始终找到该结点的指针p,然后才能： pdata=new_value 读取第 i 个数据元素的核心语句是：Linklist *findLinklist *head ,int i int j=1; Linklist *

8、p; P=head-next; Whilep.=NULL&jnext; j+; return p; 3.单链表的插入链表插入的核心语句：Step 1：s-next=p-next; Step 2：p-next=s ；6.单链表的删除删除动作的核心语句（要借助帮助指针变量 q）：q = p-next; /第一储存 b 的指针,靠它才能找到c；p-next=q-next; /将 a、c 两结点相连,剔除b 结点；freeq ；/完全释放 b 结点空间7.双向链表的插入操作：设 p 已指向第i 元素,请在第i 元素前插入元素x： ai-1 的后继从 ai 指针是 p变为 x（指针是 s : s-nex

9、t = p ; p-prior-next = s ; ai 的前驱从 ai-1 指针是 p-prior 变为 x 指针是 s; s-prior = p -prior ; p-prior = s ; 名师归纳总结 - - - - - - -第 4 页,共 29 页精选学习资料 - - - - - - - - - 8.双向链表的删除操作：设 p 指向第i 个元素,删除第i 个 元素后继方向： ai-1 的后继由 ai 指针 p变为 ai+1指针 p -next ; p -prior-next = p-next ; 前驱方向： ai+1 的前驱由 ai 指针 p变为 ai-1 指针 p - prio

10、r ; p-next-prior = p -prior ; 数组的规律结构定义及储备数组：由一组名字相同、下标不同的变量构成N 维数组的特点：n 个下标,每个元素受到 n 个关系约束一个 n 维数组可以看成是 由如干个 n 1 维数组 组成的线性表；储备：事先商定按某种次序将数组元素排成一列序列,然后将这个线性序列存入储备器中；在二维数组中,我们既可以规定按行储备,也 可以规定按列储备；设一般的二维数组是 Ac1.d1, c2.d2 ,就行优先储备时的地址公式为：二维数组列优先储备的通式为：稀疏矩阵（含特殊矩阵）的储备及运算；稀疏矩阵：矩阵中非零元素的个数较少（一般小于 5%）学习重点：线性表

11、的规律结构,指线性表的数据元素间存在着 线性关系 ；在次序储备结构中,元素储备的 先后位置 反映出这种线性关系,而在链式储备结构中,是靠 指针 来反映这种关系的；次序储备结构用一维数组表示,给定下标,可以存取相应元素,属于 随机存取 的储备结构；链表操作中应留意不要使链意外“ 断开”；因此,如在某结点前插入一个元素,或删除某元素,必需知道该元素的 前驱结点的指针；把握通过画出结点图来进行链表（单链表、循环链表等）的 生成、插入、删除、遍历 等操作；名师归纳总结 数组（主要是二维）在以行序 /列序 为主的储备中的地址运算方法；第 5 页,共 29 页稀疏矩阵的三元组表储备结构；稀疏矩阵的十字链表

12、储备方法；- - - - - - -精选学习资料 - - - - - - - - - 补充重点：1.每个储备结点都包含两部分：数据域和指针域链域 其直接前驱结点的链域的值指示；2.在单链表中, 除了首元结点外, 任一结点的储备位置由3.在链表中设置头结点有什么好处？头结点即在链表的首元结点之前附设的一个结点,表长度 等附加信息, 其作用是为了对链表进行操作时,元结点 进行统一处理,编程更便利；4.如何表示空表？（1）无头结点时,当头指针的值为空时表示空表；（2）有头结点时,当头结点的指针域为空时表示空表；该结点的 数据域可以为空, 也可存放 可以对 空表、 非空表 的情形以及对 首5.链表的数

13、据元素有两个域,不再是简洁数据类型,编程时该如何表示？因每个结点至少有两个重量,且数据类型通常不一样,所以要采纳结构数据类型；6.sizeofx运算变量 x 的长度（字节数） ；mallocm 开创 m 字节长度的地址空间,并返回这段空间的首地址；freep 释放指针 p 所指变量的储备空间,即完全删除一个变量；7.链表的运算效率分析：（1）查找因线性链表只能次序存取,即在查找时要从头指针找起,查找的时间复杂度为 On；（2） 插入和删除因线性链表不需要移动元素,只要修改指针,一般情形下时间复杂度为 O1 ；但是,假如要在单链表中进行前插或删除操作,由于要从头查找前驱结点,所耗时间复杂度将是O

14、n ；*P,需找到它的 前驱结点的地址,其时间复杂例：在 n 个结点的单链表中要删除已知结点度为 O（n）8. 次序储备和链式储备的区分和优缺点？其物理存放地址也相邻；次序储备的优点是储备次序储备时, 规律上相邻的数据元素,密度大,储备空间利用率高；缺点是插入或删除元素时不便利；链式储备时, 相邻数据元素可随便存放,但所占储备空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针；链式储备的优点是插入或删除元素时很便利,使用敏捷；缺点是储备密度小,储备空间利用率低；次序表相宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作；如线性表的长度变化不大,且其主要操作是查找,就采纳

15、次序表；如线性表的长度变化较大,且其主要操作是插入、删除操作,就采纳链表；9. 判定：“ 数组的处理比其它复杂的结构要简洁”,对吗？答：对的；由于 数组中各元素具有 统一的类型； 数组元素的下标一般具有 固定的上界和下界,即数组一旦被定义,它的维数和维界就不再转变；数组的 基本操作比较简单,除了结构的初始化和销毁之外,只有存取元素和修改元素值的操作；10.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别名师归纳总结 表示该元素的行下标、列下标和 元素值；第 6 页,共 29 页- - - - - - -精选学习资料 - - - - - - - - - 11.写出右图

16、所示稀疏矩阵的压缩储备形式；解：介绍 3 种储备形式；法 1：用线性表表示：（ 1,2,12 ,1,3,9, 3,1,-3 , 3,5,14,4,3,24 , 5,2,18 ,6,1,15, 6,4,-7 ）法 2：用十字链表表示用途：便利稀疏矩阵的加减运算方法：每个非 0 元素占用 5 个域法 3：用三元组矩阵表示：稀疏矩阵压缩储备的缺点：将失去随机存取功能代码：1.用数组 V 来存放 26 个英文字母组成的线性表（和显示该表的 C 语言程序；char V30; void build /字母线性表的生成,即建表操作 int i; V0=a; for i=1; i=n-1; i+ Vi=Vi-

17、1+1; void display / 字母线性表的显示,即读表操作 int i; for i=0; iM 上溢 else stop+=e; 次序栈出栈函数 POP status Pop iftop=L 下溢 returne; else e=s-top; 名师归纳总结 - - - - - - -第 8 页,共 29 页精选学习资料 - - - - - - - - - 队列的定义及操作,队列的删除在一端（队尾）,而插入就在队列的另一端（队头）；因此在两种储备结构中,都需要队头和队尾两个指针；队列：只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表；链队列结点类型定义：typedef S

18、truct QNode QElemType data; /元素Struct QNode *next; /指向下一结点的指针Qnode , * QueuePtr ; 链队列类型定义：typedef struct QueuePtr front ; / 队首指针QueuePtr rear ; /队尾指针 LinkQueue; 链队示意图：空链队的特点：front=rear 链队会满吗？一般不会,由于删除时有 free 动作；除非内存不足！ 入队（尾部插入） ：rear-next=S; rear=S; 出队（头部删除） ：front-next=p-next; 2.次序队次序队类型定义：#define

19、QUEUE-MAXSIZE 100 /最大队列长度typedef struct QElemType *base; /队列的基址int front; /队首指针int rear; /队尾指针SqQueue 建队核心语句：q . base=QElemType *mallocsizeof QElemType ）* QUEUE_MAXSIZE; /安排空间次序队示意图：名师归纳总结 - - - - - - -第 9 页,共 29 页精选学习资料 - - - - - - - - - 循环队列：队空条件: front = rear 初始化时： front = rear 队满条件：front = rear+

20、1 % N N=maxsize 队列长度（即数据元素个数）1）初始化一个空队列：L=（Nrearfront） % N Status InitQueue SqQueue &q / 初始化空循环队列q q . base=QElemType *mallocsizeofQElemType）* QUEUE_MAXSIZE; /安排空间if .q.base exitOVERFLOW;/ 内存安排失败,退出程序q.front =q.rear=0; / 置空队列return OK; /InitQueue; 2）入队操作Status EnQueueSqQueue &q, QElemType e / 向循环队列

21、q 的队尾加入一个元素 e if q.rear+1 % QUEUE_MAXSIZE = = q.front return ERROR ; / 队满就上溢,无法再入队q.rear = q . rear + 1 % QUEUE_MAXSIZE; q.base q.rear = e; /新元素 e 入队return OK; / EnQueue; 3）出队操作Status DeQueue SqQueue &q, QElemType &e / 如队列不空,删除循环队列 q 的队头元素,/由 e 返回其值,并返回 OK if q.front = = q.rear return ERROR;/ 队列空q.f

22、ront=q.front+1 % QUEUE_MAXSIZE ; e = q.base q.front ; return OK; / DeQueue 链队列空的条件是首尾指针相等,而循环队列满的条件的判定,就有队尾加1 等于队头和设标记两种方法；名师归纳总结 - - - - - - -第 10 页,共 29 页精选学习资料 - - - - - - - - - 补充重点：1.为什么要设计堆栈？它有什么特殊用途？ 调用函数或子程序非它莫属； 递归运算的有力工具； 用于爱护现场和复原现场； 简化了程序设计的问题；2.为什么要设计队列？它有什么特殊用途？ 离散大事的模拟（模拟大事发生的先后次序 ,例如

23、 CPU 芯片中的指令译码队列）； 操作系统中的作业调度（一个 CPU 执行多个作业） ； 简化程序设计；3.什么叫“ 假溢出”？如何解决？答：在次序队中,当尾指针已经到了数组的上界,不能再有入队操作,但其实数组中仍有空位置,这就叫“ 假溢出”；解决假溢出的途径采纳循环队列；4.在一个循环队列中,如商定队首指针指向队首元素的前一个位置；那么,从循环队列中删除一个元素时,其操作是先移动队首位置,后 取出元素 ；5.线性表、栈、队的异同点：相同点：规律结构相同,都是线性的；都可以用次序储备或链表储备；栈和队列是两种特殊的线性表,即受限的线性表（只是对插入、删除运算加以限制）；不同点： 运算规章不同

24、：线性表为随机存取；而栈是只答应在一端进行插入和删除运算,因而是后进先出表 LIFO ；队列是只答应在一端进行插入、另一端进行删除运算,因而是先进先出表 FIFO ； 用途不同,线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、 OS 作业调度和简化设计等；名师归纳总结 - - - - - - -第 11 页,共 29 页精选学习资料 - - - - - - - - - 第四章 串 内容提要 ：串是数据元素为字符的线性表,串的定义及操作；串即字符串,是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表；串比较： int strcmpchar *s1,cha

25、r *s2; 求串长： int strlenchar *s; 串连接： char strcatchar *to,char *from 子串 T 定位： char strchrchar *s,char *c; 串的储备结构,因串是数据元素为字符的线性表,所以存在“ 结点大小” 的问题；模式匹配算法；串有三种机内表示方法：模式匹配算法：算法目的：确定主串中所含子串第一次显现的位置（定位）定位问题称为串的模式匹配,典型函数为 IndexS,T,pos BF 算法的实现即编写 IndexS, T, pos函数 BF 算法设计思想：将主串 S 的第 pos 个字符和模式 T 的第 1 个字符比较,如相等

26、,连续逐个比较后续字符；如不等,从主串 S 的下一字符（ pos+1）起,重新与 T 第一个字符比较；直到主串 S 的一个连续子串字符序列与模式 T 相等；返回值为 S 中与 T 匹配的子序列 第一个字符的序号,即匹配胜利；否就,匹配失败,返回值 0；Int Index_BPSString S, SString T, int pos / 返回子串 T 在主串 S 中第 pos 个字符之后的位置；如不存在,就函数值为 0. / 其中, T 非空, 1posStrLengthS j=1; i=pos; while i=S0 & jT0 return i-T0; /T 子串指针 j 正常到尾,说明匹

27、配胜利,else return 0; /否就属于 iS0 情形, i 先到尾就不正常 /Index_BP 名师归纳总结 - - - - - - -第 12 页,共 29 页精选学习资料 - - - - - - - - - 补充重点：1.空串和空白串有无区分？答：有区分；空串 Null String 是指长度为零的串；而空白串 Blank String, 是指包含一个或多个空白字符空格键 的字符串 . S2.“ 空串是任意串的子串；任意串S 都是 S 本身的子串,除S 本身外, S 的其他子串称为的真子串；”名师归纳总结 - - - - - - -第 13 页,共 29 页精选学习资料 - -

28、- - - - - - - 第六章 树和二叉树内容提要：树是复杂的非线性数据结构,树,二叉树的递归定义,基本概念,术语；树：由一个或多个 n 0结点组成的有限集合 T,有且仅有一个结点称为根（root）,当 n1时,其余的结点分为 mm 0个互不相交的有限集合 T1,T2 , , Tm；每个集合本身又是棵树,被称作这个根的子树；二叉树：是 n（n0）个结点的有限集合,由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成；术语： P88 二叉树的性质,储备结构；性质 1: 在二叉树的第 i 层上至多有 2i-1 个结点（ i0）；性质 2: 深度为 k 的二叉树至多有 2k-1 个

29、结点（ k0 ）；性质 3: 对于任何一棵二叉树,如 2 度的结点数有 n2 个,就叶子数（n0）必定为 n21 性质 4: 具有 n 个结点的完全二叉树的深度必为性质 5: 对完全二叉树,如从上至下、从左至右编号,就编号为i 的结点,其左孩子编号必为 2i ,其右孩子编号为2i1；其双亲的编号必为i/2 （i1 时为根 ,除外）；二叉树的储备结构：一、次序储备结构 按二叉树的结点“ 自上而下、从左至右” 编号,用一组连续的储备单元储备；如是完全 /满二叉树就可以做到唯独复原；不是完全二叉树：一律转为完全二叉树！方法很简洁,将各层空缺处统统补上“ 虚结点”,其内容为空；缺点：铺张空间；插入、删

30、除不便 二、链式储备结构 用二叉链表即可便利表示；一般从根结点开头储备；优点：不铺张空间；插入、删除便利二叉树的遍历；指根据某种次序拜访二叉树的全部结点,并且每个结点仅拜访一次,得到一个线性序列；遍历规章二叉树由根、左子树、右子树构成,定义为 D、 L 、R 如限定先左后右,就有三种实现方案：名师归纳总结 DLR LDR LRD 第 14 页,共 29 页先序遍历中序遍历后序遍历- - - - - - -精选学习资料 - - - - - - - - - 树的储备结构,树、森林的遍历及和二叉树的相互转换；回忆 2：二叉树怎样仍原为树？要点：逆操作,把全部右孩子变为兄弟！争论 1：森林如何转为二叉

31、树？法一：各森林先各自转为二叉树；依次连到前一个二叉树的右子树上；法二：森林直接变兄弟,再转为二叉树 争论 2：二叉树如何仍原为森林？要点：把最右边的子树变为森林,其余右子树变为兄弟 树和森林的储备方式：树有三种常用储备方式：双亲表示法 孩子表示法 孩子兄弟表示法 问：树二叉树的“ 连线抹线旋转”如何由运算机自动实现？答：用“ 左孩子右兄弟” 表示法来储备即可；储备的过程就是树转换为二叉树的过程！树、森林的遍历： 先根遍历：拜访根结点；依次先根遍历根结点的每棵子树； 后根遍历：依次后根遍历根结点的每棵子树；拜访根结点；争论：树如采纳“ 先转换,后遍历” 方式,结果是否一样？1. 树的先根遍历与

32、二叉树的先序遍历相同；2. 树的后根遍历相当于二叉树的中序遍历；3. 树没有中序遍历,由于子树无左右之分； 先序遍历 如森林为空,返回；拜访森林中第一棵树的根结点；先根遍历第一棵树的根结点的子树森林；先根遍历除去第一棵树之后剩余的树构成的森林； 中序遍历 如森林为空,返回；中根遍历森林中第一棵树的根结点的子树森林；拜访第一棵树的根结点；中根遍历除去第一棵树之后剩余的树构成的森林；名师归纳总结 - - - - - - -第 15 页,共 29 页精选学习资料 - - - - - - - - - 二叉树的应用：哈夫曼树和哈夫曼编码；Huffman 树：最优二叉树（带权路径长度最短的树）Huffma

33、n 编码：不等长编码；树的带权路径长度：（树中全部叶子结点的带权路径长度之和）构造 Huffman 树的基本思想：权值大的结点用短路径,权值小的结点用长路径；构造 Huffman 树的步骤（即 Huffman 算法）：1 由给定的 n 个权值 w1, w2, , wn 构成 n 棵二叉树的集合 F = T1, T2, , Tn （即森林）,其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点,其左右子树均空；2 在 F 中选取两棵根结点权值最小的树做为左右子树构造一棵新的二叉树,且让新二叉树根结点的权值等于其左右子树的根结点权值之和；3 在 F 中删去这两棵树,同时将新得到的二叉树加入 F

34、中；4 重复 2 和3 , 直到 F 只含一棵树为止；这棵树便是 Huffman 树；详细操作步骤：学习重点：（本章内容是本课程的重点）二叉树性质及证明方法,并能把这种方法推广到 K 叉树；二叉树遍历,遍历是基础,由此导出很多有用的算法,如求二叉树的高度、各结点的层次数、度为 0、1、2 的结点数；由二叉树遍历的前序和中序序列或后序和中序序列可以唯独构造一棵二叉树；由前序和后序序列不能唯独确定一棵二叉树；名师归纳总结 - - - - - - -第 16 页,共 29 页精选学习资料 - - - - - - - - - 完全二叉树的性质；树、森林和二叉树间的相互转换；哈夫曼树的定义、构造及求哈夫

35、曼编码；补充：1.满二叉树和完全二叉树有什么区分？答：满二叉树是叶子一个也不少的树,而完全二叉树虽然前k-1 层是满的,但最底层却答应在右边缺少连续如干个结点；满二叉树是完全二叉树的一个特例；2.Huffman 树有什么用？最小冗余编码、信息高效传输名师归纳总结 - - - - - - -第 17 页,共 29 页精选学习资料 - - - - - - - - - 第七章 图 内容提要：图的定义,概念、术语及基本操作；图：记为 G V, E 其中： V 是 G 的顶点集合,是有穷非空集；E 是 G 的边集合,是有穷集；术语：见课件图的储备结构；1.邻接矩阵 数组 表示法 建立一个顶点表和一个邻接

36、矩阵 设图A = V, E 有 n 个顶点,就图的邻接矩阵是一个二维数组A.Edgenn ；注：在有向图的邻接矩阵中,第 i 行含义：以结点 vi 为尾的弧 即出度边）；第 i 列含义：以结点 vi 为头的弧 即入度边）；邻接矩阵法优点：简洁实现图的操作,如：求某顶点的度、判定顶点之间是否有边（弧）、找顶点的邻接点等等；邻接矩阵法缺点：n 个顶点需要n*n 个单元储备边 弧;空间效率为On2；2.邻接表 链式 表示法 对每个顶点 vi 建立一个单链表,把与 vi 有关联的边的信息（即度或出度边）链接起来,表中每个结点都设为 3 个域 : 每个单链表仍应当附设一个头结点（设为 2 个域）,存 v

37、i 信息； 每个单链表的头结点另外用次序储备结构储备；邻接表的优点：空间效率高；简洁查找顶点的邻接点；邻接表的缺点： 判定两顶点间是否有边或弧,需搜寻两结点对应的单链表,没有邻接矩阵方便；图的遍历；沿着一些边,访遍图中全部的顶点,且使遍历定义：从已给的连通图中某一顶点动身,每个顶点仅被拜访一次,就叫做图的遍历,它是图的基本运算；图常用的遍历：一、深度优先搜寻；二、广度优先搜寻 深度优先搜寻（遍历）步骤： 拜访起始点 v; 如 v 的第 1 个邻接点没拜访过,深度遍历此邻接点； 如当前邻接点已拜访过,再找v 的第 2 个邻接点重新遍历；基本思想：仿树的先序遍历过程；名师归纳总结 - - - -

38、- - -第 18 页,共 29 页精选学习资料 - - - - - - - - - 广度优先搜寻（遍历）步骤： 在拜访了起始点v 之后,依次拜访v 的邻接点； 然后再依次（次序）拜访这些点（下一层）中未被拜访过的邻接点； 直到全部顶点都被拜访过为止；图的应用（最小生成树,最短路经）最小生成树（ MST ）的性质如下：如 U 集是 V 的一个非空子集,如 u0, v0是一条最小权值的边,其中 u0 U,v0 V-U；就： u0, v0必在最小生成树上；求 MST 最常用的是以下两种：Kruskal （克鲁斯卡尔）算法、Prim（普里姆）算法Kruskal 算法特点：将边归并,适于求稀疏网的最小生成树；Prime 算法特点 : 将顶点归并,与边数无关,适于稠密网；在带权有向图中A 点（源点）到达B 点（终点）的多条路径中,查找一条各边权值之和最小的路径