Chapter 1 Data structures and algorithms Concept
Type: A type is a collection of values. Simple type: Its values contain no subparts.
Composite type/Aggregate type: Its values contain subparts called data item or member. Data type: A data type is a type together with a collection of operations to manipulate the type.
ADT: An abstract data type (ADT) is the realization of a data type as a software component. The interface of the ADT is defined in terms of a type and a set of operations on that type. The behavior of each operation is determined by its inputs and outputs. Data structure: A data structure is the physical implementation for an ADT. Problems: A problem is a task to be performed.
Function: A function is a matching between inputs (the domain) and outputs (the range). Algorithm: An algorithm is a recipe for solving a problem whose steps are concrete and unambiguous. Algorithms must be correct, of finite length, and must terminate for all inputs.
Programs: A program is an instantiation of an algorithm in a programming language. Chapter 2 Mathematical preliminaries Concept
Set: A set is a collection of distinguishable members or elements. Recursion: An algorithm is recursive if it calls itself to do part of its work. Chapter 3 Algorithm Analysis Concept
Asymptotic algorithm analysis(对资源消耗进行评估，对同一程序算法进行分析): Asymptotic analysis attempts to estimate the resource consumption of an algorithm. It allows us to compare the relative costs of two or more algorithms for solving the same problem. Asymptotic analysis also gives algorithm designers a tool for estimating whether a proposed solution is likely to meet the resource constraints for a problem before they implement an actual program.
Growth rate（算法随着输入增长导致整体花费增长的比重）: the rate at which the cost of the algorithm grows as the size of its input grows.
Best/worst/average case: They express what the resource usage is at least, at most and on average, respectively.
Upper/Lower bound: It indicates the upper/lower or highest/least growth rate that the algorithm can have.
Big-Oh/Big-Omega notation（最大最小增长率，最多最少资源消耗）: It describes an upper/lower bound to its growth rate of𝑓(𝑛). It states a claim about the greatest/least amount of some resource that is required by an algorithm for some class of inputs of size n. Theta notation: When the upper and lower bounds are the same within a constant factor, we indicate this by using it.
Space/time tradeoff（时间和空间的平衡）: One can often achieve a reduction in time if one is willing to sacrifice space or vice versa. Chapter 4 Lists, Stacks and Queues Concept
List: list is a finite, ordered sequence of data items known as elements. Array-based/Linked list: Implement lists make use of arrays/pointers.
Ordered/Unordered list：A list that the elements in it are stored in ascending order.
Singly/Doubly linked list:
Each list node has a single pointer to the next node on the list.
A doubly linked list allows convenient access from a list node to the next node and also to the preceding node on the list.
Stack: The stack is a list-like structure in which elements may be inserted or removed from only one end.
Array-based/Linked stack: Implement stacks make use of arrays/pointers
Queue: The queue is a list-like structure that provides restricted access to its elements. Queue elements may only be inserted at the back and removed from the front. Array: A contiguous block of memory locations, where each memory location stores one fixed-length data item.
Array-based/Linked queue: Implement queues make use of arrays/pointers.
Circular queue: The first position of the storage space are connected to the last position, so this form a loop in the queue. Algorithm Insert and delete Chapter 5 Binary Trees BST：Binary Search Tree.
A binary tree that conforms to the following condition, known as the Binary Search Tree Property: All nodes stored in the left subtree of a node whose key value is K have key values than K. All nodes stored in the right subtree of a node whose key value is K have key values greater than or equal to K. Huffman tree
Full binary tree: Each node is either a leaf or internal node with exactly two non-empty
children.(叶节点数为内节点数加1，删除一个内部节点的两个叶节点则内部节点数减1，空指针数= 非空指针数+1)
Complete binary tree: If the height of the tree is d, then all leaves except possibly level d-1are completely full. The bottom level has all nodes to the left side. Height/depth of a binary tree
The depth of a node M in the tree is the length of the path from the root of the tree to M.（指单独一个点）
The height of a tree is one more than the depth of the deepest node in the tree.
Preorder traversal（前）: Visit each node before visiting its children. template Postorder traversal（后）: Visit each node after visiting its children. LRVRLV template void postorder(BinNode visit(root); // Perform some action } Inorder traversal（中）: Visit the left subtree, then the node, then the right subtree. template inorder(root->right()); } BST插入： template if (root == NULL) // Empty: create node return new BSTNode inserthelp(root->left(), k, it)); else root->setRight( inserthelp(root->right(), k, it)); // Return tree with node inserted return root; } BST删除： template deletemin(rt->left())); return rt; } } Heap（堆）：Complete binary tree with the heap property（partially ordered） Priority queue：When a collection of objects is organized by importance or priority Heap: 构造堆时按编号一个一个插入（不比较大小），比较时从最后一个非叶子树开 始与自己的子节点进行对比。插入时从末尾插入，删除时将最后一个元素提到堆顶。 Huffman tree: The goal is to build a tree with the minimum external path weight =sum of weighted path lengths of all leaves= its weight times its depth. Chapter 6 General Trees Traversal: The one of the search path visit every node in the tree, each node are visited once, and only be visited once. Equivalence classes: Consider the problem of assigning the members of a set to disjoint subsets called equivalence classes.(两个节点是有联系的则为等价) K-ary tree: Tree whose internal nodes all have exactly K children(内部节点都有k个孩子) FIND：通过一个节点最终找到根节点 UNION（a,b）：通过找到a和b的根节点来将b根节点作为a根节点的子树。 Chapter 7 Internal Sorting 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，（快选堆儿） 冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。 方式： 平均 最坏 最好 插入 n^2 n^2 n 希尔 n^1.3 / / 冒泡 n^2 n^2 n 快速 nlogn n^2 nlogn 选择 n^2 n^2 n^2 堆排 nlogn nlogn nlogn 归并 nlogn nlogn nlogn Stable sorting algorithm: A sorting algorithm is said to be stable if it does not change the relative ordering of records with identical key values.一种排序算法不改变关键码相同的记录的相对顺序，则称算法是稳定的。 就平均时间而言，快速排序最好。 冒泡排序：比较相邻两个数字，并交换位置 希尔排序：不断缩小间距进行排序 快速排序：选一端的一个元素为枢轴，从另一端开始寻找比数轴大或者小的元素进行交换，然后又从另一端开始寻找比数轴小或者大的元素进行交换，以此往复，直到数轴指向相遇，便完成一趟排序。 堆排序：利用堆的删除和构造进行排序，每次拿走最大或者最小元素。 Chapter 8 File Processing and External Sorting Golden Rule of File Processing: Minimize the number of disk accesses 使磁盘访问的次数最少 磁头在一个盘片的某个位置上可以访问的所有数据就构成了一个磁道（Track），即这个盘片上与主轴具有相同距离的所有数据。每个磁道分为多个扇区（sector），多个扇区通常集结成组，成为簇（cluster），是文件磁盘分配的最小单位。 Track:磁道：磁头在一个盘片的某个位置上可以访问到的所有数据构成一个磁道，即这个盘片上与主轴具有相同距离的所有数据。 The data on a single platter that are accessible to anyone position of the head for that platter are collectively called a track, that is, all data on a platter that are a fixed distance from the spindle. Each track is subdivided into sectors.扇区。I/O的基本单位。 Contiguous sectors are often grouped to form a cluster. A cluster is the smallest unit of allocation for a file, so all files are a multiple of the cluster size. 簇。多个扇区集结成的组。簇是文件分配的最小单位。 Consider the problem of sorting collections of records too large to fit in main memory. Because the records must reside in peripheral or external memory, such sorting methods are called external sorting. 外部排序算法的主要目标是尽量减少读、写磁盘的信息量。 A sorted sublist is called a run. 在外排序时，被排序的子列成为顺串 Chapter 9 Searching Hashing: The process of mapping a key value to a position in a table. Hashing Function: A hash function maps key values to positions. Collision: Given a hash function h and two keys k1 and k2 if h(k1) == h(k2) whereis a slot in the table, then we say that k1 and k2 have a collision at slotunder hash function h. Open hashing: When collisions occur, some are stored outside the table. Closed hashing: One of the records at another slot in the table. Probe Function: A function both of the element’s key value, and of the number of steps taken along the probe sequence. Load factor: How full the table is a= N/M where N is the number of records currently in the table. Chapter 10 Indexing Indexing is the process of associating a key with the location of a corresponding data record. Entry sequenced file: Order records by time of insertion. Each record of a database normally has a unique identifier, called the primary key. A key field where a particular key value might be duplicated in multiple records, is called a secondary key. A linear index is an index file organized as a sequence of key/pointer pairs where the keys are in sorted order and the pointers either (1) point to the position of the complete record on disk, (2) point to the position of the primary key in the primary index, or (3) are actually the value of the primary key. 2-3树：（满足左小右大） A. 一个结点包含一个或两个关键码； B,每个内部结点有2个（若它含1个关键码）或3个子女（它含2个关键码） C.所有叶结点在树结构的同一层，因此树的高度总是平衡 B树（m阶，满足左小右大）: 1.根要么是一个叶节点，要么至少有两个子女。 2.除了根节点以外，每个内部节点有m/2到m个子女。 3.所有的叶节点在树结构的同一层，因此树结构总是树高平衡的。 B+Tree： B+树是一个B树的更复杂的变体，只在叶结点储存记录，内部节点存储关键码值，只占据位置用于引导检索。M阶叶节点可能存储多余或少于m条记录，只是简单地要求叶节点至少达到半满。B+树的叶节点一般链接起来，形成一个双链表。 内部节点有m/2到m个孩子，叶节点可以存储？？？ Chapter 11 Graphs A cycle is a path of length 3 or more that connects to itself. Path: A sequence of vertices v1, v2, …, vn of length n-1 with an edge from vi to vi+1 for 1 <= i< n. The maximally connected subgraphs of an undirected graph are called connected components. DAG: A directed graph without cycles is called a directed acyclic graph。 广度优先（每次尽量多的遍历顶点个数，队列实现） BFS (breadth-first search) examines all vertices connected to the start vertex before visiting vertices further away. 深度优先（每次遍历一个顶点，栈实现） DFS (deep-first search) will recursively visit all of V’s unvisited neighbors. (p393) The process of laying out the vertices of a DAG in a linear order to meet the prerequisites rules is called a topological sort. （拓扑排序） The MST (minimum-cost spanning tree) is the graph containing the vertices of G along with the subset of G’s edges that (1) has the minimum total cost as measured by summing the values for all of the edges in the subset（权值之和最小，不能有回路） (2) keeps the vertices connected. Prime算法：选取一个顶点作为根，从根开始，每次选取一个顶点与上一个顶点相连且权值最小，保证不能有回路，并且连通所有顶点。 Kruskal算法：选取原图中最短的边开始连接，然后选取第二短的边进行连接，但保证不产生回路，每次都选取最短的边，直到连接完所有顶点 邻接矩阵\\表（链表） Chapter 1 类型（type）是一组值的集合。 数据项（data item）是一条信息或者其值属于某个类型的一条记录，数据项也可说成是数据类型的成员 数据类型(data type)是指一个类型和定义在这个类型上的一组操作 ADT，抽象数据类型，是指数据结构作为一个软件构件的实现。ADT 组操作来定义，每个操作由它的输入和输出定义。 的接口利用一个类型和这个类型上的一 数据结构（Data structure）是ADT的实现。即具体定义了一个类型和这个类型上的一组操作。 问题：数据类型和数据结构怎么区分？ 问题（problem） 问题是一个需要解决的任务，即对应一组输入，就有一组相应的输出。其定义不能包含有 关怎样解决问题的限制，然而，应该包含对任何可行方案所需资源的限制。 函数（function) 是输入（定义域，domain）和输出（range）之间的一种映射关系。 算法（algorithm）是指解决问题的一种方法或者一个过程。 程序（program）：一个计算机程序被认为是使用某种程序设计语言对一个算法的具体实现。 Chapter 2 递归(Rusursive)：一个递归算法必须有两个部分：初始情况（base case）和递归部分。初始情况只处理可以直 接解决而不需要再次递归调用的简单输入。递归部分包含对算法的一次或者多次递归调用，每一次的调用参数都在某种程度上比原始调用参数耿接近初始情况 集合（set）是由互不相同的成员或者元素构成的一个整体。 Chapter 3 渐进算法分析（Asymptotic algorithm analysis）又称渐进分析。渐进分析可以估算出当问题规 模变大时，一种算法及实现它的程序的效率和开销。 增长率（growth rate）,即当问题的规模增大时，算法代价增长的速度。 最佳、最差和平均情况（beat/worst/average case） 最佳情况（best case），第一个元素可能恰恰就是K，于是只要检查一个元素就行了，这种情况运行时间很短， 称为算法的最佳情况。 最差情况（worst case），如果最后一个元素是K，运行时间就会相当长。 平均情况（average case），平均搜索到整个数组的一半就能找到K，这种算法平均要检查n/2个元素，称之 为算法的平均情况。 Upper/lower bound 上限是当某一类数据的输入规模为n时，一种算法消耗的最大值（最小值） big-Oh/big-Omega/Theta notation 大O表示法描述上限。大Ω表示法描述 下限。当上、下限相等时，可能用θ表示法。即如果一种算法既在O(h(n)),又在Ω(h(n))中，则称其为θ(h(n)). Chapter 4 线性表（list）是由称为元素的数据项组成的一种有限且有序的序列。 顺序表（array based list）生成的长度已知且将表中元素顺序存储在数组的相邻单元上。 链表（linked list）是动态的，能按照表中新的元素分配存储空间。链表是由一系列称为表的节点 （node）的对象组成的。 增加表头节点的优点： 因为不需要考虑空链表或当前位置在链表末尾这些特殊情况，所以表头节点节省了源代码。这种源代码的简化增加了表头节点的空间开销，但是因为不再需要处理特殊情况而减少了源代码，使总的空间得到节省。 Ordered/unordered list 单链表（singly list）只允许从一个表节点直接访问它的后继节点。 双链表（doubly linked list）可以从一个表节点出发，在线性表中任意访问它的前驱节点和后继节 点。 数组（array）是在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起 来的一种形式。这些按序排列的同类数据元素的集合称为数组。 顺序栈（array-based stack）的元素数目已知且将栈中元素存储在栈里。 链式栈（linked stack）是动态的，能够按照栈中新的元素分配空间。链式栈是由一系列节点组成 的 顺序队列（array based queue）的元素数目已知，与顺序表不同的是，顺序队列为循环队列。 链式队列（linked queue）是动态的，能够按照队列新的元素分配空间，成员front和rear分别指 向首尾，增加时enqueue把新元素放入链表尾部，rear指向新的节点，出栈时dequeue只是简单地删除队列中的第一个节点，并修改front指针。 Chapter5 二叉检索树，BST（binary search tree），对于二叉检索树的任何一个节点，设其值为K，则该 结点左子树中任意一个结点的值都小于K；该结点右子树中任何一个结点的值都大于或等于K。 赫夫曼树（huffman tree）是一种变长编码。代码长度取决于对应字母的相对使用频率或者“权 重”。 Full/complete binary tree完全二叉树/满二叉树 满二叉树的每一个节点或者是一个分支节点并恰好由两个非空子结点；或者是叶结点。完全二叉树从根节点起，每一层从左到右填充，一棵树为d的完全二叉树除了d-1层以外，每一层都是满的。底层叶结点集中在左边的若干位置上。 Height/depth of a binary tree 二叉树的高和深度 结点M的深度就是从跟结点到M的路径长度。树的高度等于最深结点的深度加1.任何深度为d的结点的层数都为d。跟结点的深度为0. Full/complete binary tree完全二叉树/满二叉树的性质 1、完全二叉树的高度最短 2、非空满二叉树的叶结点数等于其分支节点数加1 3、一棵非空二叉树空子树的数目等于其结点数目加1 Heap 堆 堆是一棵完全二叉树，其次，堆中存储的数据是局部有序的即分为最大堆和最小堆。 priority queue优先队列 一些按照重要性或优先级来组织的对象称为优先队列 Chapter 6 Travelsal 遍历 所谓遍历(Traversal)，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。 Chapter 7 stable sorting algorithm 稳定排序算法 如果一个排序算法不会改变关键码值相同的记录的相对顺序，则称为稳定的 （stable）。 1.选择排序 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2.直接插入排序 基本思想： 每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 3.冒泡排序 基本思想： 依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小 数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为 可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的）， 第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。 由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。 4.Shell排序 基本思想： 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2 ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key ③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然 后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n- 1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 …… 直到无序区只有一个元素为止。 6.快速排序 基本思想： 快速排序（Quicksort）是对冒泡排序的一种改进。 它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 7.归并排序 基本思想： 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 8.基数排序 基本思想： 基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。 插入排序，起泡排序，选择排序，时间代价为(Θn2) Shell排序，Θ(n1.5) 快速排序， Θ(nlogn) 归并排序， Θ(nlogn) 堆排序， 最差、最优、平均都为Θ（nlogn） 分配排序和基数排序， Θ（n），仅能对一个0-n-1的排列进行排序 Chapter 8 Track/sector/cluster:磁头在一个盘片的某个位置上可以访问的所有数据就构成了一个磁道 （Track），即这个盘片上与主轴具有相同距离的所有数据。每个磁道分为多个扇区（sector），多个扇区通常集结成组，成为簇（cluster），是文件分配的最小单位。 Track:磁道：磁头在一个盘片的某个位置上可以访问到的所有数据构成一个磁道，即这个盘 片上与主轴具有相同距离的所有数据。 Sector:扇区。I/O的基本单位。 Cluster:簇。多个扇区集结成的组。簇是文件分配的最小单位。 Golden Rule of File Processing使磁盘访问的次数最少 external sorting 外排序 当记录因数量太大而无法存放到主存中，必须驻留在外存中，这些排序方法称为外排序 Run:在外排序时，被排序的子列成为顺串（Run） Chapter9 Hashing：根据关键码值直接访问表。把关键码值映射到表中的位置来访问记录，这个过程称 为散列（hashing） Properties of hash function:把关键码值映射到位置的函数成为散列函数（hashing function） Collision: 对于一个散列函数h的两个关键码值k1和k2，如果h(k1) = β= h(k2),其中β是表 中的一个槽，那么就说k1和k2对于β在散列函数h下有冲突（collision） Open hashing: Separate chaining:开散列方法（open hashing）也称单链方法（separate chaining），把冲突记录储存在表外。 Closed hashing:闭散列方法（closed hashing）也称开地址方法（open addressing），把冲突记 录储存在表中的另外一个槽内。闭散列方法把所有记录直接存储在散列表中，每条记录i 有一个基位置h(ki)，即由散列函数计算出的槽 Probe function:探查函数（Probe function）为关键码R的探查序列的第i个槽返回从基位置 开始的偏移量 Load factor:定义表的负载因子（Load factor）为α=N/M，其中N是表中当前的记录数，M是 表长。 Chapter 10 Entry-sequenced file：输入顺序文件（entry-sequenced file）按记录进入系统的顺序把记录 储存在磁盘里。 Indexing:索引（indexing）是把一个关键码与相应数据记录的位置相关联的过程。 Primary/secondary key:数据库中每条记录通常都有一个唯一标识，称为主码 Linear indexing:可能有多条记录具有相同的关键码值，成为辅码。 2-3 tree:形状符合如下定义：1.一个节点包含一个或两个关键码 2.每个内部节点有两个子女 （如果它包含一个关键码）或者三个子女（如果它包含两个关键码），因此得名2-3树。(2-3树是一个3阶B树) 3、所有叶结点都在树结构的同一层，因此树的高度总是平衡的。2-3树是形状符合以下特征的树： A. 一个结点包含一个或两个关键码； B,每个内部结点有2个（若它含1个关键码）或3个子女（它含2个关键码） C.所有叶结点在树结构的同一层，因此树的高度总是平衡 另外，对2-3树的每个结点，其左子树后继结点值都小于其第一个关键码值；其中间子树后继结点值都大于或等于第一个关键码值；如果结点有右子树，其中间子树后继结点值都小于第二个关键码值，其右子树后继结点值都大于或等于第二个关键码值。 B-tree:一个m阶的B树定义为有以下特性：1.根或者是一个叶节点，或者至少有两个子女。 2.除了根节点以外，每个内部节点有【m/2】到m个子女。3.所有的叶节点在树结构的同一层，因此树结构总是树高平衡的。 B+Tree：B+树是一个B树的更复杂的变体，只在叶结点储存记录，内部节点存储关键码值， 只占据位置用于引导检索。M阶叶节点可能存储多余或少于m条记录，只是简单地要求叶节点至少达到半满。B+树的叶节点一般链接起来，形成一个双链表。 Chapter 11 Path:如果定点序列v1,v2,v3„„vn从vi到vi+1的边均存在，则称顶点序列v1,v2„„vn构成 构成一条长度为n-1的路径。（Path） Cycle:如果一条路径将某个顶点连接到它本身，且其长度大于或等于3，则称此路径为回路 （Cycle） Connected component(连通分量):无向图的最大连通子图称为连通分量。 Adjacent list/matrix: 相邻矩阵法（Adjacent matrix）是图的一种常用的表示方法。是一个|V|*|V|数组，其第i行包括所有以vi为起点的边。如果从vi到vj存在一条边，则对第i行的第j个元素进行标记，否则不做标记。 邻接表法（Adjacent matrix）是图的一种常用的表示方法，是一个以链表为元素的数组。该数组包含|v|个元素，其中第i个元素储存的是一个指针，指向顶点vi的边构成的链表。这个链表储存由顶点vi的邻接点。 BFS:广度优先搜索（breadth-first search）是一种图周游算法，在进一步深入访问其他顶 点前，检查起点的所有邻接点。（从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。） DFS:深度优先搜索（depth-first search）是一种系统的图周游方式。在搜索过程中，每当 访问某个顶点v后，DFS就会递归地访问它的所有未被访问的相邻顶点。（从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。） Topological sort:拓扑排序（Topological sort）即将一个DAG（有向无环图）中所有顶点 在不违反先决条件规定的基础上排成线性序列的过程称为拓扑排序。 Greedy algorithm（贪心算法:包括Prim算法、Kruskal算法）: Prim算法：从图的任意一个顶点N开始，初始化MST为N。选出与N相关联的边中权最小的一条边，设其连接顶点N与另一个顶点M。把顶点M和边（N,M）加入到MST中，接下来，选出与顶点N或M相关联的边中权最小的一条边，设其连接一个新顶点，将这条边和新顶点添加到MST中。反复进行这样的处理直到所有的顶点都被加入到MST中，从而得到一个最小支撑树。 Kruskal算法：首先将顶点集分为|V|个等价类，每个等价类中包括一个顶点。然后按照权大小顺序处理每条边。如果一条边连接属于两个不同等价类的顶点，就把这条边添加到MST中，并把这两个等价类合并为一个，反复执行这个过程直到只剩下一个等价类。 DAG directed acycline graph（有向无环图） MST:最小支撑树（minimun-cost-spanning tree，MST）给定一个联通无向图G，且它 的每条边均有相应的长度或权值，则MST是一个包括G所有顶点及一部分边的图，其中包括的边是图G的子集，这些便满足下列条件：1：这个子集中所有边的权之和为所有子集中最小的。2.子集中的边能保证图是联通的。 因篇幅问题不能全部显示，请点此查看更多更全内容