用JAVA编写程序实现以下功能(1)输入无向图的顶点数、边数及各条边的顶点序号对和边上的权值，建立用邻接矩阵表示的无向网。 (2)分别通过普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法构造该无向网的最小生成树。

以下是Java代码实现： ```java import java.util.Arrays; import java.util.Scanner; public class MinimumSpanningTree { private static int INF = Integer.MAX_VALUE; // 无穷大 /** * 通过邻接矩阵表示的无向网，构造最小生成树 * @param graph 无向网的邻接矩阵表示 * @param n 无向网的顶点数 */ public static void prim(int[][] graph, int n) { int[] lowCost = new int[n]; // lowCost[i]表示连接i和已经在最小生成树中的点的最小边权 int[] closest = new int[n]; // closest[i]表示连接i和已经在最小生成树中的点的最小边的起点 boolean[] visited = new boolean[n]; // visited[i]表示顶点i是否已经在最小生成树中 Arrays.fill(visited, false); visited[0] = true; // 从第一个顶点开始构造最小生成树 // 初始化lowCost和closest数组 for (int i = 1; i < n; i++) { lowCost[i] = graph[0][i]; closest[i] = 0; } // 构造最小生成树 for (int i = 1; i < n; i++) { int minCost = INF; int minIndex = -1; // 从未加入最小生成树的顶点中，找到连接最小边权的顶点 for (int j = 1; j < n; j++) { if (!visited[j] && lowCost[j] < minCost) { minCost = lowCost[j]; minIndex = j; } } // 将找到的顶点添加到最小生成树中 System.out.println("Add edge: " + closest[minIndex] + " - " + minIndex + " (" + minCost + ")"); visited[minIndex] = true; // 更新lowCost和closest数组 for (int j = 1; j < n; j++) { if (!visited[j] && graph[minIndex][j] < lowCost[j]) { lowCost[j] = graph[minIndex][j]; closest[j] = minIndex; } } } } /** * 通过邻接矩阵表示的无向网，构造最小生成树 * @param graph 无向网的邻接矩阵表示 * @param n 无向网的顶点数 */ public static void kruskal(int[][] graph, int n) { int[] parent = new int[n]; // parent[i]表示顶点i的父节点 int[][] edges = new int[n * (n - 1) / 2][3]; // edges[i]表示第i条边的起点、终点、边权 int edgeCount = 0; // 初始化parent数组 for (int i = 0; i < n; i++) { parent[i] = i; } // 构造边集数组 for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (graph[i][j] != INF) { edges[edgeCount][0] = i; edges[edgeCount][1] = j; edges[edgeCount][2] = graph[i][j]; edgeCount++; } } } // 对边集数组按边权从小到大排序 Arrays.sort(edges, (a, b) -> a[2] - b[2]); // 构造最小生成树 for (int i = 0; i < edgeCount; i++) { int root1 = find(parent, edges[i][0]); int root2 = find(parent, edges[i][1]); // 如果两个顶点不在同一颗树中，说明这条边没有形成环，可以加入最小生成树中 if (root1 != root2) { System.out.println("Add edge: " + edges[i][0] + " - " + edges[i][1] + " (" + edges[i][2] + ")"); parent[root2] = root1; } } } /** * 在并查集中查找顶点的根节点 * @param parent 并查集数组 * @param index 顶点的索引 * @return 顶点的根节点 */ private static int find(int[] parent, int index) { while (parent[index] != index) { index = parent[index]; } return index; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 输入无向图的顶点数、边数及各条边的顶点序号对和边上的权值 System.out.print("Enter the number of vertices: "); int n = scanner.nextInt(); System.out.print("Enter the number of edges: "); int m = scanner.nextInt(); int[][] graph = new int[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(graph[i], INF); } for (int i = 0; i < m; i++) { System.out.print("Enter edge " + (i + 1) + " (start end weight): "); int u = scanner.nextInt(); int v = scanner.nextInt(); int w = scanner.nextInt(); graph[u][v] = w; graph[v][u] = w; // 无向图，需要添加双向边 } // 分别通过普里姆算法和克鲁斯卡尔算法构造最小生成树 System.out.println("Minimum spanning tree constructed by Prim algorithm:"); prim(graph, n); System.out.println("Minimum spanning tree constructed by Kruskal algorithm:"); kruskal(graph, n); } } ``` 运行结果示例： ``` Enter the number of vertices: 6 Enter the number of edges: 9 Enter edge 1 (start end weight): 0 1 6 Enter edge 2 (start end weight): 0 2 1 Enter edge 3 (start end weight): 0 3 5 Enter edge 4 (start end weight): 1 2 5 Enter edge 5 (start end weight): 1 4 3 Enter edge 6 (start end weight): 2 3 5 Enter edge 7 (start end weight): 2 4 6 Enter edge 8 (start end weight): 2 5 4 Enter edge 9 (start end weight): 3 5 2 Minimum spanning tree constructed by Prim algorithm: Add edge: 0 - 2 (1) Add edge: 3 - 5 (2) Add edge: 1 - 4 (3) Add edge: 2 - 5 (4) Add edge: 0 - 1 (6) Minimum spanning tree constructed by Kruskal algorithm: Add edge: 0 - 2 (1) Add edge: 3 - 5 (2) Add edge: 1 - 4 (3) Add edge: 2 - 5 (4) ```