最小生成树(MATLAB)

prim 算法算法 设置两个集合 P 和 Q 其中 P 用于存放 G 的最小生成树中的顶点 集合 Q 存放 G 的最小生成树中的边 令集合 P 的初值为 P V1 假设构造最小生成树时 从顶点 V1 出发 集合 Q 的初值为 Prime 算法的思想是 从所有 p P v V P 的边中 选取具有最小权值的边 pv 将顶点 v 加入集合 P 中 将边 pv 加入集合 Q 中 如此不断重复 直到 P V 时 最小 生成树构造完毕 这时集合 Q 中包含了最小生成的所有边 找最 小的权 不连成圈即可 clc clear M 1000 a 1 2 50 a 1 3 60 a 2 4 65 a 2 5 40 a 3 4 52 a 3 7 45 a 4 5 50 a 4 6 30 a 4 7 42 a 5 6 70 a a zeros 2 7 a a a a find a 0 M result p 1 tb 2 length a while length result length a 1 temp a p tb temp temp d min temp jb kb find a p tb d j p jb 1 k tb kb 1 result result j k d p p k tb find tb k end result 例例 一个乡有 7 个自然村 其间道路如图所示 要以村为中心建有线广播网络 如要求沿道路架设广播线 应如何架设 Kruskal 算法算法 每步从未选的边中选取边每步从未选的边中选取边 e 使它与已选边不构成圈 且 使它与已选边不构成圈 且 e 是未选边中的最小权边 直到选够是未选边中的最小权边 直到选够 n 1 条边为止 条边为止 clc clear M 1000 a 1 2 50 a 1 3 60 a 2 4 65 a 2 5 40 a 3 4 52 a 3 7 45 a 4 5 50 a 4 6 30 a 4 7 42 a 5 6 70 i j find a 0 b a find a 0 data i j b index data 1 2 loop max size a 1 result while length result v2 index find index v1 v2 else index find index v2 v1 end data flag index flag end result 中国邮递员问题中国邮递员问题 中国邮递员问题也可以表示为 在一个有奇点的连通图中 要求增加一 些重复边 使得新的连通图不含有奇点 并且增加的重复边总权最小 我们把增加重复边后不含奇点的新的连通图叫做邮递路线 而总权最小 的邮递路线叫做最优邮递路线 求图中所示的中国邮递员问题求图中所示的中国邮递员问题 Fleury 算法 在一个算法 在一个 Euler 图中找出图中找出 Euler 环游 环游 注 包括三个文件 fleuf1 m edf m flecvexf m function T c fleuf1 d 注 必须保证是 Euler 环游 否则输出 T 0 c 0 n length d b d b b inf 0 b b 0 1 m 0 a sum b eds sum a 2 ed zeros 2 eds vexs zeros 1 eds 1 matr b for i 1 n if mod a i 2 1 m m 1 end end if m 0 fprintf there is not exit Euler path n T 0 c 0 end if m 0 vet 1 flag 0 t1 find matr vet 1 for ii 1 length t1 ed 1 vet t1 ii vexs 1 1 vet vexs 1 2 t1 ii Fleury 算算法法 算算法法步步骤骤 任选一个顶点 v0 令道路 w0 v0 假定道路 wi v0e1v1e2 eivi已经选好 则从 E e1 e2 ei 中选 一条边 ei 1 使 a ei 1与 vi相关联 b 除非不能选择 否则一定要使 ei 1不是 Gi G E e1 e2 ei 的割边 第 步不能进行时就停止 matr vexs 1 2 vexs 1 1 0 flagg 1 tem 1 while flagg flagg ed edf matr eds vexs ed tem tem tem 1 if ed 1 eds 0 T 2 eds 1 c 0 for g 1 eds c c d T 1 g T 2 g end flagg 0 break end end end end function flag ed edf matr eds vexs ed tem flag 1 for i 2 eds dvex f flecvexf matr i vexs eds ed tem if f 1 flag 0 break end if dvex 0 ed i vexs 1 i dvex vexs 1 i 1 dvex matr vexs 1 i 1 vexs 1 i 0 else break end end function dvex f flecvexf matr i vexs eds ed temp f 0 edd find matr vexs 1 i 1 dvex 0 dvex1 ded if length edd 1 dvex edd else dd 1 dd1 0 kkk 0 for kk 1 length edd m1 find vexs edd kk if sum m1 0 dvex1 dd edd kk dd dd 1 dd1 1 else kkk kkk 1 end end if kkk length edd tem vexs 1 i ones 1 kkk edd1 tem edd for l1 1 kkk lt 0 ddd 1 for l2 1 eds if edd1 1 2 l1 ed 1 2 l2 lt lt 1 end end if lt 0 ded ddd edd l1 ddd ddd 1 end end end if templength dvex1 for m 1 L 3 for n m 2 L 1 if a c1 m c1 n a c1 m 1 c1 n 1 0 flag 0 for m 1 L 3 for n m 2 L 1 if a c1 m c1 n a c1 m 1 c1 n 1 a c1 m c1 m 1 a c1