TypeScript代码
function prim(graph: number[][], numberOfVertexes: number) { let debug: boolean = true; let adjVex: number[] = [], // 邻接顶点数组：搜索边的最小权值过程中各边的起点坐标 lowCost = []; // 各边权值数组：搜索边的最小权值过程中各边的权值，数组下标为边的终点。 for (let i = 0; i < numberOfVertexes; i++) // 从图G的下标为0的顶点开始搜索。（也是图G的最小生成树的顶点集合）。 { adjVex[i] = 0; } for (let i = 0; i < numberOfVertexes; i++) // 初始从下标为0的顶点开始到下标为i的顶点的边的权值去搜索。找lowCost中权值最小的下标i。 { lowCost[i] = graph[0][i]; } let k: number = 0; // 初始假定权值最小的边的终点的下标为k。 for (let i = 1; i < numberOfVertexes; i++) { if (debug) { console.log(`Loop ${i}`); console.log(`lowCost: ${printArray(lowCost)}`); console.log(` adjVex: ${printArray(adjVex)}`); } let minimumWeight: number = Number.MAX_VALUE; // 搜索过程中发现到的最小的权值。初始设置为最大的整数值以示两点间无边。 for (let 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.log(`(${adjVex[k]}, ${k})`);// 输出边 } adjVex[i] = k; // 此时找到的k值即是权值最小的边的终点。将V[k]放入集合U。（这步可省略，因lowCost[j]已被标为“无需搜索”了）。 lowCost[k] = 0; // 0表示该点已经搜索过了，已不需要再被搜索了。 for (let 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.log(`lowCost: ${printArray(lowCost)}`); console.log(` adjVex: ${printArray(adjVex)}`); console.log(''); } } } function primSimplified(graph: number[][], numberOfVertexes: number) { let adjVex: number[] = [], // 邻接顶点数组：搜索边的最小权值过程中各边的起点坐标 lowCost = []; // 各边权值数组：搜索边的最小权值过程中各边的权值，数组下标为边的终点。 for (let i = 0; i < numberOfVertexes; i++) { adjVex[i] = 0; // 从图G的下标为0的顶点开始搜索。（也是图G的最小生成树的顶点集合）。 lowCost[i] = graph[0][i]; // 初始从下标为0的顶点开始到下标为i的顶点的边的权值去搜索。找lowCost中权值最小的下标i。 } let k: number = 0; // 初始假定权值最小的边的终点的下标为k。 for (let i = 1; i < numberOfVertexes; i++) { let minimumWeight: number = Number.MAX_VALUE; // 搜索过程中发现到的最小的权值。初始设置为最大的整数值以示两点间无边。 for (let j = 1; j < numberOfVertexes; j++) { if (lowCost[j] != 0 && lowCost[j] < minimumWeight) // lowCost中0表示该点已经搜索过了。lowCost[j] < minimumWeight即发现目前最小权值。 { minimumWeight = lowCost[j]; // 发现目前最小权值。 k = j; // 目前最小权值的边的终点下标。 } } console.log(`(${adjVex[k]}, ${k})`); // 输出边 lowCost[k] = 0; // 0表示该点已经搜索过了，已不需要再被搜索了。 for (let 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为下标的顶点为起点。 } } } } function printArray(array: number[]): string { let str: string[] = []; str.push("[ "); for (let i = 0; i < array.length - 1; i++) // 输出数组的前面n-1个 { str.push(`${toInfinity(array[i])}, `) } if (array.length > 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], ]; // let graph: number[][] = [ // [0, 1, 5, infinity, infinity, infinity, infinity, infinity, infinity], // [1, 0, 3, 7, 5, infinity, infinity, infinity, infinity], // [5, 3, 0, infinity, 1, 7, infinity, infinity, infinity], // [infinity, 7, infinity, 0, 2, infinity, 3, infinity, infinity], // [infinity, 5, 1, 2, 0, 3, 6, 9, infinity], // [infinity, infinity, 7, infinity, 3, 0, infinity, 5, infinity], // [infinity, infinity, infinity, 3, 6, infinity, 0, 2, 7], // [infinity, infinity, infinity, infinity, 9, 5, 2, 0, 4], // [infinity, infinity, infinity, infinity, infinity, infinity, 7, 4, 0], // ]; //prim(graph, numberOfVertexes); primSimplified(graph, numberOfVertexes); } Main(); /** 运行结果： (0, 1) (1, 2) (2, 4) (4, 3) (4, 5) (3, 6) (6, 7) (7, 8) */参考资料：