经贸大学2016年数据结构总复习【PPT课件】

数据结构 总复习 第一章 绪论 重点内容 逻辑结构和物理结构 顺序存储和链式存储 算法的五个特性 算法的时间复杂度 逻辑结构：数据元素之间的逻辑关系。 物理结构（存储结构）：数据结构在计算机中的表示，包括数据元素的表示和关系的表示。 3 基本概念和术语 顺序存储结构 ： 用数据元素在存储器中的 相对位置 来表示数据元素之间的逻辑结构 (关系 )。 数据元素存放的地址是连续的 链式存储结构：借助指示元素存储地址得指针表示数据之间的逻辑关系。 数据元素存放的地址是否连续没有要求 4 基本概念和术语 5 顺序存储 以存储位置的相邻表示后继关系 链式存储 以附加信息 (指针 )表示后记关系，需要用一个和 x y 基本概念和术语 y x 算法是为了解决某类问题而给出的一个有限长的 指令序列 。 算法有以下 5个特性： 有穷性：有穷步骤，每步都有有穷的时间 确定性：每条指令有确定的含义 可行性：是能行的，基本运算的有限次运算完成 输入： 0个或多个输入，取自某个特定对象集合 输出：一个或多个输出，同输入有某些特定关系 6 算法与算法分析 一个“好”的算法需满足： 7 算法与算法分析 正确 性 程序 中不含语法错误； 程序对于几组给定的输入可得到满足要求的结果 程序对于精心挑选的、典型的输入也可得到满足要求的结果 程序对于一切合法的输入均可以得出满足要求的结果 8 算法与算法分析 可读 性 算法主要是为 了人的阅读与交流 ， 其次才是为计算机执 行 。 因此算法应该易于人的 理解 ； 另 一方面，晦涩难读的程序易于隐藏较多错误而难以调试和修改。 9 算法与算法分析 健壮性 当 输入 的数据非法 时，算法应当给予 恰当的反应或进行相应的处理 ，而不是产生系统错误或莫名其妙的结果 。 处理出错 的方法不应是中断程序的执行， 而应该返回错误提示 ，以便在更高抽象层次上进行处理 。 10算法与算法分析 假设，随着问题规模 法执行时间的增长率和 f(n)的增长率相同，则可记作：T(n)=O(f(n) 称 T(n)为算 法的（渐进）时间复杂度 11算法与算法分析 原操作 ： 固有数据类型的操作。 （如： +， -， ，/， ， 因此， 链表不是随机存取结构 设单链表的长度为 n，要查找表中第 当 1 i 单链表的插入 实现步骤 ： 首先，找到 结点 p 然后，生成一个数据域为 s， 为 b p a b p a e s s-e; s-p- p-s; 单链表的删除 实现步骤 ： 首先找到 p； 然后令 p把 最后释放结点 ai p q=p-p-q- e=q- q); 静态链表 0 1 1 2 3 4 5 6 7 8 9 10 0 1 1 2 3 4 5 6 7 8 9 10 0 1 1 2 3 4 5 6 7 8 9 10 修改前 在第 5个位置插入 除 环链表 循环链表 (是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结点， 整个链表的指针域链接成一个环 。 从循环链表的 任意一个结点出发 都可以找到链表中的其它结点，使得表处理更加方便灵活。 空表 非空表 an 向链表的插入 S e p a b S e p a b 双向链表的插入 算法主要语句 S=(); S-e; S-p- p-; S-p; p-; 设要删除 的结点为 p ，删除时直接先断链 ，再释放结点。部分语句组如下： p-p-p-p-p); 与单链 表的插入和删除操作不同的是，在双向链表中 插入 和 删除 必须同时 修改两个方向上的指针域的指向 。 双向链表的删除 a1 a2 a3 p 优点 ：易于查询，索引快 缺点 ：扩展性弱，不易删除、添加。 优点 ：扩展性强，易于删除、添加 缺点 ：不易于查询，索引慢 二者优缺点正好是互补关系，根据实际情况选择使用 顺序存储与链式存储的对比 第三章 栈和队列 重点内容 栈和队列逻辑结构的特点 顺序栈的栈满、栈空判断 循环队列的满与空的判断 压栈、出栈算法 进队列、出队列算法 栈 (限制在表尾进行插入和删除操作的线性表。又称为后进先出 n 栈顶 (允许进行插入、删除操作的一端 栈底 (是固定端，又称为表头。 空栈 ： 满栈 : a1 a2 栈顶 栈底 进栈(出栈 ( 采用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素： 用 底固定不变的；栈顶则随着进栈和退栈操作而变化。 用 为栈顶指针 )指示当前栈顶位置。 用 每次 结点进栈 ：首先将数据元素保存到栈顶 (，然后执行 ，使 结点出栈 ：首先执行 ，使 后将栈顶元素取出 。 空栈 素 a 元素 b， a b c 元素 a b a b d e f 元素 d， e， 3 元素进栈 , e) /* 使数据元素 */ ( = /栈满 ) (* ! *=e ; /* 栈顶指针加 1 */ K; /* 压栈成功 */ 4 弹栈 (元素 出栈 ) &S, &e ) /*弹出栈顶元素 */ /* 栈空，返回错误标志 */ e=*K ; 队列 队列 (也是运算受限的线性表。是 一种先进先出 (n 简称 线性表。 只允许在表的一端进行插入，而在另一端进行删除 队头 (： 允许进行删除的一端称为队头。 队尾 (：允许进行插入的一端称为队尾。 , a n 出队 入队 队尾 队头 链 队列 队列的链式存储结构简称为链队列 它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。 需要两类不同的结点： 数据元素 结点，队列的 队首指针和队尾指针 的结点 a) 空队列 (b) x c) y x (d) y x 队列 设立一个队首指针 一个队尾指针 分别指向队首和队尾元素 。 初始化 ： 。 入队 ： 将新元素插入 后 。 出队 ： 删去 后加 1并返回被删元素。 队列为空 ： 队满 ： 序 队列 (a) 空队列 b) 入队 3个元素 a3 a2 c) 出队 3个元素 d) 入队 2个元素 a5 序队列 将新元素插入 后 删去 后加 1并返回被删元素 队列已满，但仍有存储空间 充分利用向量空间 ，克服上述“假溢出”现象 将为队列分配的向量空间看成为一个首尾相接的圆环，并称这种队列为 循环队列 循环队列 1 2 3 4 5 0 循环 队列 2 3 4 5 0 (a) 空队列 b) d, e, b, d e b g c) d, b g d) i, j, b g i j k e) b, i j k f) r, p, s, i j k r p 环队列 Q , e) /* 将数据元素 的队尾 */ ()% /* 队满，返回错误标志 */ . e ; /* 元素 */ () % /* 队尾指针向前移动 */ K; /* 入队成功 */ 循环队列 循环队列 Q, &e) /* 将循环队列 */ ( /* 队空，返回错误标志 */ e = ; /* 取队首元素 */ ()% /* 队首指针向前移动 */ K ; 第四章 串 重点内容 串的基本概念 串 (字符串 )：是零个或多个字符组成的有限序列 。记作 ： S= 其 中 i n)是单个， 可以是字母、数字或其它字符。 串值 ：双引号括起来的字符序列是串值。 串长 ：串中所包含的字符个数称为该串的长度。 空串 (空的字符串 )： 长度为零 的串称为空串，它不包含任何字符。 空 格串 (空白串 )：构成串的所有 字符都是空格 的串称为空白串。 注意 ：空串和空白串的不同，例如 和分别表示长度为 1的空白串和长度为 0的空串。 第五章 数组和广义表 重点内容 稀疏矩阵的压缩存储 广义表的基本概念、求表头、表尾操作 两种顺序存储方式 行优先顺序 (： 将数组元素按行排列，第i+1个行向量紧接在第 二维数组，按行优先顺序存储的线性序列为： ,a 1n, a 2n , a m1, 列优先顺序 (： 将数组元素按列向量排列，第 j+1个列向量紧接在第 二维数组，按列优先顺序存储的线性序列为： ,a a , a n1, 组的顺序表示和实现 = (a) 二维数组的表示形式 (b) 行优先顺序存储 (c) 列 优先顺序存储 1 行 2 行 第 m 行 1 列 2 列 n 列 给每一对对称 元素 ij)分配 1个存储空间 ，则n(n+1)/2个存储空间 假设按 行优先顺序 存储下三角形中的元素。 设用一维数组 (向量 )n(n+1)/2 存储 为便于访问，找出矩阵 i,j） 和向量 sak的 下标值 1 2 3 4 n(2 n(n+1)/2 对称矩阵的 压缩存储示例 广义表 (称为列表 )：是由 n(n 0)个元素组成的有穷序列： ， 中第一个元素 )称为 表头 ； 其余元素组成的子表称为 表尾 ； ( ， 广义表中所包含的元素 (包括原子和子表 )的个数称为 表的长度 。 广义表中括号的最大层数称为表深 (度 )。 义表的定义 第六章 树和二叉树 重点内容 树和二叉树的定义及相关概念 二叉树的 5个性质 二叉树的各种存储结构 树的各种存储结构 二叉树的各种遍历方法、中序遍历算法 线索二叉树的画法 树的两种遍历方法 哈夫曼树的构造、哈夫曼编码方法 树 的 基本术语 结点 (数据元素 若干指向其子树的分支 结点的度 (：结点所拥有的子树的个数称为结点的度 。 树 的度： 树中结点度的 最大值 。 A A B D C E G F H I M J N K L 只有根结点 树的基本术语 叶子结点 ： 即度为 0的结点 分支结点 ： 除叶子结点之外的其它结点 孩子 ( 若结点 子树的根结点是 双亲 ( 若 该 A B D C E G F H I M J N K L 树的基本术语 兄弟结点 ： 同一个双亲的孩子结点 祖先结点 ： 从根结点到该结点所经 路径 上的所有结点。 子孙结点 ： 以某个结点为根的子树 中的任何一个结点都称为该结点的子孙结点 结点的 层次 ：从根开始定义，根为第 1层，根的孩子为第 2层 堂兄弟 ： 双亲结点在同一层上 A B D C E G F H I J 树的基本术语 有序树 ： 树中各个节点的子树 2， 之间是 有次序的 ，即为有序树。即各个子树之间的左右次序不能互换 无序树 ： 树中各个节点的子树 2， 之间 没有次序关系 的，即为无序树。 60A B C D E A C B D E 树的基本术语 树的深度 ： 树中节点的 最大层次， 也称为树的高度或深度。 61A B C D D E F H I J K L M 第 1层 第 2层 第 3层 第 4层 62二叉树的定义 二叉树或者为空树 或是由一个根结点加上两棵分别称为 左子树和 右子树 的、 互不相交 的二叉树组成。 叉树 E G B E F A A A A A (a) (b) (c) (d) (e) 叉树 二叉树有 5种基本形态： 二叉树的特点： 1）每个结点的度 1，则其双亲结点 i) 的编号是 i/2 。 如果 2in，则编号为 i 的结点无左孩子（编号为 i 的结点为叶子结点）；否则其左孩子结点 i)的编号是 2i 。 如果 2i+1n，则编号为 i 的结点无右孩子；否则其右孩子结点 i) 的编号是结点 2i+1。 叉树 i i+1 2i 2i+1 2i+2 2i+3 i/2 (a) i和 i+1结点在同一层 i+1 2i+2 2i+3 i 2i 2i+1 (b) i和 i+1结点不在同一层 顺序存储结构 二叉树存储结构的类型定义： # 100 用一组地址连续的存储单元依次 “ 自上而下 、 自左至右 ” 存储完全二叉树 的数据元素 。 对于完全二叉树上 编号为 对于一般的二叉树， 将其每个结点与完全二叉树上的结点相对照 ， 存储在一维数组中 叉树 a b c d h i e j k l f g (a) 完全二叉树 (b) 非完全二叉树 a b c d e f g h 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 a b c d e f g h i j k l (c) 完全二叉树的顺序存储形式 0 1 2 3 4 5 6 7 8 9 10 a b c d e 0 h 0 0 f g (d) 非完全二叉树的顺序存储形式 叉树 最坏的情况下，一个深度为 链式存储结构 二叉链表 。 结点有三个域： 一个数据域 ，两个分别指向左右子结点的 指针域 * * 叉树 a) 二叉链表结点 三 叉链表 除二叉链表的三个域外，再增加一个指针域， 用来指向 结点的父结点 * * * 叉链表结点 叉树 (2) 二叉树的链式存储形式 (a) 二叉树 a f e d c b g (c) 三 叉链表 a b c d e f g T (b) 二 叉链表 a b c d e g f T 叉树 1 双亲表示法 ; r， n; / 根结点位置，结 点数 F G H I R A B C D E 树的双亲存储结构 R A 0 1 B 0 2 C 0 3 D 1 4 E 1 5 F 3 6 G 6 7 H 6 8 I 6 9 r=0 n=10 这种存储结构利用了任一结点的双亲结点唯一的性质。 可以方便地直接找到任一结点的双亲 但求结点的孩子结点时需要扫描整个数组。 树的存储结构 8 9 3 5 0 1 2 6 0 1 2 3 4 5 6 7 8 9 r n A B C D E F G H I R 4 10 孩子链表存储结构 孩子链表表示法 F G H I R A B C D E (b) 树 F G R A B C D E (c) 孩子兄弟存储结构 R A D C G B F E 孩子结点 兄弟结点 a) 结点结构 3 孩子兄弟表示法 先左 后右的遍历算法 先 (根 )序 的遍历 算法 中 (根 )序 的遍历 算法 后 (根 )序 的遍历 算法 7根 左 子树 右 子树 历二叉树和线索二叉树 历二叉树和线索二叉树 遍历序列可否唯一确定一棵二叉树？ 先序序列： 序序列： B C I D E F G H J 遍历二叉树 的结果是求得结点的一个线性序列 。 指向该线 性序列中的前驱和后继的指针，称作 线索 。 包含 线索的 存储结构 称作 线索链表 ；与其相应的二叉树，称为 线索二叉树 。 历二叉树和线索二叉树 A F H I E G B D C A F H I E G B D C 序遍历结点序列： F H I E G B D C (a) 二叉树 (b) 先序线索树的逻辑形式 结点序列： F H I E G B D C d) 后序线索树的逻辑形式 结点序列： c) 中序线索树的逻辑形式 结点序列： F H I E G B D C F H I E G B D C 线索二叉树的指针信息存储在哪里？ 设一棵二叉树有 有 (指针连线 ) ， 而 ( ，显然 有 n+1个空闲指针域 未用。 可以利用这些空闲的指针域来存放结点的 直接前驱 和 直接后继 信息。 历二叉树和线索二叉树 对结点的指针域做如下规定： 若结点有左子树，则 0； 否则，指向其直接前驱， 1； 若结点有右子树，则 0； 否则，指向其直接后继， 1； 历二叉树和线索二叉树 索二叉树的结点结构 0： 1： 0： 1： 树和森林的遍历 1 树的遍历 由树结构的定义可知，树的遍历有二种方法。 (1) 先根序遍历 ：先访问根结点，然后 先序遍历完 每棵子树。 (2) 后根序遍历 ：先 依次后序遍历完 每棵子树，然后访问根结点。 A B D C K G J I F H E 先序遍历： 序遍历： 本概念 结点路径 ：从树中一个结点到另一个结点的之间的分支构成这两个结点之间的路径。 路径长度 ：结点路径上的分支数目称为路径长度 。 树的路径长度 ：从树根到每一个结点的路径长度之和 。 夫曼树及其应用 A B D C K G J I F H E ：结点路径 路径长度 (即边的数目 )： 2 ； 树的路径长度 ：31+52+23=19 结点的带权路径长度 ：从该结点的到树的根结点之间的路径长度与结点的权 (值 )的乘积 。 权 (值 )：各种 开销 、 代价 、 频度 等的抽象称呼 。 树的带权路径长度 ：树中 所有叶子结点 的带权路径长度之和，记做： w1l1+w2+wnwi (i=1,2,n) 其中： 具有 每个结点的权值为 的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵称这棵树为 或称最优树 ) 。 基本概念 根据 ,构造成 ,其中每棵二叉树只有一个权值为 有左、右子树； 在 取两棵根结点权值最小 的树作为左 、 右子树构造一棵新的二叉树，且新的二叉树根结点权值为其左 、 右子树根结点的权值之和； 在 时将新得到的树加入 重复、，直到 规定 F=2, , 权值小 的二叉树作为新构造的二叉树的 左子树 ， 权值大的二叉树作为新构造的二叉树的右子树 ； 在取值相等时， 深度小 的二叉树作为新构造的二叉树的 左子树 ， 深度大的二叉树作为新构造的二叉树的右子树 。 权值集合 W=8, 3, 4, 6, 5, 5构造 所构造的 2+33+43+82+53+53 =79 3 4 5 5 6 8 第一步 5 5 6 8 第二步 3 4 7 6 8 第三步 3 4 7 5 5 10 8 第四步 5 5 10 6 3 4 7 13 第六步 1 1 1 1 1 0 0 0 0 0 8 5 5 10 18 6 3 4 7 13 31 第五步 8 5 5 10 18 6 3 4 7 13 例子 在电报收发等数据通讯中 ， 常需要将传送的文字转换成由二进制字符 0、 1组成的字符串来传输 。 为了使收发的速度提高 ， 要求电文 编码要尽可能短 。 要设计 长短不等 的编码，还必须保证 任意字符的编码都不是另一个字符编码的前缀 ，称为 前缀编码 。 设电文中的字符集 C=c1,各个字符出现的次数或频度集 W=w1, 以 字符集 次数或频度集 的权值 来构造 规 定 0”，右分支代表 1” 。 从根结点到每个叶子结点所经历 的路径分支上的 0”或 1”所组成的字符串 ， 为该结点所对应的编码 ， 称之为 *由于每个字符都是叶子结点 ，不可能出现在根结点到其它字符结点的路径上，所以一个字符的 第七章 图 重点内容 图的定义及相关术语 图的各种存储结构 图的深度优先遍历和广度优先遍历法 图的最小生成树的概念 克鲁斯卡尔算法、普里姆算法生成最小生成树 图的拓扑排序、关键路径的求法 图的存储结构 图的数组存储表示法 基本思想 ： 对于 有 一维数组 n存储顶点信 息 用二维数组 Ann存储顶点之间关系的信 息 该二维数组称为 邻接矩阵 在邻接矩阵中 ： 以顶 点在 的下标代表顶点 邻接矩阵中的 元素 Aij存放的是 顶点 信 息 921 无向图的数组表示 (1) 无权图的邻接矩阵 无向无权图 G=(V， E)有 n(n 1)个顶点，其邻接矩阵是其元素的定义如下： 1 若 ( E，即 0 若 ( E，即 Aij= (a) 无向图 a b c d (b) 顶点矩阵 a b c d 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 (c) 邻接矩阵 (2) 带权图（网）的邻接矩阵 无向带权图 G=(V， E) 的邻接矩阵元素的定义如下： 带权无向图 邻接矩阵 3 5 4 1 2 6 a b c d e 3 a b c d e 6 2 6 3 4 3 2 3 1 4 3 5 3 5 若 ( E，即 值为 若 ( E，即 Aij= 特点： 1、无向图的邻接矩阵是 对称方阵 ； 2、顶点 第 0元素的个数 ； 3、 无向图的边数是上 (或下 )三角形矩阵中 非 0元素个数 。 952 有向图的数组表示 (1) 无权图的邻接矩阵 有向无权图 G=(V， E)有 n(n 1)个顶点，则其邻接矩阵是 素定义如下： 1 若 E，从 Aij= 0 若 E 从 有弧 (a) 有向图 a c b d e (b) 顶点矩阵 a b c d e (c) 邻接矩阵 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 (2) 带权图的邻接矩阵 有向带权图 G=(V， E)的邻接矩阵元素的定义如下： 若 E，即 值为 若 E，即 Aij= (b) 顶点矩阵 a b c d e (c) 邻接矩阵 6 2 3 3 1 4 5 (a) 带权有向图 3 5 4 1 2 6 a b c d e 3 特点： 1、 对于顶点 第 非 0元素的个数是其出度OD( 第 非 0元素的个数是其入度 ID(。 2、邻接矩阵中 非 0元素的个数就是图的 弧的数目 。 邻接链表法 基本 思想 ： 对图 的 每个顶点 建立一个 单链表 ，存储该顶点所有邻接顶点及其相关信息 。 每一个单链表设一个 表头结点 。 第 表示依附于顶点 (对有向图是以顶点 )。 1 结点结构与邻接链表示例 链表中的结点称为 表结点 ，表结点由三个域组 成： 邻 接点域：指示与顶点 的位置 链域：指向下一个与顶点 数据域：存储和边或弧相关 的信息，如权值等。 表头结点 (称为 顶点结点 )，由两个域组成： 链域：指向链表 中的第一个结点 数据域 ： 存储顶点名或其他信息。 结点 ： 头结点 ： 所有 顶点结点 用一个向量以顺序结构形式存储，可以随机访问任意顶点的链表，该向量称为 表头向量 向 量的下标指示 顶点的位置 ？ v1 v2 v3 v4 1 2 3 4 v2 2 1 3 0 2 0 3 1 4 2 0 4 2 3 无向图邻接表 有向图 v1 v2 v3 v4 3 0 1 4 2 3 0 1 2 3 4 v1 v3 邻接链表 出度直观 2 0 2 2 0 1 2 3 4 0 4 逆邻接链表 入度直观 有向图邻接表 有向图的邻接表有两种： 正邻接表 和 逆邻接表 正邻接表 是以顶点 立的邻接表 ； 逆邻接表 是以顶点 立的邻接表； 2 邻接表法的特点 表头向量中每个分量就是一个单链表的头结点， 分量个数就是图中的顶点数目 ； 在 边或弧稀疏 的情况下 ，用邻接表表示比用邻接矩阵表示节省存储空间； 在无向图， 顶点 在有向图中 ，第 (或入 )度；求入 (或出 )度，须遍历整个邻接表； 在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点 ； 要判定两个顶点 要搜索第 图的遍历 图 的遍历 (从图的某一顶点出发，访遍图中的其余顶点， 且每个顶点仅被访问一次 。图 的遍历算法是各种图操作的基础 。 复杂性： 图的任意顶点可能和其余的顶点相邻接，可能在访问了某个顶点后，沿某条路径搜索后又回到原顶点。 解决办法 ： 在遍历过程中记下已被访问过的顶点。设置一个辅助向量 n(，其初值为 0，一旦访问了顶点 i为 1或为访问的次序号 。 图 的遍历算法有 深度优先搜索算法 和 广度优先搜索算法 。 采用的数据结构 是 (正 )邻接链表 。 深度优先搜索算法 深度优先搜索 (历类似树的先序遍历 ，是 树的先序遍历的推广 。 1 算法思想 设初始状态时图中的所有顶点未被访问，则： 从图中某个顶点 访问 后找到 个邻接顶点 从 度优先搜索访问和 接 且 未被访问 的所有顶点； 转 ，直到和 接的所有顶点都被访问为止 继续选取图中未被访问顶点 (1)，直到图中所有顶点都被访问为止。 (a) 无向图 G v1 v2 v3 v4 b) 0 1 2 3 4 v2 2 1 2 0 0 1 4 3 无向图的深度优先搜索遍历示例。 某种 深度优先搜索算法 有向图的广度优先搜索遍历示例 。 上述图 的 b) G的正邻接链表 1 3 0 1 4 2 3 0 1 2 3 4 2 0 3 1 1 (a) 有向图 G v1 v2 v3 v4 广度优先搜索算法 构 造最小生成树的算法有许多，基本原则是： 尽可能选取权值最小的边，但不能构成回路； 选择 以上的基本原则是基于 设 G=(V， E)是一个带权连通图， 的一个非空子集。若 u U ， v (u, v)是 值最小的边 ， 则必存在一棵包含边 (u, v)的最小生成树 。 最小生成树 普里姆 (法 从连通网 N=(U， E)中找最小生成树 T=(U， 。 1 算法思想 若从顶点 U= ； 先找 权值最小 的边 (u， v)，其中 u U且 v 且子图不构成环，则 U= U v， E (u， v) ； 重复 ，直到 U= 则 T=(U，是最小生成树 。 v1 v3 v2 v4 8 5 7 12 11 3 6 (1) v2 (2) (3) v2 (4) v2 (5) v2 普里姆 (法 克鲁斯卡尔 (法 1 算法思想 设 G=(V, E)是具有 T=(U, 其最小生成树 。 初值： U=V， 。 对 选取权值 最小的边 (若 边 (入到 则舍弃该边 (边 (；否则，将该边并入到 即 E ( 。 重复 ，直到 v1 v3 v2 v4 8 5 7 12 11 3 6 (1) (2) 3 v5 v4 (5) v2 按 (3) 3 v5 4) 3 v5 拓扑排序 1 定义 拓扑排序 ： 由某个集合上的一个 偏序 得到该集合上的一个 全序 的操作。 自反性 ：若 a R，称集合 是 自反的 。 对称