没有合适的资源?快使用搜索试试~ 我知道了~
引入辅助向量:集合如何实现?CloseST 和 LowCost 的初值是多少?普里姆(Prim)算法如何实现呢?CloseST全为1;LowCost为邻接矩阵第
资源详情
资源评论
资源推荐
第4部分 图以及图有关的算法
数据结构与算法
4-1
计算机科学与技术学院(2021春)
数据结构与算法
Data Structures and Algorithms
第四部分 图
第4部分 图以及图有关的算法
数据结构与算法
4-2
计算机科学与技术学院(2021春)
回顾:图--2
1. 图的搜索算法
2. 图与树的联系
深度优先生成树
广度优先生成树
最小生成树
算法一: Prim (普里姆算法)
算法二: Kruskal (克鲁斯卡尔算法)
深度优先搜索DFS (Depth-First Search )
广度优先搜索BFS (Breadth-First Search)
图的遍历
第4部分 图以及图有关的算法
数据结构与算法
4-3
计算机科学与技术学院(2021春)
(1)求最小生成树 —— Prim 算法
输入:加权无向图(无向网)G=(V, E),其中v=(1,2, …,n).
输出:G的最小生成树
步骤:引入集合U和T。U为预备顶点集,T为树边集。
初值U={v
0
},T=¢。选择有最小权的边(u,v),
使u∈U, v∈(V-U), 将v加入U,(u,v)加入T。
重复这一过程,直到 U=V。
void Prim( G, T )
{ T = ¢ ;
U = { v
0
};
while ( ( V – U ) != ¢ )
{ 设( u, v ) 是使u∈U与v∈(V-U)且权最小的边 ;
T = T∪{ ( u, v ) } ;
U = U ∪ { v };
}
} ;
第4部分 图以及图有关的算法
数据结构与算法
4-4
计算机科学与技术学院(2021春)
引入辅助向量 :
CloseST[] 和 LowCost ,其中:
CloseST[i] 为 U 中的一个顶点
边 ( i , CloseST[i]) 具有最小的权 LowCost[i];
集合如何实现?
若顶点 i ∈ U 则 LowCost[i] = INFINITY
否则 LowCost[i] = 0;
CloseST 和 LowCost 的初值是多少?
普里姆(Prim)算法如何实现呢?
CloseST全为1;LowCost为邻接矩阵第一行。
第4部分 图以及图有关的算法
数据结构与算法
4-5
计算机科学与技术学院(2021春)
开始
调整LowCost, 对非集合U中的顶点 j
LowCost[j] = min( C[k][j], LowCost[j])
CloseST[j] = k;
i++
结束
LowCost[i]为邻接矩阵C的第一行值
CloseST[i]的初值均为1
从LowCost[i]中求值最小的顶点 k
( k , CloseST[k] )为求得的一条边,
将顶点 k 加入到集合U
定义:
CloseST[i]为U中的一个顶点
边( i , CloseST[i]) 具有
最小的权 LowCost[i]
Prim 算法流程图
i=2
i<=n
Yes
No
剩余54页未读,继续阅读
张景淇
- 粉丝: 40
- 资源: 276
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0