数据结构部分线性表树图幻灯片.ppt

《数据结构部分线性表树图幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构部分线性表树图幻灯片.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构部分线性表数据结构部分线性表树图树图第1页，共56页，编辑于2022年，星期六第一部分：线性结构第一部分：线性结构v一、线性表一、线性表最常见的一种线性结构，有两种存储方法：顺序存储和链式存储最常见的一种线性结构，有两种存储方法：顺序存储和链式存储1、定义定义：N个元素的有限序列，个元素的有限序列，n0，通常表示为（，通常表示为（a1,a2,an）2、特点特点：元素集合中存在唯一称作元素集合中存在唯一称作“第一个第一个”和唯一和唯一“最后一个最后一个”元素，除第一个元素外，元素，除第一个元素外，每个元素均只有一个直接前驱；除最后一个元素外，序列中的每个元素只有一个每个元素均只有一个直接

2、前驱；除最后一个元素外，序列中的每个元素只有一个直接后继。直接后继。3、存储结构存储结构：顺序存储结构顺序存储结构含义：用一组连续的存储单元存放线性表中的数据元素。含义：用一组连续的存储单元存放线性表中的数据元素。特点：逻辑相邻的元素，物理位置也相邻。特点：逻辑相邻的元素，物理位置也相邻。优点和缺点：存取方便，插入删除操作需要移动大量元素。优点和缺点：存取方便，插入删除操作需要移动大量元素。第2页，共56页，编辑于2022年，星期六第一部分：线性结构第一部分：线性结构.链式存储结构链式存储结构含义：含义：存储数据元素的同时必须存储元素之间的关系。用节点来存储数据元素，节点存储数据元素的同时必须

3、存储元素之间的关系。用节点来存储数据元素，节点地址可以连续，也可以不连续。地址可以连续，也可以不连续。节点结构：节点结构：节点的插入和删除操作节点的插入和删除操作 插入操作插入操作 删除操作删除操作 第3页，共56页，编辑于2022年，星期六第一部分：线性结构第一部分：线性结构4.其他几种链表结构其他几种链表结构：双向链表：双向链表：每个节点包含两个指针，分别指出当前节点元素的直接前驱和直接后继。每个节点包含两个指针，分别指出当前节点元素的直接前驱和直接后继。循环链表：循环链表：静态链表：静态链表：借助数组来描述线性表的链式存储结构借助数组来描述线性表的链式存储结构第4页，共56页，编辑于20

4、22年，星期六第一部分：线性结构第一部分：线性结构v二、栈和队列二、栈和队列1.栈栈定义定义只能通过它的一端来实现数据存储和检索的只能通过它的一端来实现数据存储和检索的线性结构，也称为后进先出（或先进后出）的线性结构，也称为后进先出（或先进后出）的线性表。线性表。基本运算基本运算初始化栈：初始化栈：InitStack(S)判栈空判栈空:StackEmpty入栈入栈:Push(S,x)出栈出栈:Pop(S)读栈顶元素读栈顶元素:Top(s)存储结构存储结构顺序存储顺序存储：（顺序栈）指用一组地址连续的存储单元依次存储自栈顶到：（顺序栈）指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同

5、时附设指针栈底的数据元素，同时附设指针top指示栈顶元素的位置。指示栈顶元素的位置。第5页，共56页，编辑于2022年，星期六第一部分：线性结构第一部分：线性结构链式存储链式存储（链栈）：为了克服（链栈）：为了克服顺序栈可能存在上溢的不足，采顺序栈可能存在上溢的不足，采用钻链表作为存储结构的栈。用钻链表作为存储结构的栈。栈的应用：表达式求值，括号匹配，递归转非递归。栈的应用：表达式求值，括号匹配，递归转非递归。2.队列队列定义：是一种先进先出（定义：是一种先进先出（FIFO）的线性表，只允许在表的一端插入元素，表的另一端删除元素。）的线性表，只允许在表的一端插入元素，表的另一端删除元素。基本运

6、算：基本运算：(1)初始化队初始化队 InitQueue(Q)(2)判队空判队空 Empty(Q)(3)入队入队 EnQueue(Q,x)(4)出队出队 DeQueue(Q)(5)读队头元素读队头元素 FrontQue(Q)第6页，共56页，编辑于2022年，星期六第一部分：线性结构第一部分：线性结构队列的存储结构队列的存储结构顺序存储（顺序队列）顺序存储（顺序队列）利用一组地址连续的存储单元存放队列中的元素，同时设置队头指针和队尾利用一组地址连续的存储单元存放队列中的元素，同时设置队头指针和队尾指针，分别表示当前的队首元素和队尾元素。指针，分别表示当前的队首元素和队尾元素。思考思考:(1)为

