技术图文：如何利用C# 实现 Prim 最小生成树算法？

背景

我们上一篇图文介绍了 如何利用 C# 实现 Kruskal 最小生成树算法？，Kruskal 算法通过寻找边最优的方式来构造最小生成树，本篇图文介绍如何利用 C# 实现 Prim 最小生成树算法，Prim 算法通过寻找顶点最优的方式来构造最小生成树。

在继续介绍 Prim 算法之前，我整理了以前发布的有关数据结构与算法的图文，建个索引以方便大家的复习啊。

线性结构

• 如何利用“栈”解决“出轨”问题？
• 如何利用“队列”解决“窗口混乱”问题？
• 字符串的模式匹配算法

树形结构

• 如何利用C#实现Huffman编码？

排序相关

• 8大排序算法之：直接插入排序
• 8大排序算法之：希尔插入排序
• 8大排序算法之：直接选择排序
• 8大排序算法之：堆选择排序
• 8大排序算法之：冒泡排序
• 8大排序算法之：快速交换排序
• 8大排序算法之：并归排序
• 8大排序算法之：桶排序

搜索相关

• 8大搜索算法之：顺序搜索
• 8大搜索算法之：二分搜索
• 8大搜索算法之：插补搜索
• 8大搜索算法之：二叉搜索树（上）
• 8大搜索算法之：二叉搜索树（中）
• 8大搜索算法之：二叉搜索树（下）
• 8大搜索算法之：AVL树（上）
• 8大搜索算法之：AVL树（中）
• 8大搜索算法之：AVL树（下）
• 8大搜索算法之：红黑树（上）
• 8大搜索算法之：红黑树（中）
• 8大搜索算法之：红黑树（下）

LeetCode 实战

• LeetCode实战：旋转链表
• LeetCode实战：相同的树
• LeetCode实战：对称二叉树
• LeetCode实战：删除链表的倒数第N个节点
• LeetCode实战：合并两个有序链表
• LeetCode实战：两两交换链表中的节点

---

技术分析

Prim 算法：

Prim算法

例子：

例子

该例子演示了一个含有6个结点，10条边的联通网，通过 Prim 算法从 V0 点开始逐步演化为含有6个结点，5条边的连通子网的过程，即构造最小生成树的过程。

---

代码实现

我们利用邻接表的方式来存储图的结构。有关于边表 EdgeNode、顶点表 VertexNode 和图 AdGraph 的结构，参见 如何利用 C# 实现 Kruskal 最小生成树算法？ 中的 Step1、Step2 和 Step3。

上面例子，在内存中的邻接表结构为：

邻接表

最小生成树的节点结构 SpanTreeNode，参见 如何利用 C# 实现 Kruskal 最小生成树算法？ 中的 Step4。

有了以上的基础，我们就可以写 Prim 算法了。

public SpanTreeNode[] MiniSpanTree(string vName)
{
    int i = GetIndex(vName);
    if (i == -1)
        return null;

    SpanTreeNode[] spanTree = new SpanTreeNode[VertexCount];
    
    //首先加入根节点
    spanTree[0] = new SpanTreeNode(_vertexList[i].VertexName,
        "NULL", 0.0);

    //U中结点到各结点最小权值那个结点在VertexList中的索引号
    int[] vertexIndex = new int[VertexCount];
    
    //U中结点到各个结点的最小权值
    double[] lowCost = new double[VertexCount];
    
    for (int j = 0; j < VertexCount; j++)
    {
        lowCost[j] = double.MaxValue;
        vertexIndex[j] = i;
    }

    EdgeNode p1 = _vertexList[i].FirstNode;
    while (p1 != null)
    {
        lowCost[p1.Index] = p1.Weight;
        p1 = p1.Next;
    }
    vertexIndex[i] = -1;

    for (int count = 1; count < VertexCount; count++)
    {
        double min = double.MaxValue;
        int v = i;
        for (int k = 0; k < VertexCount; k++)
        {
            if (vertexIndex[k] != -1 && lowCost[k] < min)
            {
                min = lowCost[k];
                v = k;
            }
        }
        spanTree[count] = new SpanTreeNode(_vertexList[v].VertexName,
            _vertexList[vertexIndex[v]].VertexName, min);
        vertexIndex[v] = -1;

        EdgeNode p2 = _vertexList[v].FirstNode;
        while (p2 != null)
        {
            if (vertexIndex[p2.Index] != -1 &&
                p2.Weight < lowCost[p2.Index])
            {
                lowCost[p2.Index] = p2.Weight;
                vertexIndex[p2.Index] = v;
            }
            p2 = p2.Next;
        }
    }
    return spanTree;
}

