每组数据分为两个部分，第一部分为图的点数n，和边数m, 第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。

在这段代码中，输入的第一行应该是两个整数n和m，分别表示图的点数和边数。接下来的m行输入每条边的信息，每行包含三个整数，分别表示边的起点、终点和权值。你可以尝试以下输入格式：

6 9
0 1 10
0 2 3
1 2 5
1 3 1
2 3 8
2 4 2
2 5 4
3 4 7
4 5 6

这代表了一个有6个节点和9条边的无向图，每条边的信息依次为(0,1,10)，(0,2,3)，(1,2,5)，(1,3,1)，(2,3,8)，(2,4,2)，(2,5,4)，(3,4,7)，(4,5,6)。

相关问题

使用Prim算法求图的最小生成树(MST) 输入 每组数据分为两个部分，第一部分为图的点数n，和边数m, 第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。 输出 最小生成树，输出时按照边的两个端点的升序输出。（先看左端点，再看右端点，端点不换位置） 样例输入 Copy 3 3 0 1 10 0 2 15 1 2 50 样例输出 Copy 0 1 10 0 2 15

下面是使用Java实现Prim算法求解最小生成树的代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt(); // 点的个数
            int m = scanner.nextInt(); // 边的个数
            int[][] graph = new int[n][n]; // 邻接矩阵存储图
            for (int i = 0; i < m; i++) {
                int u = scanner.nextInt();
                int v = scanner.nextInt();
                int w = scanner.nextInt();
                graph[u][v] = w;
                graph[v][u] = w;
            }
            prim(graph);
        }
        scanner.close();
    }

    private static void prim(int[][] graph) {
        int n = graph.length;
        int[] dist = new int[n]; // 存储从当前最小生成树到各个点的最小距离
        int[] parent = new int[n]; // 存储最小生成树上每个点的父节点
        boolean[] visited = new boolean[n]; // 标记每个点是否已加入最小生成树
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(parent, -1);
        dist[0] = 0; // 从第一个点开始构建最小生成树
        for (int i = 0; i < n - 1; i++) {
            int u = getMinVertex(dist, visited);
            visited[u] = true;
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0 && !visited[v] && graph[u][v] < dist[v]) {
                    parent[v] = u;
                    dist[v] = graph[u][v];
                }
            }
        }
        printMST(parent, graph);
    }

    private static int getMinVertex(int[] dist, boolean[] visited) {
        int minDist = Integer.MAX_VALUE;
        int minVertex = -1;
        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minVertex = i;
            }
        }
        return minVertex;
    }

    private static void printMST(int[] parent, int[][] graph) {
        for (int i = 1; i < graph.length; i++) {
            if (parent[i] < i) {
                System.out.println(parent[i] + " " + i + " " + graph[parent[i]][i]);
            } else {
                System.out.println(i + " " + parent[i] + " " + graph[parent[i]][i]);
            }
        }
    }
}

对于输入`3 3 0 1 10 0 2 15 1 2 50`，程序将输出`0 1 10`和`0 2 15`，与样例输出一致。

完善下列代码， #include<iostream> #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MVNum 100 //最大顶点数 using namespace std; typedef struct {//图的邻接矩阵存储表示 int vexs[MVNum]; //顶点表 int arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //图的当前点数和边数 }AMGragh; int CreateUDN(AMGragh &G,int vexnum,int arcnum) {//采用邻接矩阵表示法，创建无向网G } int InsertVex(AMGragh &G) {//在以邻接矩阵形式存储的无向图G上插入顶点 } int OutputUDN(AMGragh G) {//输出图G }，要求如下:输入 多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有一个数字f，代表新插入的顶点编号。当n和m都等于0时，输入结束。 输出 每组数据输出n+1行。为增加顶点后的邻接矩阵。每两个数字之间用空格隔开。

下面是完善后的代码，请仔细查看注释：

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100     //最大顶点数
using namespace std;

typedef struct {//图的邻接矩阵存储表示
    int vexs[MVNum];    //顶点表
    int arcs[MVNum][MVNum];    //邻接矩阵
    int vexnum, arcnum;     //图的当前点数和边数
} AMGragh;

//采用邻接矩阵表示法，创建无向网G
int CreateUDN(AMGragh &G, int vexnum, int arcnum) {
    int i, j, k, w;
    //初始化无向网的顶点数和边数
    G.vexnum = vexnum;
    G.arcnum = arcnum;
    //初始化邻接矩阵
    for (i = 1; i <= G.vexnum; i++) {
        for (j = 1; j <= G.vexnum; j++) {
            G.arcs[i][j] = 0;
        }
    }
    //读入每条边的信息，建立邻接矩阵
    for (k = 1; k <= G.arcnum; k++) {
        cin >> i >> j >> w;
        G.arcs[i][j] = w;
        G.arcs[j][i] = w;
    }
    return OK;
}

//在以邻接矩阵形式存储的无向图G上插入顶点
int InsertVex(AMGragh &G) {
    int i, j, v;
    //读入新插入的顶点编号
    cin >> v;
    //将新插入的顶点添加到顶点表中
    G.vexnum++;
    G.vexs[G.vexnum] = v;
    //将新插入的顶点与其他顶点的关系添加到邻接矩阵中
    for (i = 1; i <= G.vexnum; i++) {
        G.arcs[i][G.vexnum] = 0;
        G.arcs[G.vexnum][i] = 0;
    }
    return OK;
}

//输出图G
int OutputUDN(AMGragh G) {
    int i, j;
    //输出邻接矩阵
    for (i = 1; i <= G.vexnum; i++) {
        for (j = 1; j <= G.vexnum; j++) {
            cout << G.arcs[i][j] << " ";
        }
        cout << endl;
    }
    return OK;
}

int main() {
    int n, m, f;
    AMGragh G;
    while (1) {
        //读入顶点数和边数
        cin >> n >> m;
        if (n == 0 && m == 0) {
            break;
        }
        //创建邻接矩阵表示的无向网
        CreateUDN(G, n, m);
        //插入新顶点
        InsertVex(G);
        //输出增加顶点后的邻接矩阵
        OutputUDN(G);
    }
    return 0;
}