网站设置快捷方式到桌面,做网站租用服务器,百度知道首页官网,织梦手机网站分亨链接怎么做Otakar Boruvka
本文给出Boruvka算法的C#实现源代码。
Boruvka算法用于查找边加权图的最小生成树#xff08;MST#xff09;#xff0c;它早于Prim和Kruskal的算法#xff0c;但仍然可以被认为是两者的关联。
一、Boruvka算法的历史
1926年#xff0c;奥塔卡博鲁夫卡MST它早于Prim和Kruskal的算法但仍然可以被认为是两者的关联。
一、Boruvka算法的历史
1926年奥塔卡·博鲁夫卡Otakar Boruvka首次提出了一种求给定图的MST的方法。这在计算机出现之前就已经存在了事实上它被用来设计一个高效的配电系统。 Georges Sollin在1965年重新发现了它并将其用于并行计算。
二、Boruvka算法的思路
该算法的核心思想是从一组树开始每个顶点代表一棵孤立的树。然后我们需要不断增加边以减少孤立树的数量直到我们有一个单一的连接树。 让我们通过一个示例图逐步了解这一点 步骤0创建一个图表 步骤1从一堆未连接的树开始树的数量顶点的数量 步骤2当存在未连接的树时对于每个未连接的树 (1)以较小的重量找到它的边缘 (2)添加此边以连接另一棵树 三、Boruvka算法的源代码
1、核心代码
using System;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{/// summary/// 图的连接边信息/// /summarypublic class EdgeInfo{/// summary/// 起始节点编码按一般教材习惯1起步/// /summarypublic int Start { get; set; } 0;/// summary/// 终点编码按一般教材习惯也从1起步/// /summarypublic int End { get; set; } 0;/// summary/// 边的权值/// /summarypublic int Weight { get; set; } 0;/// summary/// 构造函数/// /summary/// param namea/param/// param nameb/param/// param namec/parampublic EdgeInfo(int a, int b, int c){this.Start a;this.End b;this.Weight c;}}/// summary/// MST-Boruvka算法/// /summarypublic static class Boruvka_Minium_Spaning_Tree{private static int[] Parent { get; set; } null;private static int[] Minium { get; set; } null;/// summary/// 计算最小生成树MST的最小代价及树信息/// /summary/// param namegraph图信息边列表/param/// param nametree返回树信息边的列表/param/// returns/returnspublic static int Execute(EdgeInfo[] graph, out Listint tree){tree new Listint();// 计算最大节点编号int N 0;for (int i 0; i graph.Length; i){if (graph[i].Start N) N graph[i].Start;if (graph[i].End N) N graph[i].End;}Parent new int[N 1];for (int i 1; i N; i){Parent[i] i;}Minium new int[N 1];int result 0;int components N;while (components 1){for (int i 1; i N; i){Minium[i] -1;}for (int i 0; i graph.Length; i){if (Root(graph[i].Start) Root(graph[i].End)){continue;}int r_v Root(graph[i].Start);if (Minium[r_v] -1 || graph[i].Weight graph[Minium[r_v]].Weight){Minium[r_v] i;}int r_u Root(graph[i].End);if (Minium[r_u] -1 || graph[i].Weight graph[Minium[r_u]].Weight){Minium[r_u] i;}}for (int i 1; i N; i){if (Minium[i] ! -1){if (Merge(graph[Minium[i]].Start, graph[Minium[i]].End)){result graph[Minium[i]].Weight;tree.Add(Minium[i]);components--;}}}}return result;}private static int Root(int v){if (Parent[v] v){return v;}return Parent[v] Root(Parent[v]);}private static bool Merge(int v, int u){v Root(v);u Root(u);if (v u){return false;}Parent[v] u;return true;}}
}2、测试与显示
ListEdgeInfo g new ListEdgeInfo();
g.Add(new EdgeInfo(1, 2, 6));
g.Add(new EdgeInfo(1, 3, 1));
g.Add(new EdgeInfo(1, 4, 4));
g.Add(new EdgeInfo(1, 5, 4));
g.Add(new EdgeInfo(2, 4, 2));
g.Add(new EdgeInfo(2, 5, 2));
g.Add(new EdgeInfo(3, 4, 8));int weight Boruvka_Minium_Spaning_Tree.Execute(g.ToArray(), out Listint path);
StringBuilder sb new StringBuilder();
sb.AppendLine(The minium weight is: weight br);
sb.AppendLine(The minium tree is : br);
foreach (int idx in path)
{sb.AppendLine((g[idx].Start --- g[idx].End ) weight g[idx].Weight br);
}
webBrowser1.DocumentText sb.ToString();更多算法源代码将陆续发布建议关注。
——————————————————————————————————————————
POWER BY TRUFFER.CN
