《《基本数据结构》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《基本数据结构》PPT课件.ppt（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、ACM/ICPC程序设计程序设计基本数据结构基本数据结构及其在程序设计中的应用及其在程序设计中的应用非线性结构非线性结构n树、二叉树树、二叉树n图图n并查集并查集非线性结构非线性结构n树、二叉树树、二叉树n图图n并查集并查集树树树树是是n n个结点的有限集合个结点的有限集合(可以是空集可以是空集)，在任一棵非空树中：，在任一棵非空树中：（1 1）有且仅有一个称为）有且仅有一个称为根根的结点。的结点。（2 2）其余结点可分为互不相交的子集，而且这些子集本身又）其余结点可分为互不相交的子集，而且这些子集本身又是一棵树，称为根的是一棵树，称为根的子树子树。J JI IA AC CB BD DH HG
2、 GF FE EK KL LM M从逻辑结构看：从逻辑结构看：1）树中只有）树中只有树根没有父结点树根没有父结点；2）除根外，其余结点都有且仅一个父结点；除根外，其余结点都有且仅一个父结点；3）树中的结点，可以有零个或多个）树中的结点，可以有零个或多个孩子结点孩子结点；4)没有孩子的结点称为没有孩子的结点称为叶子结点叶子结点，或终端结点；，或终端结点；5）除根外的其他结点，都存在唯一一条从根到该结点的路径；）除根外的其他结点，都存在唯一一条从根到该结点的路径；J JI IA AC CB BD DH HG GF FE EK KL LM M树树树的结点：树的结点：包含一个数据元素及若干指向子树的分
3、支；包含一个数据元素及若干指向子树的分支；孩子结点：孩子结点：结点的子树的根称为该结点的孩子；结点的子树的根称为该结点的孩子；父结点：父结点：B B 是是A A的孩子，则的孩子，则A A是是B B的父亲；的父亲；兄弟结点：兄弟结点：同一双亲的孩子结点；同一双亲的孩子结点；堂兄结点：堂兄结点：同一层上的结点；同一层上的结点；祖先结点祖先结点:从根到该结点的所经分支上的所有结点；从根到该结点的所经分支上的所有结点；子孙结点：子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；以某结点为根的子树中任一结点都称为该结点的子孙；结点的度：结点的度：结点的子树数目；结点的子树数目；.J JI IA
4、AC CB BD DH HG GF FE EK KL LM M树的基本术语树的基本术语n二叉树二叉树的定义：二叉树要么为空，要么由根结点、的定义：二叉树要么为空，要么由根结点、左子树和右子树组成。左、右子树本身也是二叉树。左子树和右子树组成。左、右子树本身也是二叉树。n注意：二叉树的子树有严格的左右之分，而树没有。注意：二叉树的子树有严格的左右之分，而树没有。二叉树的定义二叉树的定义二叉树的定义二叉树的定义ACBFEDG二叉树的存储二叉树的存储n顺序存储顺序存储n链表存储链表存储二叉树的顺序存储二叉树的顺序存储n二叉树的顺序存储指的是用元素在数组中的下标表二叉树的顺序存储指的是用元素在数组中的
5、下标表示一个结点与其孩子和父结点的关系示一个结点与其孩子和父结点的关系.E EGFCDABA B CD EF G12345678910 11 12 13 14 15 16二叉树的链表存储二叉树的链表存储n二叉树的二叉链表存储二叉树的二叉链表存储(每个节点有两个指针域每个节点有两个指针域)，分别指示出结点的左子树和右子树分别指示出结点的左子树和右子树E EGFCDABABCEDFGrootLchilddataRchildtypedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;二叉树的链
6、式存储二叉树的链式存储n三叉链表存储三叉链表存储(每个节点有三个指针域，分别指示出每个节点有三个指针域，分别指示出左子树、右子树和父结点左子树、右子树和父结点)E EGFCDABABCEDFGrootLchilddataRchildParent树的存储树的存储n树的孩子兄弟表示法树的孩子兄弟表示法用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和其右边的下一个兄弟结点I IA AC CB BH HG GF FE ED DABFDCEGHIroot树的存储树的存储n树的孩子兄弟表示法树的孩子兄弟表示法用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子
7、结点和其右边的下一个兄弟结点A AC CB BD D A A B B C C D D=I I I I J J K K L L=J JK KL Ln借助于借助于“孩子兄弟表示法孩子兄弟表示法”可将树转化成二叉树可将树转化成二叉树二叉树的运算和应用二叉树的运算和应用n二叉树的遍历运算二叉树的遍历运算先序、中序、后序、层序遍历n哈夫曼树哈夫曼树二叉树的结构特点二叉树的结构特点n任何一个非空的二叉树都由三部分构成任何一个非空的二叉树都由三部分构成DLR二叉树的遍历运算二叉树的遍历运算n遍历运算是有关二叉树的主要运算，遍历方式有遍历运算是有关二叉树的主要运算，遍历方式有先序遍历(DLR)、中序遍历(LD
8、R)、后序遍历(LRD)层序遍历DLR先序遍历先序遍历nDLR：访问根结点、先序遍历左子树、先序遍历右子树访问根结点、先序遍历左子树、先序遍历右子树E EGFCDAB先序先序遍遍历序列序列:ABCDEFGDLR若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点；（2 2）先序遍历左子树；）先序遍历左子树；（3 3）先序遍历右子树；）先序遍历右子树；若二叉树为空，结束若二叉树为空，结束 基本项（也叫终止项）基本项（也叫终止项）若二叉树非空若二叉树非空 递归项递归项 （1 1）访问根结点；）访问根结点；（2 2）先序遍历左子树；）先序遍历左子树；（3 3）先序遍历右子树；）先序遍历右子树
9、；voidpreorder(BiTNode*root)/先序遍历root指向根的二叉树 if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorder中序遍历中序遍历nLDR：中序遍历左子树、访问根结点、中序遍历右子树中序遍历左子树、访问根结点、中序遍历右子树E EGFCDAB中序中序遍遍历序列序列:BADCFEGDLR若二叉树非空若二叉树非空 （1 1）中序遍历左子树；）中序遍历左子树；（2 2）访问根结点；）访问根结点；（3 3）中序遍历右
10、子树；）中序遍历右子树；voidinorder(BiTNode*root)/中序遍历root指向根的二叉树 if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if /inorder后序遍历后序遍历nLRD：后序遍历左子树、后序遍历右子树、访问根结点后序遍历左子树、后序遍历右子树、访问根结点E EGFCDAB后序后序遍遍历序列序列:BDFGECADLR若二叉树非空若二叉树非空 （1 1）后序遍历左子树；）后序遍历左子树；（2 2）后序遍历右子树；）后序遍历右子树
11、；（3 3）访问根结点；）访问根结点；voidpostorder(BiTNode*root)/后序遍历root指向根的二叉树 if(root!=NULL)postorder(root-Lchild);/后序遍历根的左子树 postorder(root-Rchild);/后序遍历根的右子树coutdata；/访问根结点/if /postorder层序遍历层序遍历nLRD：先根，后子树；先左子树，后右子树先根，后子树；先左子树，后右子树DLRE EGFCDAB层序层序遍历序列:ABCDEFG例例1：TreeRecoveryn已知二叉树的先序遍历序列和中序遍历序列，输出已知二叉树的先序遍历序列和中序
12、遍历序列，输出它的后序遍历序列它的后序遍历序列n如图如图输入：输入：DBAFCEGFABCDEG输出：输出：FACBGEDDBAFCEG例例1：TreeRecoveryn先序遍历序列特点：先序遍历序列特点：根根左子树先序序列 右子树先序序列根根左子树中序序列右子树中序序列n中序遍历序列特点：中序遍历序列特点：例例1：TreeRecoveryD B A F C E G 先序(DLR)中序(LDR)v根据先序确定树根，根据中序划分左、右子树根据先序确定树根，根据中序划分左、右子树F A B C D E GDFABCEGBAFCEG分析分析n输出后序序列，必先输出左子树的后序序列，再输输出后序序列，
13、必先输出左子树的后序序列，再输出右子树的后序序列，最后再输出根。出右子树的后序序列，最后再输出根。n可用递归过程实现可用递归过程实现 postorder()if()postorder()；/输出左子树的后序遍历序列 postorder()；/输出右子树的后序遍历序列 输出根输出根；postorder(先序序列，中序序列先序序列，中序序列)if(序列不空序列不空)postorder(左子树先序序列，左子树中序序列左子树先序序列，左子树中序序列)；postorder(右子树先序序列，右子树中序序列右子树先序序列，右子树中序序列)；输出根；输出根；/postorder例例2 2：Trees on t
14、he LevelTrees on the LevelnTreesarefundamentalinmanybranchesofcomputerscience.Currentstate-of-theartparallelcomputerssuchasThinkingMachinesCM-5arebasedonfattrees.Quad-andoctal-treesarefundamentaltomanyalgorithmsincomputergraphics.nThisprobleminvolvesbuildingandtraversingbinarytrees.n.sample input:(1
15、1,LL)(7,LLL)(8,R)(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()(3,L)(4,R)()sample output:5 4 8 11 13 4 7 2 1not complete 例例2 2：Trees on the LevelTrees on the Level(11,LL)(7,LLL)(8,R)(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()(3,L)(4,R)()sample input:case 1case 254811134721例例2 2：Trees on the LevelTrees on the Lev
16、el(11,LL)(7,LLL)(8,R)(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()11LLhead7LLL54811134721例例2 2：Trees on the LevelTrees on the Level(11,LL)(7,LLL)(8,R)(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()11LLhead7LLL8R54811134721例例2 2：Trees on the LevelTrees on the Level(11,LL)(7,LLL)(8,R)(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,
17、RR)()45L8R11LL13RL4RR7LLL2LLR1RRRhead54811134721例例3：Isitatree?A tree is a well-known data structure that is either empty(null,void,nothing)or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties.1)There is exactly one node,called the root,to whi
18、ch no directed edges point./入度为入度为02)Every node except the root has exactly one edge pointing to it./除根之外结点的入度为除根之外结点的入度为13)There is a unique sequence of directed edges from the root to each node./根到每个结点有唯一路径根到每个结点有唯一路径例例3：Isitatree?7345681928345623412189375264(a)(b)(c)哈夫曼树哈夫曼树(最优二叉树最优二叉树)结点的带权路径长度结
19、点的带权路径长度从根到该结点的路径长度与该结点权的乘积称为结点的带权路径长度树的带权路径长度树的带权路径长度树中所有叶子的带权路径长度之和称为树的带权路径长度记作哈夫曼树哈夫曼树(最优二叉树最优二叉树)设有四个叶子有四个叶子a、b、c和和d的二叉的二叉树中，中，对应的的权值分分别为7 7、5 5、2 2和和4 4，计算算WPL。abcd752475dcab4275dabc24WPL=36WPL=46WPL=35最优二叉树最优二叉树哈夫曼算法哈夫曼算法1)1)根据根据给定的定的n个个权值 w1,w2,.,wn构造构造n棵二叉棵二叉树的集合的集合F=T1,T2,.,Tn，其中每棵二叉其中每棵二叉树
20、Ti中只中只有一个有一个带权为wi的根的根结点，其左右子点，其左右子树均空。均空。2)2)在在F中中选取两棵根取两棵根结点的点的权值最小的最小的树作作为左右左右子子树构造一棵新的二叉构造一棵新的二叉树，且置新的二叉，且置新的二叉树的根的根结点的点的权值为其左、右子其左、右子树上根上根结点的点的权值之和。之和。3)3)在在F中中删除除这两棵两棵树，同，同时将新得到的二叉将新得到的二叉树加加入入F中。中。4)4)重复重复2)2)和和3)3)，直到，直到F中只含一棵中只含一棵树为止。止。这棵棵树便是最便是最优二叉二叉树。Example实例实例合并果子合并果子(fruit.pas/dpr/c/cpp)
21、【问题描述问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并可以把两堆果子合并到一起，消耗的体力等于两堆果每一次合并可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。耗体力之和
22、。因为还要花大力气把这些果子搬回家，所以多多在合并果子因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。使多多耗费的体力最少，并输出这个最小的体力耗费值。实例（续）实例（续）合并果子合并果子(fruit.pas/dpr/c/cpp)【问题描述问题描述】例如有例如有3种果子，数目依次为种果子，数目依次为1，2，9。可以
23、先将。可以先将1、2堆合并，新堆数目为堆合并，新堆数目为3，耗费体力为，耗费体力为3。接着，将新堆与原先。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为的第三堆合并，又得到新的堆，数目为12，耗费体力为，耗费体力为12。所以多多总共耗费体力所以多多总共耗费体力=3+12=15。可以证明。可以证明15为最小的为最小的体力耗费值。体力耗费值。实例（续）实例（续）合并果子合并果子(fruit.pas/dpr/c/cpp)【输入文件输入文件】输入文件输入文件fruit.in包括两行，第一行是一个整数包括两行，第一行是一个整数n（1=n=30000），表示果子的种类数。第二行包含），表示果子的种类
24、数。第二行包含n个整数，个整数，用空格分隔，第用空格分隔，第i个整数个整数ai（1=ai=20000）是第）是第i种种果子的数目。果子的数目。【输出文件输出文件】输出文件输出文件fruit.out包括一行，这一行只包含一个整数，包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于也就是最小的体力耗费值。输入数据保证这个值小于231。实例（续）实例（续）合并果子合并果子(fruit.pas/dpr/c/cpp)【样例输入样例输入】3129【样例输出样例输出】15【数据规模数据规模】对于对于30%的数据，保证有的数据，保证有n=100；对于对于50%的数据，保证有的数据，
25、保证有n=5000；对于全部的数据，保证有对于全部的数据，保证有n=30000。实例实例nzoj1486ColortheTreenzoj1167TreesontheLevel按规则构造二叉树nzoj1944TreeRecovery已知二叉树先序遍历序列和中序遍历序列，输出它的后序遍历序列nzoj1071FollowMyLogic构造逻辑表达式二叉树并求值nzoj1117Entropy哈夫曼编码非线性结构非线性结构n树、二叉树树、二叉树n图图n并查集并查集图结构图结构n基本概念基本概念图是顶点集和边集组成的二元组图是顶点集和边集组成的二元组G=(V,E),E中每条中每条边是边是V中一对顶点中一对
26、顶点(u,v)间的联系间的联系,如果是无序对，如果是无序对，那么称该图为那么称该图为无向图无向图，否则为，否则为有向图有向图。顶点顶点u,v间有边，间有边，u,v互为互为邻接点邻接点。边边(u,v)，和顶点和顶点u和和v相关联相关联。顶点顶点v的的度度是和是和v相关联的边的数目相关联的边的数目.有向图中有向图中,以以v为头的弧的数目称为为头的弧的数目称为出度出度;以以v为尾的弧的数目称为为尾的弧的数目称为入度。入度。连通图、连通图、强连通强连通子图子图(分量分量)无向图的无向图的生成树生成树.无向图及其生成树无向图及其生成树V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V
27、5无向图G图的邻接矩阵表示图的邻接矩阵表示8273496221V32V2V4V1V6V5 8 7 4 9 8 2 1 2 3 2 7 1 3 2 4 2 6 9 2 2 6 1234561 2 3 4 5 6图图1图图1的邻接矩阵的邻接矩阵图的邻接链表表示图的邻接链表表示8273496221V32V2V4V1V6V5表头顶点的表头顶点的邻接顶点编号邻接顶点编号和边相关和边相关的信息的信息指向下一个指向下一个邻接顶点的指针邻接顶点的指针(a)表结点结构表结点结构(b)图1的邻接链表12345628546947183241225262431721336214663219425632V1V2V3V4
28、V5V6图图1有向图及其强连通子图有向图及其强连通子图54613241510215203041010132415220546图图2图图2的强连通子图的强连通子图例例4 4：学校：学校网络网络A number of schools are connected to a computer network.Agreements have been developed among those schools:each school maintains a list of schools to which it distributes software(the receiving schools).No
29、te that if B is in the distribution list of school A,then A does not necessarily appear in the list of school B.54231You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network accor
30、ding to the agreement(Subtask A).431每个强连通分量每个强连通分量抽象为一个顶点抽象为一个顶点例例4 4：学校：学校网络网络(续续)431As a further task,we want to ensure that by sending the copy of new software to an arbitrary school,this software will reach all schools in the network.To achieve this goal we may have to extend the lists of receiv
31、ers by new members.Compute the minimal number of extensions that have to be made so that whatever school we send the new software to,it will reach all other schools(Subtask B).One extension means introducing one new member into the list of receivers of one school.431(a)(b)例例4 4：学校：学校网络网络(续续)The firs
32、t line of input file contains an integer N:the number of schools in the network(2=N=100).The schools are identified by the first N positive integers.Each of the next N lines describes a list of receivers.The line i+1 contains the identifiers of the receivers of school i.Each list ends with a 0.An em
33、pty list contains a 0 alone in the line.sample input524 3 045 050601 0 54231Your program should write two lines to the output file.The first line should contain one positive integer:the solution of subtask A.The second line should contain the solution of subtask B.sample output1 2 深度优先搜索深度优先搜索DFSV3V
34、2V4V1V6V5V3V2V4V1V6V5n深度优先遍历图的方法是，从深度优先遍历图的方法是，从图中某顶点图中某顶点v v出发：出发：(1)(1)访问顶点访问顶点v v；(2)(2)依次从依次从v v的未被访问的邻接点出发，对图进行深度优先遍历；的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和直至图中和v v有路径相同的顶点都被访问有路径相同的顶点都被访问(3)(3)若此时图中尚有顶点未被访问，则从一个未被访问的顶点出若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止为止(用栈
35、用栈)V2V3V4V5V6广度优先搜索广度优先搜索BFSV3V2V4V1V6V5V3V2V4V1V6V5n从图中某顶点从图中某顶点vivi出发：出发：访问顶点访问顶点vi vi；访问访问vi vi 的所有未被访问的邻接点的所有未被访问的邻接点w w1 1,w,w2 2,w,wk k ；依次从这些邻接点（在步骤依次从这些邻接点（在步骤中访问的顶点）出发，访问它中访问的顶点）出发，访问它们的所有未被访问的邻接点们的所有未被访问的邻接点;依此类推，直到图中所有访问依此类推，直到图中所有访问过的顶点的邻接点都被访问；过的顶点的邻接点都被访问；(用队列用队列)V2V4V5V6V3DFSVSBFSV3V2
36、V4V1V6V5V3V2V4V1V6V5(a)a)深度优先生成树深度优先生成树V3V2V4V1V6V5(b)b)广度优先生成树广度优先生成树例例5 5：SPF(1119)SPF(1119)Consider the two networks shown below.Assuming that data moves around these networks only between directly connected nodes on a peer-to-peer basis,a failure of a single node,3,in the network on the left wou
37、ld prevent some of the still available nodes from communicating with each other.Nodes 1 and 2 could still communicate with each other as could nodes 4 and 5,but communication between any other pairs of nodes would no longer be possible.1345213452例例5 5：SPFSPFNode 3 is therefore a Single Point of Fail
38、ure(SPF)for this network.Strictly,an SPF will be defined as any node that,if unavailable,would prevent at least one pair of available nodes from being able to communicate on what was previously a fully connected network.Note that the network on the right has no such node;there is no SPF in the netwo
39、rk.At least two machines must fail before there are any pairs of available nodes which cannot communicate.1345213452例例5 5：SPFSPFInputThe input will contain the description of several networks.A network description will consist of pairs of integers,one pair per line,that identify connected nodes.Orde
40、ring of the pairs is irrelevant;1 2 and 2 1 specify the same connection.All node numbers will range from 1 to 1000.A line containing a single zero ends the list of connected nodes.An empty network description flags the end of the input.Blank lines in the input file should be ignored.1 2 5 43 13 23 4
41、3 501 2 2 33 44 55 10 1345213452例例5 5：SPFSPF1 2 2 33 44 6 6 3 2 5 5 10 0Input(续续)134526outputFor each network in the input,you will output its number in the file,followed by For each network in the input,you will output its number in the file,followed by a list of any SPF nodes that exist.a list of
42、any SPF nodes that exist.例例5 5：SPFSPFoutputThe first network in the file should be identified as“Network#1”,the second as The first network in the file should be identified as“Network#1”,the second as“Network#2”,etc.For each SPF node,output a line,formatted as shown in the“Network#2”,etc.For each SP
43、F node,output a line,formatted as shown in the examples below,that identifies the node and the number of fully connected examples below,that identifies the node and the number of fully connected subnets that remain when that node fails.If the network has no SPF nodes,subnets that remain when that no
44、de fails.If the network has no SPF nodes,simply output the text“No SPF nodes”instead of a list of SPF nodes.simply output the text“No SPF nodes”instead of a list of SPF nodes.Network#1 SPF node 3 leaves 2 subnets Network#2 No SPF nodes Network#3 SPF node 2 leaves 2 subnets SPF node 3 leaves 2 subnet
45、s1345213452134526关节点的特点：关节点的特点：(1)若深度优先生成树的根有两棵或两棵以上的子树，则此根顶点必为关节点；若深度优先生成树的根有两棵或两棵以上的子树，则此根顶点必为关节点；(2)若生成树中某个非叶子结点若生成树中某个非叶子结点v，存在存在v的某棵子树的根及该子树的其他结点均的某棵子树的根及该子树的其他结点均没有指向没有指向v的祖先的回边，则的祖先的回边，则v是关节点。是关节点。因此，以深度优先遍历为基础增加相应的处理即可。详见严蔚敏的数据结构因此，以深度优先遍历为基础增加相应的处理即可。详见严蔚敏的数据结构掌握有关图的基本算法掌握有关图的基本算法n遍历方法：深度优先
46、遍历遍历方法：深度优先遍历(DFS)，广度优先遍历广度优先遍历(BFS)n求最短路径：求最短路径：Dijkstra算法，算法，Floyd算法，算法，Bellman-Ford算法算法n最小生成树：最小生成树：Prim算法，算法，Kruskal算法算法n关键路径关键路径n关节点关节点n最大独立集，最小支配集最大独立集，最小支配集n最大匹配，最优匹配最大匹配，最优匹配n最大网络流最大网络流.q克鲁斯卡尔算法求最小生成树克鲁斯卡尔算法求最小生成树V4V1V3V2V6V56512665534V4V1V3V2V6V51234最小代价生成树最小代价生成树q克鲁斯卡尔算法求最小生成树克鲁斯卡尔算法求最小生成树
47、V4V1V3V2V6V56512665534V4V1V3V2V6V512345V V3 3、V V4 4依附在同依附在同一个连通分量一个连通分量最小代价生成树最小代价生成树q克鲁斯卡尔算法求最小生成树克鲁斯卡尔算法求最小生成树V4V1V3V2V6V56512665534V4V1V3V2V6V51234V V1 1、V V4 4依附在同依附在同一个连通分量一个连通分量5最小代价生成树最小代价生成树q克鲁斯卡尔算法求最小生成树克鲁斯卡尔算法求最小生成树V4V1V3V2V6V56512665534V4V1V3V2V6V512534最小代价生成树最小代价生成树例例6 6：QSNetworkInthep
48、lanetw-503ofgalaxycgb,thereisakindofintelligentcreaturenamedQS.QScommunicatewitheachothervianetworks.IftwoQSwanttogetconnected,theyneedtobuytwonetworkadapters(oneforeachQS)andasegmentofnetworkcable.PleasebeadvisedthatONENETWORKADAPTERCANONLYBEUSEDINASINGLECONNECTION.(ie.ifaQSwanttosetupfourconnectio
49、ns,itneedstobuyfouradapters).Intheprocedureofcommunication,aQSbroadcastsitsmessagetoalltheQSitisconnectedwith,thegroupofQSwhoreceivethemessagebroadcastthemessagetoalltheQStheyconnectedwith,theprocedurerepeatsuntilalltheQSshavereceivedthemessage.例例6 6：QSNetworkAsampleisshownbelow:AsampleQSnetwork,and
50、QSAwanttosendamessage.Step1.QSAsendsmessagetoQSBandQSC;Step2.QSBsendsmessagetoQSA;QSCsendsmessagetoQSAandQSD;Step3.theprocedureterminatesbecausealltheQSreceivedthemessage.例例6 6：QSNetworkEachQShasitsfavoratebrandofnetworkadaptersandalwaysbuysthebrandinallofitsconnections.AlsothedistancebetweenQSvary.