第四节第四节 最小树问题最小树问题最小树及其性质最小树及其性质求最小树的求最小树的Kruskal算法算法 算法步骤算法步骤 算法复杂性算法复杂性 求最小树的求最小树的Dijkstra算法算法 算法步骤算法步骤 算法复杂性算法复杂性最小树及其性质最小树及其性质支撑树支撑树T的权（或长）的权（或长）：最小树最小树：G中权最小的支撑树中权最小的支撑树定定理理6.4.1 设设T是是G的的一一个个支支撑撑树树，则则T是是G的的最最小小树树当且仅当对任意边当且仅当对任意边eT*有有证明证明最小树及其性质最小树及其性质续续定理定理6.4.3 设设T是是G的支撑树，则的支撑树，则T是是G的唯一最小树当且仅的唯一最小树当且仅当对任意边当对任意边eGT，e是是C(e)中的唯一最大边。中的唯一最大边。定理定理6.4.4 设设T是是G的支撑树，则的支撑树，则T是是G的唯一最小树当且仅的唯一最小树当且仅当对任意边当对任意边eT ，e是是(e)中的唯一最小边。中的唯一最小边。证明证明Kruskal算法算法的步骤的步骤第第1步步 开始把边按权的大小由小到大排列，即将图的开始把边按权的大小由小到大排列，即将图的边排序为边排序为a1,a2, ,am，使，使W(a1) W(a2)W(am) 置置S=，i=0，j=1。第第2步步 若若|S|=i=n-1，则停止。这时，则停止。这时GS=T即为所求；即为所求；否则，转向第否则，转向第3步。步。第第3步步 若若GSaj不构成回路，则置不构成回路，则置ei+1=aj，S=Sei+1 ，i:=i+1，j:=j+1，转向第，转向第2步；否则，置步；否则，置j:=j+1，转向第，转向第2步。步。例例Kruskal算法算法的复杂性的复杂性首先首先，在第，在第1步中把边按权的大小由小到大排列起来，步中把边按权的大小由小到大排列起来，这约需这约需mlog2m次比较次比较( (m为此网络的边数为此网络的边数) )其次其次，第，第2步最多循环步最多循环n次次在第在第3步中步中，判定加边后是否构成回路总共约需，判定加边后是否构成回路总共约需m次次比较，而加边后点的重新标号最多需比较，而加边后点的重新标号最多需n(n-1)次比较次比较所以，所以，总的计算量总的计算量为为mlog2m+n+m+n(n-1)O(n2log2n)Dijkstra算法算法的步骤的步骤第第1步步 置置uj=w1j，T=，R=1，S=2,3, ,n例例Dijkstra算法算法的复杂性的复杂性执行第执行第2步时步时，第一次是，第一次是(n-2)次比较，次比较， 第二次为第二次为(n-3)次比较，次比较， 第三次为第三次为(n-4)次比较，次比较， 因此总的比较为因此总的比较为(n-1)(n-2)/2次次执行第执行第3步时步时，第一次是，第一次是(n-2)次比较，次比较， 第二次为第二次为(n-3)次比较，次比较， 第三次为第三次为(n-4)次比较，次比较， 因此总的比较为因此总的比较为(n-1)(n-2)次次所以所以，总的计算量约为，总的计算量约为O(n2)