1、Prim算法 1、Prim算法 ■算法求精一最终算法 void PrimMST(AdjMatrix G,MST T,int r){ ■时间分析 int k,m,v; 初始化：O(n) InitCandidateSet(G,T,r);彻蛤候选集To.,n2 在k循环中： for(k=0;k<n-1;k+){求n-1条衡边中的k条 Select中循环次数为n-k-1∥在Tk.n-2选轻边Tm m=SelectLightEdge(T,k); Modify中循环次数为n-k-2 ∥在Tk.n-2习选轻边Tm间 Tk+1-2]是新候选集，报据斯红点v词整候选轻边、 T[m]→T[k灯；轻边和紫边T的交换，将其扩充至树中 因此： y=T[K].tovex;交换后红边集为TO.的，v是斯红点 时间为0，与边无关，适合稠密图。 ModifyCandidateSet(G,T,k+1,v); 厅k+1-2习是新候选第，根据新红点候选轻边编 2、Kruskal算法 2、Kruskal算法（续） ■特点：当前形成的集合T除最终结果外，始终是森林，无环。 ■算法： 例子：略 ■时间： KruskalMST(G){ T=,):包含n个顶点，不含边的森林： ◆对边排序O(elge) ◆for循环中： 依权的增序对E(G)中边排序，设结果在E0.e-1小： 检测每条边的两个顶点是否在同一连通分量（制）上 for(=0;i长e;it+)( 取E中第条边(u,店 只要采用合适的败据结构，检测时间为O(g) if(u和v分黑森林T中两棵不同的树)then 因此，此时间亦为o(elge)。 $总计： T=TU((u,v):否则产生回路，放弃此边 f(T已是一棵树)then return T: O(elge) M/endfor ■结论：时间性能主要取决于边数，适合稀琉图。 1、相关概念 ■集合与关系 §7.5拓扑排序 ◆信吉是公意记到为成的集合（《eAy 有向无环图DAG(Directed :必的减美泽 个完关系，他酒了教合A中行两 Acyclic Graph)的应用 个完意之间的关系，若区，yR,则称x和y有关系R,亦可记为xRy, 香和没有关系R,记为xRy。 ◆算合A上的关系R是自反的（反身的），若对x∈A,都有xRx, ◆算合A上的关系R是对物的，着xRy,则yRx,其中，x,y∈A ◆算合A上的关系R是反对察的，若xRy,yRx,则必有x=y其中xy∈A。 ◆桌合A上的关系R是传遭的，若xRy,yRZ,则XR.其中x,y2∈A 数之向的相够关暴，具有自反性，对称性，传递性，反对称性 败之闻的小于关暴，具有传递性，反对称性： 数之间的小于等于关系，具有自反性，传递性，反对称性： 33 13 1、Prim算法 „算法求精－最终算法 void PrimMST(AdjMatrix G, MST T, int r) { int k,m,v; InitCandidateSet(G, T, r);//初始候选集T[0..n-2] for (k=0; k<n-1; k++) { //求n-1条树边中的kth条 m＝SelectLightEdge(T,k); // 在T[k..n-2]选轻边T[m] T[m]↔T[k];//轻边和紫边T[k]交换，将其扩充至树中 v＝T[k].tovex; //交换后红边集为T[0..k],v是新红点 ModifyCandidateSet(G,T,k+1,v); //T[k+1..n-2]是新候选集，根据新红点v调整候选轻边集 } } 14 1、Prim算法 „时间分析 初始化：O(n) 在k循环中： Select中循环次数为n-k-1 // 在T[k..n-2]选轻边T[m] Modify中循环次数为n-k-2 //T[k+1..n-2]是新候选集，根据新红点v调整候选轻边集 因此： 时间为O(n2)，与边无关，适合稠密图。 15 2、Kruskal算法 „ 特点：当前形成的集合T除最终结果外，始终是森林，无环。 „ 算法： KruskalMST(G){ T=(V, φ)；//包含n个顶点，不含边的森林； 依权的增序对E(G)中边排序，设结果在E[0..e-1]; for (i=0; i<e; i++) { 取E中第i条边(u,v); if （u和v分属森林T中两棵不同的树） then T＝T∪{（u,v）}; //否则产生回路，放弃此边 if （T已是一棵树）then return T； }//endfor } 16 2、Kruskal算法（续） „ 例子：略 „ 时间： ™对边排序O(elge) ™for循环中： 检测每条边的两个顶点是否在同一连通分量（树）上 只要采用合适的数据结构，检测时间为O(lge) 因此，此时间亦为O(elge)。 ™总计： O(elge) „ 结论：时间性能主要取决于边数，适合稀疏图。 17 §7.5 拓扑排序 有向无环图DAG（Directed Acyclic Graph）的应用 18 1、相关概念 „ 集合与关系 ™ 笛卡儿积：设A、B是两个集合，所有序偶(x,y)构成的集合（x∈A, y ∈B ），称为A，B的笛卡儿积，记为A×B。 ™ 二元关系：集合A×B的一个子集R，称为集合A与B上的一个二元关系， 简称关系。若B＝A，则R称为A上的一个二元关系，他刻画了集合A中两 个元素之间的关系。若(x，y)∈R，则称x和y有关系R，亦可记为xRy， 否则x和y没有关系R，记为x y。 ™ 集合A上的关系R是自反的（反身的），若对∀x ∈A，都有xRx。 ™ 集合A上的关系R是对称的，若xRy，则yRx。其中，x，y ∈A。 ™ 集合A上的关系R是反对称的，若xRy，yRx,则必有x＝y.其中x,y ∈A。 ™ 集合A上的关系R是传递的，若xRy，yRz，则xRz。其中x,y,z ∈A。 ™ 例子： 数之间的相等关系，具有自反性，对称性，传递性，反对称性； 数之间的小于关系，具有传递性，反对称性； 数之间的小于等于关系，具有自反性，传递性，反对称性； R