关于离散数学中Kruskal生成最小生成树的一个白痴概念问题
来源:学生作业帮 编辑:百度作业网作业帮 分类:综合作业 时间:2024/08/18 03:11:04
关于离散数学中Kruskal生成最小生成树的一个白痴概念问题
假设给定一个加权连通图G,G的边集合为E,顶点个数为n,要求其一棵最小生成树T。
假设T中的边和顶点均涂成红色,其余边为白色。开始时G中的边均为白色。
1)将所有顶点涂成红色;
2)在白色边中,挑选一条权最小的边,使其与红色边不形成圈,将该白色边涂红;
3)重复2)直到有n-1条红色边,这n-1条红色边便构成最小生成树T的边集合。
请问一个边的“权重”指什么??? 怎么算出来一个边的权?
假设给定一个加权连通图G,G的边集合为E,顶点个数为n,要求其一棵最小生成树T。
假设T中的边和顶点均涂成红色,其余边为白色。开始时G中的边均为白色。
1)将所有顶点涂成红色;
2)在白色边中,挑选一条权最小的边,使其与红色边不形成圈,将该白色边涂红;
3)重复2)直到有n-1条红色边,这n-1条红色边便构成最小生成树T的边集合。
请问一个边的“权重”指什么??? 怎么算出来一个边的权?
![关于离散数学中Kruskal生成最小生成树的一个白痴概念问题](/uploads/image/z/15756443-35-3.jpg?t=%E5%85%B3%E4%BA%8E%E7%A6%BB%E6%95%A3%E6%95%B0%E5%AD%A6%E4%B8%ADKruskal%E7%94%9F%E6%88%90%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E7%9A%84%E4%B8%80%E4%B8%AA%E7%99%BD%E7%97%B4%E6%A6%82%E5%BF%B5%E9%97%AE%E9%A2%98)
边的权重是算法的输入(input)
举个例子 假设我们要把N个城市连起来,使修路的总距离最短。这时计算MST 边的权重就是两个城市间的距离
举个例子 假设我们要把N个城市连起来,使修路的总距离最短。这时计算MST 边的权重就是两个城市间的距离
如何证明用 Kruskal's 算法生成的树是最小生成树
离散数学中关于环的概念的一个问题
急求KRUSKAL算法求最小生成树过程演示
数据结构课程设计用Kruskal 算法求最小生成树
求最小生成树 利用Kruskal算法求图G的一棵最小生成树T,用c语言
Kruskal算法和Prim算法构造它的一棵最小代价生成树的过程
数据结构与算法:请使用Kruskal算法求出下图的最小生成树
离散数学中树的概念问题
离散数学中求最小生成树的方法中点集法是怎么操作的
如图所示为一个无向带权图,请分别按照Prim算法和Kruskal算法求最小生成树
离散数学问题:证明连通图中至少有一颗生成树
用普里姆(Prim)或克鲁斯卡尔(Kruskal)算法画出下列无向网的最小生成树