---

总结

到此为止代码部分就全部介绍完了，我们来看一下上面例子的应用。

利用邻接表存储图的结构。

static AdGraph CreateGraph()
{
    AdGraph result = new AdGraph(6);
    result[0] = "V0";
    result[1] = "V1";
    result[2] = "V2";
    result[3] = "V3";
    result[4] = "V4";
    result[5] = "V5";
    result.AddEdge("V0", "V1", 6);
    result.AddEdge("V0", "V2", 1);
    result.AddEdge("V0", "V3", 5);
    result.AddEdge("V1", "V0", 6);
    result.AddEdge("V1", "V2", 5);
    result.AddEdge("V1", "V4", 3);
    result.AddEdge("V2", "V0", 1);
    result.AddEdge("V2", "V1", 5);
    result.AddEdge("V2", "V3", 7);
    result.AddEdge("V2", "V4", 5);
    result.AddEdge("V2", "V5", 4);
    result.AddEdge("V3", "V0", 5);
    result.AddEdge("V3", "V2", 7);
    result.AddEdge("V3", "V5", 2);
    result.AddEdge("V4", "V1", 3);
    result.AddEdge("V4", "V2", 5);
    result.AddEdge("V4", "V5", 6);
    result.AddEdge("V5", "V2", 4);
    result.AddEdge("V5", "V3", 2);
    result.AddEdge("V5", "V4", 6);
    return result;
}

从 V2 点开始构建最小生成树。

static void Main(string[] args)
{
    AdGraph alg = CreateGraph();
    SpanTreeNode[] tree = alg.MiniSpanTree("V2");
    double sum = 0;
    for (int i = 0; i < tree.Length; i++)
    {
        string str = "(" + tree[i].ParentName + ","
                        + tree[i].SelfName + ") Weight:"
                        + tree[i].Weight;
        Console.WriteLine(str);
        sum += tree[i].Weight;
    }
    Console.WriteLine(sum);
}

结果如下：

输出结果

我们再通过一个例子来演示如何应用：

地图

上面是一幅纽约市附近的地图，对应的数据存储在 graph.txt 文件中。

数据

读入该文件，构造好 AdGraph 结构后，调用我们写好的 Prim 算法，得到的结果如下：

输出结果

是不是很有趣，今天就到这里吧！马上要放假了，我们的招新活动也即将开启，希望大家关注呦！

See You！

---

相关图文：

• 如何利用 C# 实现 K 最邻近算法？
• 如何利用 C# 实现 K-D Tree 结构？
• 如何利用 C# + KDTree 实现 K 最邻近算法？
• 如何利用 C# 对神经网络模型进行抽象？
• 如何利用 C# 实现神经网络的感知器模型？
• 如何利用 C# 实现 Delta 学习规则？
• 如何利用 C# 爬取带 Token 验证的网站数据？
• 如何利用 C# 向 Access 数据库插入大量数据？
• 如何利用 C# 开发「桌面版百度翻译」软件！
• 如何利用 C# 开发「股票数据分析软件」（上）
• 如何利用 C# 开发「股票数据分析软件」（中）
• 如何利用 C# 开发「股票数据分析软件」（下）
• 如何利用 C# 爬取「财报说」中的股票数据？
• 如何利用 C# 爬取 One 持有者返利数据！
• 如何利用 C# 爬取Gate.io交易所的公告！
• 如何利用 C# 爬取BigOne交易所的公告！
• 如何利用 C# 爬取 ONE 的交易数据？
• 如何利用 C# 爬取「猫眼电影：热映口碑榜」及对应影片信息！
• 如何利用 C# 爬取「猫眼电影专业版：票房」数据！
• 如何利用 C# 爬取「猫眼电影：最受期待榜」及对应影片信息！
• 如何利用 C# 爬取「猫眼电影：国内票房榜」及对应影片信息！
• 如何利用 C# + Python 破解猫眼电影的反爬虫机制？
• 如何利用BigOne的API制作自动化交易系统 -- 身份验证
• 如何利用BigOne的API制作自动化交易系统 -- 获取账户资产
• 如何利用BigOne的API制作自动化交易系统 -- 订单系统