C56 = C54 + C66 + 3 = 5 C55 + C76 + 3 = 4 OK R56 = 6
C44 = C43 + C54 + 7 = 7 OK R44 = 4
C45 = C43 + C55 + 8 = 9 OK R45 = 4
C44 + C65 + 8 = 15
C46 = C43 + C56 + 10 = 14 OK R46 = 4 C44 + C66 + 10 = 19 C45 + C76 + 10 = 19
以下省略.......
C16 = C10 + C26 + 25 = 63
C11 + C36 + 25 = 52 OK R16 = 2 root/cost 1 2 3 4 5 6 7 0 -1/0 1 1/5 -1/0 2 2/16 2/6 -1/0 3 2/24 2/14 3/4 -1/0 4 2/42 3/30 4/15 4/7 -1/0 5 2/54 3/33 4/17 4/9 5/1 -1/0 6 2/52 4/38 4/22 4/14 6/4 6/2 -1/0 最优二分树的建立
root[1][6] = 2，所以2为树根，左子树有1，右子树有3-6； root[3][6] = 4，所以4为树根，左子树有3，右子树有5-6； root[5][6] = 6，所以6为树根，左子树有5，右子树为空
最后构成的最优二分树如图：
7.给出利用DFS进行拓扑排序算法描述，并给出时间复杂度分析
把图中节点的状态分成三种。white代表节点还未被搜索到，gray代表节点已被搜索到但还
未被处理完，black代表节点已被处理完。数组topo[]来记录每个顶点的编号。
把图中所有的节点的状态初始化为white，topoNum=n，从顶点号为1的顶点开始搜索color[1]=gray. 设当前搜索到的节点为v，则按深度优先的方式搜索它的邻接点，若存在某个邻接点状态为white，则把该邻接点的状态改为gray，把它作为当前搜索到的节点，继续按深度优先方式搜索；若所有的邻接点状态都不是white则把当前节点状态改为black，topo[v]=topoNum,topoNum--,然后退回到上一个节点。 当所有节点的状态都为black时，退出循环。 时间复杂度：
设顶点数为n，边数为m。
算法分为两部分：初始化和搜索节点，显然初始化的时间复杂度是O（n），搜索节点则是按按深度优先的方式查找所有的边，时间复杂度为O（m+n），故此时间复杂度为O（m+n）。 8.对于给定的长度为n的数字序列，给出一个算法，找到该序列中的最长不降子序列（要求至少找到一个）。即对于序列a1，a2，a3，……，an，找到一组1 <= j1 < j2 < …… < jk <= n，使得aj1 <= aj2 <= …… <= ajk，且k最大。并分析时间复杂度 解答：定义两个数组maxLength[n]和preEle[n]
maxLength[i]表示：序列a1，a2，a3，……，ai中， ai之前（包括ai）最长的子序列的长度 preEle[i]表示：上诉子序列中ai的前一个元素的编号。 初始：maxLength[1] = 1，preEle数组全部置0 for(int k=2; k<=n; k++)
{//对于a1，a2，a3，……，ak-1中小于ak的所有at所对应的maxLength[t]中找到最大的一个，将该maxLength[t]加上1即为maxLength[k]，找到的t即为at在当前最长不下降子序列中的前一个元素 maxLength[k] = max{maxLength[t] | 1<=t 最后，maxLength[n]数组中最大的数即为所求的最长不下降子序列的长度，对应的元素即为最长不下降子序列的最后一个元素，从此元素开始，顺着该元素对应的preEle数组元素向前找对应的元素，直到找到的元素对应的preEle数组元素为0，便得到所求序列。 时间复杂度分析： 为了获得每个元素ai对应的数组元素maxLength[i]的取值，都需要对原序列中ai之前的每个数进行检验，故时间复杂度为O(n2)。 举例： 数字序列：1 9 2 3 8 5 10 6 下标 数字序列 1 1 2 9 2 1 3 2 2 1 4 3 3 3 5 8 4 4 6 5 4 4 7 10 5 5 8 6 5 6 maxLength 1 preEle 0 找到的maxLength数组中最大的元素为maxLength[7]和maxLength[8]，所以找到两个所求的序列，分别为： 1，2，3，5，6 9. 克鲁斯卡尔（Kruskal）算法（只与边相关） 算法描述：克鲁斯卡尔算法需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边有关系，可以证明其时间复杂度为O（eloge）。 算法过程： 1.将图各边按照权值进行排序 2.将图遍历一次，找出权值最小的边，（条件：此次找出的边不能和已加入最小生成树集合的边构成环），若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。 3.递归重复步骤1，直到找出n-1条边为止（设图有n个结点，则最小生成树的边数应为n-1条），算法结束。得到的就是此图的最小生成树。 克鲁斯卡尔（Kruskal）算法因为只与边相关，则适合求稀疏图的最小生成树。而prime算法因为只与顶点有关，所以适合求稠密图的最小生成树。 01.#include 08.int father[MAX], son[MAX]; 09.int v, l; 10. 11.typedef struct Kruskal //存储边的信息 12.{ 13. int a; 14. int b; 15. int value; 16.}; 17. 18.bool cmp(const Kruskal & a, const Kruskal & b) 19.{ 20. return a.value < b.value; 21.} 22. 23.int unionsearch(int x) //查找根结点+路径压缩 24.{ 25. return x == father[x] ? x : unionsearch(father[x]); 26.} 27. 28.bool join(int x, int y) //合并 29.{ 30. int root1, root2; 31. root1 = unionsearch(x); 32. root2 = unionsearch(y); 33. if(root1 == root2) //为环 34. return false; 35. else if(son[root1] >= son[root2]) 36. { 37. father[root2] = root1; 38. son[root1] += son[root2]; 39. } 40. else 41. { 42. father[root1] = root2; 43. son[root2] += son[root1]; 44. } 45. return true; 46.} 47. 48.int main() 49.{ 50. int ncase, ltotal, sum, flag; 51. Kruskal edge[MAX]; 52. scanf(\ 53. while(ncase--) 54. { 55. scanf(\ 56. ltotal = 0, sum = 0, flag = 0; 57. for(int i = 1; i <= v; ++i) //初始化 58. { 59. father[i] = i; 60. son[i] = 1; 61. } 62. for(int i = 1; i <= l ; ++i) 63. { 64. scanf(\ 65. } 66. sort(edge + 1, edge + 1 + l, cmp); //按权值由小到大排序 67. for(int i = 1; i <= l; ++i) 68. { 69. if(join(edge[i].a, edge[i].b)) 70. { 71. ltotal++; //边数加1 72. sum += edge[i].value; //记录权值之和 73. cout< 75. if(ltotal == v - 1) //最小生成树条件：边数=顶点数-1 76. { 77. flag = 1; 78. break; 79. } 80. } 81. if(flag) printf(\ 82. else printf(\ 83. } 84. return 0; 85.} 普利姆（Prime）算法（只与顶点相关） 算法描述： 普利姆算法求最小生成树时候，和边数无关，只和定点的数量相关，所以适合求稠密网的最小生成树，时间复杂度为O（n*n）。 算法过程： 1.将一个图的顶点分为两部分，一部分是最小生成树中的结点（A集合），另一部分是未处理的结点（B集合）。 2.首先选择一个结点，将这个结点加入A中，然后，对集合A中的顶点遍历，找出A中顶点关联的边权值最小的那个（设为v），将此顶点从B中删除，加入集合A中。 3.递归重复步骤2，直到B集合中的结点为空，结束此过程。 4.A集合中的结点就是由Prime算法得到的最小生成树的结点，依照步骤2的结点连接这些顶点，得到的就是这个图的最小生成树。 算法实现具体过程： 1.将第一个点放入最小生成树的集合中（标记visit[i]=1意思就是最小生成树集合）。 2.从第二个点开始，初始化lowcost[i]为跟1点相连（仅仅相连）的边的权值（lowcost[i]不是这个点的最小权值！在以后会逐步更新）。 3.找最小权值的边。 从第二点开始遍历，如果不是最小生成树的集合的点，则找出从2到n的最小权值（lowcost[j]）。 4.将找出来的最小权值的边的顶点加入最小生成树的集合中（标记visit[i] = 1），权值想加。 5.更新lowcost[j]集合。 假设第一次：lowcost[2]代表与1相连的点的权值，现在加入了k点。则比较k点与2点的边map[k][2]和lowcost[2]的大小，若lowcost[2]大，则lowcost[2] = map[k][2]。（关键步骤：实质就是每在最小生成树集合中加入一个点就需要把这个点与集合外的点比较，不断的寻找两个集合之间最小的边） 6.循环上述步骤，指导将全部顶点加入到最小生成树集合为止。 代码如下：