高端建设网站,做淘宝券网站,秦皇岛最新通知,百度提交入口的使用方法文章目录前置问题问题解答一、基础概念#xff1a;最小生成树的定义和性质#xff08;1#xff09;最小生成树#xff08;Minimal Spanning Tree#xff09;的定义#xff08;2#xff09;最小生成树#xff08;MST#xff09;的性质二、如何利用MST性质寻找最小生成树…
文章目录前置问题问题解答一、基础概念最小生成树的定义和性质1最小生成树Minimal Spanning Tree的定义2最小生成树MST的性质二、如何利用MST性质寻找最小生成树三、Prim算法1Prim算法思想2Prim算法形成最小生成树的详细过程3Prim算法的C和python实现四、Dijkstra算法1和Prim算法的联系2Dijkstra算法思想前置问题 问题解答 一、基础概念最小生成树的定义和性质
1最小生成树Minimal Spanning Tree的定义
生成树的代价设G(V,E)G(V,E)G(V,E)是一个无向连通网图生成树上各边的权值之和称为生成树的代价。最小生成树在图GGG所有生成树中代价最小的生成树为最小生成树。
2最小生成树MST的性质
假设G(V,E)G(V,E)G(V,E)是一个无向连通网图UUU是顶点集的一个非空子集。若(u,v)(u,v)(u,v)是一条具有最小权值的边其中u∈U,v∈V−Uu\in U,v\in V-Uu∈U,v∈V−U,则必存在一棵包含边u,vu,vu,v的最小生成树。 二、如何利用MST性质寻找最小生成树
找到两个点集之间最小权值的边(u,v)(u,v)(u,v)让具有最小权值的(u,v)(u,v)(u,v)成为最小生成树的一部分将大于最小权值的(u,v)(u,v)(u,v)删除。
接下来有两个思路
从一个点出发一次加入点形成点集Prim算法从边出发将点集合并避免形成环Kruskal算法
三、Prim算法
1Prim算法思想
对点做操作维护一个在最小生成树中的点的顶点集A以及一个待处理点的顶点集B每次找出连接这两个集合的最短边并将其两个顶点都加入集合A直到所有顶点都处理完毕。
抽象描述觉得抽象跳过 2Prim算法形成最小生成树的详细过程 图注
红色线段表示最小生成树蓝圈表示集合UUU其他顶点集合为V−UV-UV−U蓝色线段表示UUU和V−UV-UV−U的相邻边 计算U中每个点和其相邻点之间的代价找出代价最小的点V5将V5纳入U集合。计算U中每个点和其相邻点之间的代价找出代价最小的点V5将V5纳入U集合。计算U中每个点和其相邻点之间的代价找出代价最小的点V5将V5纳入U集合。 3Prim算法的C和python实现
四、Dijkstra算法
1和Prim算法的联系
Dijkstra算法和Prim算法都是最短路径算法主要用于求图的最短路径。
不同点在于Dijkstra算法适用于有向图起点到其他点的最短路径而Prim算法适用于无向图求最小生成树。它们的求解过程也略有不同。Dijkstra算法每次选择距离起点最近的点作为新的访问点更新其他点到起点的最短距离直到所有点都被访问。Prim算法则从一个起点开始不断选择与已经访问过的点相连且边权最小的点直到图上所有点都被访问。
2Dijkstra算法思想 算出A点到图中每一点的路径长度选出一条最短路径A-B将顶点B加入集合S。
增加了一条最短路径之后顶点A到其他点的路径是不是有更短的路径了呢
更新最短路径 在A-C,A-D,A-E中选出最短路径A-D并将D顶点加入S集合。更新所有最短路径。
