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 < numberOfVertexes; i++) // 从图G的下标为0的顶点开始搜索。（也是图G的最小生成树的顶点集合）。 { adjVex[i] = 0; } for (int i = 0; i < numberOfVertexes; i++) // 初始从下标为0的顶点开始到下标为i的顶点的边的权值去搜索。找lowCost中权值最小的下标i。 { lowCost[i] = graph[0][i]; } int k = 0; // 初始假定权值最小的边的终点的下标为k。 for (int i = 1; i < numberOfVertexes; i++) { if (debug) { Console.WriteLine($"Loop {i}"); Console.Write("lowCost: "); PrintArray(lowCost); Console.Write(" adjVex: "); PrintArray(adjVex); Console.WriteLine(); } int minimumWeight = int.MaxValue; // 搜索过程中发现到的最小的权值。初始设置为最大的整数值以示两点间无边。 for (int j = 1; j < numberOfVertexes; j++) { if (lowCost[j] != 0 && lowCost[j] < minimumWeight) // lowCost中0表示该点已经搜索过了。lowCost[j] < minimumWeight即发现目前最小权值。 { minimumWeight = lowCost[j]; // 发现目前最小权值。 k = j; // 目前最小权值的边的终点下标。 } } if (!debug) { Console.WriteLine($"({adjVex[k]}, {k})"); // 输出边 } adjVex[i] = k; // 此时找到的k值即是权值最小的边的终点。将V[k]放入集合U。（这步可省略，因lowCost[j]已被标为“无需搜索”了）。 lowCost[k] = 0; // 0表示该点已经搜索过了，已不需要再被搜索了。 for (int j = 1; j < numberOfVertexes; j++) // 转到以V[k]为开始顶点的边，去与前面u为起始顶点到V[i]为终止顶点的边的权值去比较。 { if (lowCost[j] != 0 && graph[k][j] < lowCost[j]) // lowCost中0表示该点已经搜索过了。graph[k][j] < lowCost[j]即发现更小权值。 { lowCost[j] = graph[k][j]; // 更新权值；索引j即终点下标。 adjVex[j] = k; // 下次寻找权值小的边时，从k为下标的顶点为起点。 } } if (debug) { Console.Write("lowCost: "); PrintArray(lowCost); Console.Write(" adjVex: "); PrintArray(adjVex); Console.WriteLine(); } } } static void PrimSimplified(int[][] graph, int numberOfVertexes) { int[] adjVex = new int[numberOfVertexes], // 邻接顶点数组：搜索边的最小权值过程中各边的起点坐标 lowCost = new int[numberOfVertexes]; // 各边权值数组：搜索边的最小权值过程中各边的权值，数组下标为边的终点。 for (int i = 0; i < numberOfVertexes; i++) { adjVex[i] = 0; // 从图G的下标为0的顶点开始搜索。（也是图G的最小生成树的顶点集合）。 lowCost[i] = graph[0][i]; // 初始从下标为0的顶点开始到下标为i的顶点的边的权值去搜索。找lowCost中权值最小的下标i。 } int k = 0; // 初始假定权值最小的边的终点的下标为k。 for (int i = 1; i < numberOfVertexes; i++) { int minimumWeight = int.MaxValue; // 搜索过程中发现到的最小的权值。初始设置为最大的整数值以示两点间无边。 for (int j = 1; j < numberOfVertexes; j++) { if (lowCost[j] != 0 && lowCost[j] < minimumWeight) // lowCost中0表示该点已经搜索过了。lowCost[j] < minimumWeight即发现目前最小权值。 { minimumWeight = lowCost[j]; // 发现目前最小权值。 k = j; // 目前最小权值的边的终点下标。 } } Console.WriteLine($"({adjVex[k]}, {k})"); // 输出边 lowCost[k] = 0; // 0表示该点已经搜索过了，已不需要再被搜索了。 for (int j = 1; j < numberOfVertexes; j++) // 转到以V[k]为开始顶点的边，去与前面u为起始顶点到V[i]为终止顶点的边的权值去比较。 { if (lowCost[j] != 0 && graph[k][j] < lowCost[j]) // lowCost中0表示该点已经搜索过了。graph[k][j] < lowCost[j]即发现更小权值。 { lowCost[j] = graph[k][j]; // 更新权值；索引j即终点下标。 adjVex[j] = k; // 下次寻找权值小的边时，从k为下标的顶点为起点。 } } } } static void PrintArray(int[] array) { Console.Write("[ "); for (int i = 0; i < array.Length - 1; i++) // 输出数组的前面n-1个 { Console.Write($"{ToInfinity(array[i])}, "); } if (array.Length > 0) // 输出数组的最后1个 { int n = array.Length - 1; Console.Write($"{ToInfinity(array[n])}"); } Console.WriteLine(" ]"); } static string ToInfinity(int i) => i == int.MaxValue ? "∞" : i.ToString(); } }