7、什么要引入为什么要引入循环队列？循环队列？(2)什么叫假溢出？如何形成的？什么叫假溢出？如何形成的？链式存储（链队列）链式存储（链队列）队列的应用：队列的应用：常用于需要排队的场合：比如操作系统中处理打印任务，离散事件的计算模拟等。常用于需要排队的场合：比如操作系统中处理打印任务，离散事件的计算模拟等。第7页，共56页，编辑于2022年，星期六第一部分：线性结构第一部分：线性结构3 串串 即字符串，是一种特殊的线性表，它的数据元素仅由一个字符组成。即字符串，是一种特殊的线性表，它的数据元素仅由一个字符组成。串的串的定义定义是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为：是仅由字符构

8、成的有限序列，是取值范围受限的线性表。一般记为：S=a1a2an，其中，其中S是串名，单引号括起来的字符序列是串值。是串名，单引号括起来的字符序列是串值。几个相关的几个相关的基本概念基本概念空串：长度为零的串，不包含任何字符。空串：长度为零的串，不包含任何字符。空格串：由一个或多个空格组成的串。空格串：由一个或多个空格组成的串。子串：由串中任意长度的连续字符构成的序列称为子串。空串是任意串的子串。子串：由串中任意长度的连续字符构成的序列称为子串。空串是任意串的子串。串相等：两个串长度相等，且对应位置上的字符也相同。串相等：两个串长度相等，且对应位置上的字符也相同。串比较：比较大小时，以串比较：

9、比较大小时，以ASCII码值作为依据。码值作为依据。基本操作基本操作赋值赋值strAssign(s,t):将串将串t赋给串赋给串s连接连接Concat(s,t):串串t接续在串接续在串s的尾部，形成一个新串。的尾部，形成一个新串。第8页，共56页，编辑于2022年，星期六第一部分：线性结构第一部分：线性结构求串长求串长StrLength(s)串比较串比较StrCompare(s,t)返回值返回值-1、0、1分别表示分别表示st求子串求子串SubString(s,start,len)串的串的存储结构存储结构静态存储静态存储(即串的顺序存储结构即串的顺序存储结构)用一组地址连续的存储单元来存储串值

10、的字符序列。（在程序设计语言中可借助字符数组定义串的用一组地址连续的存储单元来存储串值的字符序列。（在程序设计语言中可借助字符数组定义串的存储空间）。存储空间）。链式存储链式存储 用链表存储串中的字符，每个节点中可以存储一个字符，也可以存储多个字符，注意存储密用链表存储串中的字符，每个节点中可以存储一个字符，也可以存储多个字符，注意存储密度问题度问题,因为它直接影响到串和处理效率。因为它直接影响到串和处理效率。串的串的模式匹配模式匹配即子串的定位操作，是各种串处理中最重要的运算之一。有以下两种算法：即子串的定位操作，是各种串处理中最重要的运算之一。有以下两种算法：（1）朴素模式匹配算法）朴素模

11、式匹配算法基本思想：基本思想：P432（2）改进的模式匹配算法）改进的模式匹配算法基本思想：基本思想：P433第9页，共56页，编辑于2022年，星期六第一部分：线性结构第一部分：线性结构4 数组、矩阵和广义表数组、矩阵和广义表（1）数组）数组定义定义：线性表的元素又是一个线性表，是定长线性表在维数上的一个扩张。：线性表的元素又是一个线性表，是定长线性表在维数上的一个扩张。特点特点：.数据元素数目固定数据元素数目固定 .数据元素具有相同数据类型数据元素具有相同数据类型 .数据元素的下标关系具有上下界的约束且下标有序数据元素的下标关系具有上下界的约束且下标有序两个两个基本运算基本运算 其一：给定

12、一组下标，存取相应的数据元素；其一：给定一组下标，存取相应的数据元素；其二：给定一组下标，修改相应的数据元素中某个数据项的值。其二：给定一组下标，修改相应的数据元素中某个数据项的值。存储结构存储结构由于数组一般不作插入和删除运算，所以数组中数据元素个数和元素之间的由于数组一般不作插入和删除运算，所以数组中数据元素个数和元素之间的关系固定不变，因此适合采用顺序存储结构。关系固定不变，因此适合采用顺序存储结构。.二维数组的存储方式有两种：二维数组的存储方式有两种：行优先：行优先：列优先：列优先：第10页，共56页，编辑于2022年，星期六第一部分：线性结构第一部分：线性结构（2）矩阵）矩阵在数据结

