标签：rap   坐标   deb   参考   数据   length   ret   pre   sim   

算法代码

C#代码

using System;

namespace Prim
{
    class Program
    {
        static void Main(string[] args)
        {
            int numberOfVertexes = 9,
                infinity = int.MaxValue;

            int[][] graph = new int[][] {
                new int[]{0, 10, infinity, infinity, infinity, 11, infinity, infinity, infinity },
                new int[]{ 10, 0, 18, infinity, infinity, infinity, 16, infinity, 12 },
                new int[]{ infinity, 18, 0, 22, infinity, infinity, infinity, infinity, 8 },
                new int[]{ infinity, infinity, 22, 0, 20, infinity, 24, 16, 21 },
                new int[]{ infinity, infinity, infinity, 20, 0, 26, infinity, 7, infinity },
                new int[]{ 11, infinity, infinity, infinity, 26, 0, 17, infinity, infinity },
                new int[]{ infinity, 16, infinity, 24, infinity, 17, 0, 19, infinity },
                new int[]{ infinity, infinity, infinity, 16, 7, infinity, 19, 0, infinity },
                new int[]{ infinity, 12, 8, 21, infinity, infinity, infinity, infinity, 0 },
            };

            //Prim(graph, numberOfVertexes);
            PrimSimplified(graph, numberOfVertexes);
        }

        static void Prim(int[][] graph, int numberOfVertexes)
        {
            bool debug = true;

            int[] adjVex = new int[numberOfVertexes],                          // 邻接顶点数组：搜索边的最小权值过程中各边的起点坐标
                lowCost = new int[numberOfVertexes];                           // 各边权值数组：搜索边的最小权值过程中各边的权值，数组下标为边的终点。
                        
            for (int i = 0; i  0)                                              // 输出数组的最后1个
            {
                int n = array.Length - 1;
                Console.Write($"{ToInfinity(array[n])}");
            }
            Console.WriteLine(" ]");
        }

        static string ToInfinity(int i) => i == int.MaxValue ? "∞" : i.ToString();
    }
}

TypeScript代码

function prim(graph: number[][], numberOfVertexes: number) {
    let debug: boolean = true;

    let adjVex: number[] = [],                  // 邻接顶点数组：搜索边的最小权值过程中各边的起点坐标
        lowCost = [];                           // 各边权值数组：搜索边的最小权值过程中各边的权值，数组下标为边的终点。

    for (let i = 0; i  0)                       // 输出数组的最后1个
    {
        let n: number = array.length - 1;
        str.push(`${toInfinity(array[n])}`);
    }
    str.push(" ]");
    return str.join("");
}

function toInfinity(i: number) {
    return i == Number.MAX_VALUE ? "∞" : i.toString();
}

function Main() {
    let numberOfVertexes: number = 9,
        infinity = Number.MAX_VALUE;

    let graph: number[][] = [
        [0, 10, infinity, infinity, infinity, 11, infinity, infinity, infinity],
        [10, 0, 18, infinity, infinity, infinity, 16, infinity, 12],
        [infinity, 18, 0, 22, infinity, infinity, infinity, infinity, 8],
        [infinity, infinity, 22, 0, 20, infinity, 24, 16, 21],
        [infinity, infinity, infinity, 20, 0, 26, infinity, 7, infinity],
        [11, infinity, infinity, infinity, 26, 0, 17, infinity, infinity],
        [infinity, 16, infinity, 24, infinity, 17, 0, 19, infinity],
        [infinity, infinity, infinity, 16, 7, infinity, 19, 0, infinity],
        [infinity, 12, 8, 21, infinity, infinity, infinity, infinity, 0],
    ];

    prim(graph, numberOfVertexes);
    primSimplified(graph, numberOfVertexes);
}

Main();

参考资料：

《大话数据结构》 - 程杰 著 - 清华大学出版社 第247页

普里姆算法（Prim）邻接矩阵法

标签：rap   坐标   deb   参考   数据   length   ret   pre   sim   

原文地址：https://www.cnblogs.com/kokiafan/p/14773839.html