请将上面的代码改成从键盘接受数据
时间: 2023-09-13 19:08:27 浏览: 34
以下是修改后的代码,现在可以从键盘接收节点数、边数和边的信息:
```c++
#include <iostream>
#include <climits>
using namespace std;
#define MAX_SIZE 100
class Graph {
private:
int num_vertex; // 图顶点的个数
int adj_matrix[MAX_SIZE][MAX_SIZE]; // 邻接矩阵
int parent[MAX_SIZE]; // 最小生成树中每个节点的父节点
int key[MAX_SIZE]; // 用于Prim算法的关键字数组
bool visited[MAX_SIZE]; // 节点是否已经被访问
public:
Graph(int num_vertex) {
this->num_vertex = num_vertex;
for (int i = 0; i < num_vertex; i++) {
for (int j = 0; j < num_vertex; j++) {
adj_matrix[i][j] = 0;
}
visited[i] = false;
key[i] = INT_MAX;
}
}
void add_edge(int i, int j, int weight) {
adj_matrix[i][j] = weight;
adj_matrix[j][i] = weight;
}
void prim() {
key[0] = 0;
parent[0] = -1;
for (int i = 0; i < num_vertex - 1; i++) {
// 找到未被访问的关键字最小的节点
int min_key = INT_MAX;
int min_index = -1;
for (int j = 0; j < num_vertex; j++) {
if (!visited[j] && key[j] < min_key) {
min_key = key[j];
min_index = j;
}
}
visited[min_index] = true;
// 更新相邻节点的关键字和父节点
for (int j = 0; j < num_vertex; j++) {
if (adj_matrix[min_index][j] && !visited[j] && adj_matrix[min_index][j] < key[j]) {
key[j] = adj_matrix[min_index][j];
parent[j] = min_index;
}
}
}
}
void print_tree() {
cout << "Edge\tWeight" << endl;
for (int i = 1; i < num_vertex; i++) {
cout << parent[i] << " - " << i << "\t" << adj_matrix[i][parent[i]] << endl;
}
}
};
int main() {
int num_vertex, num_edge;
cout << "Enter number of vertices and edges: ";
cin >> num_vertex >> num_edge;
Graph g(num_vertex);
cout << "Enter edges and weights:" << endl;
for (int i = 0; i < num_edge; i++) {
int u, v, w;
cin >> u >> v >> w;
g.add_edge(u, v, w);
}
g.prim();
g.print_tree();
return 0;
}
```
在main函数中,我们首先从键盘接收节点数和边数,然后创建一个Graph对象,并通过循环从键盘接收每条边的信息,最后调用prim函数求解最小生成树,并调用print_tree函数输出结果。