13、构中，我们研究的是如何存储矩阵中的元素。在数据结构中，我们研究的是如何存储矩阵中的元素。特殊矩阵特殊矩阵 指矩阵中的元素分布有一定的规律的矩阵。例如：对称矩阵、三角矩阵、对指矩阵中的元素分布有一定的规律的矩阵。例如：对称矩阵、三角矩阵、对 角矩阵。角矩阵。存储时，可以将其压缩存储在一维数组中，并建立起每个非零元素在矩阵中的位置与其存储时，可以将其压缩存储在一维数组中，并建立起每个非零元素在矩阵中的位置与其一维护数组中的位置之间的对应关系。一维护数组中的位置之间的对应关系。稀疏矩阵稀疏矩阵非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律。非零元素的个数远远少于零元素的个数，且非零元素

14、的分布没有规律。第11页，共56页，编辑于2022年，星期六第一部分：线性结构第一部分：线性结构5 广义表广义表定义定义 是线性表的推广一，由零个或多个单元素或子表所组成的有限序列。一般记为：是线性表的推广一，由零个或多个单元素或子表所组成的有限序列。一般记为：LS=（a1,a2,an）其中）其中ai(1=i=0）个节点的有限集合，当）个节点的有限集合，当n=0时，称为空树，在任一非空树中：时，称为空树，在任一非空树中：（1）有且仅有一个称为根的节点；）有且仅有一个称为根的节点；（2）其余节点可分为）其余节点可分为m(m=0)个互不相交的有限集个互不相交的有限集T1、T2、Tm,其中其中Ti又

15、都是一棵树，又都是一棵树，并且乐为根节点的子树。并且乐为根节点的子树。（递归定义）（递归定义）2、树的基本概念、树的基本概念 与树相关的概念有：与树相关的概念有：双亲、孩子、兄弟双亲、孩子、兄弟节点的度、叶子节点、节点的层次、树的高度、有序（无序）树节点的度、叶子节点、节点的层次、树的高度、有序（无序）树 3、树的遍历、树的遍历 按照某种次序，获取树中全部节点的信息。按照某种次序，获取树中全部节点的信息。第13页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构（二）二叉树的定义及基本运算、（二）二叉树的定义及基本运算、1、二叉树的定义：、二叉树的定义：二叉树或为空树；

16、空树；或是由一个根结点根结点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。2、二叉树的运算、二叉树的运算 二叉树的基本运算是遍历，其它运算都是建立在遍历的基础之上。二叉树的基本运算是遍历，其它运算都是建立在遍历的基础之上。第14页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构（三）二叉树的性质（共五个性质）（三）二叉树的性质（共五个性质）1、在二叉树的第在二叉树的第 i 层上至多有层上至多有2i-1 个结点。个结点。(i1)2、深度为深度为 k 的二叉树上至多含的二叉树上至多含 2k-1 个结点（个结点（k1）3、对任何一棵二叉树，若

17、它含有、对任何一棵二叉树，若它含有n0 个叶子结点、个叶子结点、n2 个度为个度为 2 的结点，则必的结点，则必存在关系式：存在关系式：n0=n2+1 两类两类特殊特殊的二叉树：的二叉树：满二叉树：满二叉树：指的是深度为指的是深度为k且含有且含有2k-1个结点的二叉树个结点的二叉树。完全二叉树完全二叉树：树中所含的：树中所含的 n 个结点和满二叉树中编号为个结点和满二叉树中编号为 1 至至n 的结点一的结点一 一对应。一对应。4、具有具有 n 个结点的完全二叉树的个结点的完全二叉树的深度深度为为 log2n +1第15页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构

18、5、若对含若对含 n 个结点的完全二叉树从上到下且从左至右进行个结点的完全二叉树从上到下且从左至右进行 1 至至 n 的编号，则的编号，则对完全二叉树中任意一个编号为对完全二叉树中任意一个编号为 i 的结点：的结点：(1)若若 i=1，则该结点是二叉树的根，无双亲，则该结点是二叉树的根，无双亲,否则，编号为否则，编号为 i/2 的结点为其双亲结的结点为其双亲结点点;(2)若若 2in，则该结点无左孩子，则该结点无左孩子，否则，编号为否则，编号为 2i 的结点为其左孩子结点；的结点为其左孩子结点；(3)若若 2i+1n，则该结点无右孩子结点，则该结点无右孩子结点，否则，编号为否则，编号为2i+1

19、 的结点为其右孩子结点。的结点为其右孩子结点。第16页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构(四四)二叉树的存储结构二叉树的存储结构1、顺序存储结构顺序存储结构 (1)存储存储要求要求：用一组地址连续的存储单元存储二叉树中的数据元素，节点必须排用一组地址连续的存储单元存储二叉树中的数据元素，节点必须排成线性序列，并且该序列能反映出节点之间的逻辑关系。成线性序列，并且该序列能反映出节点之间的逻辑关系。(2)完全二叉树的存储完全二叉树的存储 完全二叉树的存储完全二叉树的存储 一般二叉树的存储一般二叉树的存储 二者二者比较比较得知：对于一般的二叉树，不宜采用顺序存

20、储结构，对于完全得知：对于一般的二叉树，不宜采用顺序存储结构，对于完全二叉树，采用顺序存储结构既简单，又节省空间二叉树，采用顺序存储结构既简单，又节省空间第17页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构2、链式存储结构链式存储结构 可以采用二叉链表或三叉链表来存储二叉树。可以采用二叉链表或三叉链表来存储二叉树。ABDCEF第18页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构(五五)二叉树的遍历二叉树的遍历1、遍历的、遍历的含义含义：指按照某种策略访问树中的每个节点，且仅访问一次。遍历过程的实质指按照某种策略访问树中的每个节点，且仅

21、访问一次。遍历过程的实质是：将树中的节点排成一个线性序列的过程。是：将树中的节点排成一个线性序列的过程。2、常见几种遍历常见几种遍历：先序先序遍历算法遍历算法 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）访问根结点；）访问根结点；（2）先序遍历左子树；）先序遍历左子树；（3）先序遍历右子树）先序遍历右子树。void PreOrder(BiTree root)if(root!=null)return;elseprintf(“%d”,root-data);PreOrder(root-lchild);PreOrder(roolt-rchild);第19页，共56页，编辑于2

22、022年，星期六第二部分第二部分 非线性结构非线性结构中序中序遍历算法：遍历算法：若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）中序遍历左子树；）中序遍历左子树；（2）访问根结点；）访问根结点；（3）中序遍历右子树）中序遍历右子树 void InOrder(BiTree root)if(root=null)return;else InOrder(root-lchild);printf(“%d”,root-data);InOrder(root-rchild);第20页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构后序后序遍历算法：遍历算法：若二

23、叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）后序遍历左子树；）后序遍历左子树；（2）后序遍历右子树；）后序遍历右子树；（3）访问根结点。）访问根结点。void PostOrder(BiTree root)if(root=null)return;else PostOrder(root-lchild);PostOrder(root-rchild);printf(“%d”,root-data);第21页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构层次层次遍历算法：遍历算法：从树的根结点出发，首先访问第一层的树的根结点，然后从左到右依次访问从树的根结

24、点出发，首先访问第一层的树的根结点，然后从左到右依次访问第二层上的节点，其次是第三层上的节点第二层上的节点，其次是第三层上的节点依次类推，自上而下，自左至依次类推，自上而下，自左至右，逐层访问树中各层上的节点。右，逐层访问树中各层上的节点。层次遍历序列层次遍历序列：A B E C F D G H K第22页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构(六六)线索二叉树线索二叉树1、定义、定义 二叉树的遍历实质：对非线性结构进行线性化操作，使得每个结点二叉树的遍历实质：对非线性结构进行线性化操作，使得每个结点（除第一个和最后一个结点外）在线性序列中有且仅有一个直接前

25、驱和（除第一个和最后一个结点外）在线性序列中有且仅有一个直接前驱和直接后继。直接后继。由于二叉链表的存储结构中，只能找到结点的左、右孩子的信息，由于二叉链表的存储结构中，只能找到结点的左、右孩子的信息，得不到前驱和后继信息，因此引入线索二叉树保存遍历过程中得到的得不到前驱和后继信息，因此引入线索二叉树保存遍历过程中得到的前驱和后继信息。前驱和后继信息。2、建立线索二叉树、建立线索二叉树第23页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构第24页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构对线索链表中结点的对线索链表中结点的约定：约定：

26、在二叉链表的结点中在二叉链表的结点中增加两个标志域增加两个标志域，并作如下规定：，并作如下规定：若该结点的左子树不空，则若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为域的指针指向其左子树，且左标志域的值为“指指针针 Link”；否则否则,Lchild域的指针指向其域的指针指向其“前驱前驱”，且左标志的值为，且左标志的值为“线索线索Tread”。若该结点的右子树不空，则若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的指针指向其右子树，且右标志域的值为域的值为“指针指针 Link”；否则，否则，rchild域的指针指向其域的指针指向其“后继后继”，

27、且右标志的值为，且右标志的值为“线索线索 Thread”。如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线索链表线索链表”第25页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构 思考：画出下列二叉树的中序线索二叉树及其中序线索链表。思考：画出下列二叉树的中序线索二叉树及其中序线索链表。第26页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构(七七)二叉树的应用：最优二叉树二叉树的应用：最优二叉树1.哈夫曼树（1）相关概念：结点的路径长度结点的路径长度：从根结点到该结点的路径上分支的数目。树的路径长度树的路径长度：树中每个结点

28、的路径长度之和。树的带权路径长度树的带权路径长度定义为：树中所有叶子结点的带权路径长度结点的带权路径长度之和 WPL(T)=WkLkWPL(T)=72+52+23+43+92 =60第27页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构(2)如何构造最优二叉树（Huffuman算法）根据给定的 n 个权值 w1,w2,wn，构造 n 棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值 为 wi 的根结点,其左、右子树为空树;在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其

29、左、右子树根结点的权值之和;WPL(T)=74+94+53+42+21 =89 第28页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构 从F中删去这两棵树，同时加入刚生成的新树。重复(2)和(3)两步，直至 F 中只含一棵树为止。(3)举例：已知权值 W=5,6,2,9,7 构造一棵哈夫曼树。步骤如下：（右图为哈夫曼编码）第29页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构（八）树和森林1、树的存储结构（三种表示方法）(1)双亲表示法：双亲表示法：第30页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构(2)孩

30、子表示法孩子表示法第31页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构第32页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构2、树和林林的遍历（1）树的遍历：先根遍历后根遍历（2）森林的遍历先序遍历中序遍历3、树、森林和二叉树之间的相互转换 （1）树、森林转换为二叉树 利用孩子兄弟法实现转换（P454例）（2）二叉树转换为树和森林（P454例）第33页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构v三、图三、图（一）图的定义与图相关的概念有：有向图/无向图：无向完全图/有向完全图：度、出度和入度：路径：从一个

31、顶点到另一个顶点的顶点序列子图：连通图与连通分量：强连通图与强连通分量：网：带权值的图有向树：有向图恰有一个顶点的入度为0，其余顶点的入度为1.第34页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构(二)图的存储结构1、邻接矩阵表示法：无向图邻接矩阵第35页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构第36页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构2、邻接表表示法第37页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构有向图逆邻接表 在有向图的邻接表中，对每个顶点，链接的是指向

32、该顶点的弧。第38页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构（三）图的遍历（三）图的遍历1、深度优先（DFS）遍历算法：从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。例子：第39页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构2、广度优先遍历（BFS）遍历算法：从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到

33、。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。第40页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构(四)生成树及最小生成树1、生成树的概念 一个连通图的生成树是一个极小连通子图，它包含图中的全部顶点，但只有构成一棵树的n-1条边。按深度和广度优先搜索可以分别得到不同的生成树，分别称为深度优先生成树深度优先生成树和广度优先生成树广度优先生成树。上面图的深度优先生成树和广度优先生成树分别如下：第41页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构 深度优先生成树 广度优先

34、生成树第42页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构2、最小生成树 由于生成树不唯一，从不同顶点出发可得到不同的生成树，因此如何求解最小生成树有许多实际应用价值。常见的最小生成树算法有两种：、（1）普里姆算法（Prim）基本思想基本思想：取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。第43页，共56页，编辑于2022年，星期六第二部分第二部分

35、非线性结构非线性结构 举例第44页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构（2）克鲁斯卡尔算法(kruskal)基本思想基本思想：考虑问题的出发点考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。具体做法具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。算法举例第45页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构举例（2）两种算法比较：第46页，共56页，编辑于2022年

36、，星期六第二部分第二部分 非线性结构非线性结构（五）拓扑排序和关键路径1、拓扑排序拓扑排序 （1）问题的提出:假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。（2）什么叫拓扑排序 对有向图进行如下操作:按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列拓扑有序序列第47页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构第48页，共56页，编辑于2022年，星期六第二部分第二部分

37、 非线性结构非线性结构（3）如何进行了拓扑排序？）如何进行了拓扑排序？第49页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构结论：第50页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构2、关键路径（1）问题的提出 假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。第51页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构（2）第52页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构v（3）举例第53页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构（六）最短路径1、单源点最短路径第54页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构 算法思想：P466 举例P4672、每对顶点之间的最短路径第55页，共56页，编辑于2022年，星期六第二部分第二部分 非线性结构非线性结构第56页，共56页，编辑于2022年，星期六