设计图的数据，并建立最小生成树，同时计算生成最小生成树的时间-526互联

首先是建立图，呈现形式一共有三种，第一种是有V顶点，E边，这个第一次考虑的时候，（没有设计权重）第二种是临接表的形式；第三种是临界矩阵的形式呈现，我们使用第三种邻接矩阵来记录和统计图；

以下是生成图的代码，阶数表示为20阶，可以自行修改图的阶数；

#include <iostream>
#include <vector>
#include <random>
#include <fstream>

std::vector<std::vector<int>> generateGraph(int n) {
std::vector<std::vector<int>> graph(n, std::vector<int>(n, 0));

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(1, 100);

for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int weight = dis(gen); // 随机生成边的权重
graph[i][j] = weight;
graph[j][i] = weight;
}
}

return graph;
}

void printGraph(const std::vector<std::vector<int>>& graph) {
int n = graph.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
std::cout << graph[i][j] << " ";
}
std::cout << std::endl;
}
}

void saveGraphToFile(const std::vector<std::vector<int>>& graph) {
std::ofstream outputFile("graphT.txt");
if (outputFile.is_open()) {
int n = graph.size();
outputFile << n << std::endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
outputFile << graph[i][j] << " ";
}
outputFile << std::endl;
}
outputFile.close();
std::cout << "图已保存到 graphT.txt" << std::endl;
} else {
std::cerr << "无法打开文件 graphT.txt 进行保存" << std::endl;
}
}

int main() {
int n = 20; // 图的阶数
std::vector<std::vector<int>> graph = generateGraph(n);

printGraph(graph);

saveGraphToFile(graph);

return 0;
}

我们得到的txt文件是graphT,接下来是对这部分邻接矩阵进行生成最小生成树的操作，下面是生成最小生成树的代码，由于图的测试数据一直有变动，因此这里的输入文件，我们使用input 文件，需要自己重新修建一个txt文件，或者将图的邻接矩阵进行重命名；

#include <iostream>
#include <fstream>
#include <vector>
#include <chrono>
#include <climits>

void primMST(int n, std::vector<std::vector<int>>& graph) {
std::vector<bool> visited(n, false);
std::vector<int> key(n, INT_MAX);
std::vector<int> parent(n, -1);
int weight = 0; // 记录生成树的权重

key[0] = 0; // 将第一个顶点作为起始顶点

auto start = std::chrono::steady_clock::now(); // 记录开始时间

for (int count = 0; count < n - 1; count++) {
int u = -1;
for (int v = 0; v < n; v++) {
if (!visited[v] && (u == -1 || key[v] < key[u])) {
u = v;
}
}

visited[u] = true;

for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != 0 && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}

auto end = std::chrono::steady_clock::now(); // 记录结束时间

std::ofstream outputFile("output.txt");
if (outputFile.is_open()) {
// 输出生成树的边和权重，并计算总权重
for (int i = 1; i < n; i++) {
outputFile << parent[i] << " - " << i << ": " << graph[i][parent[i]] << std::endl;
weight += graph[i][parent[i]];
}

outputFile << "最小生成树的权重为：" << weight << std::endl;
outputFile << "生成最小生成树所耗费的时间为：" << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << "微秒" << std::endl;

outputFile.close();
std::cout << "结果已保存到 output.txt" << std::endl;
} else {
std::cerr << "无法打开文件 output.txt 进行保存" << std::endl;
}
}

int main() {
std::ifstream inputFile("input.txt");
int n;
inputFile >> n;

std::vector<std::vector<int>> graph(n, std::vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
inputFile >> graph[i][j];
}
}

inputFile.close();

primMST(n, graph);

return 0;
}

生成的结果我们保存在output文件中，在这个部分时，之前的代码都出现这个问题：

Process exited after 0.7779 seconds with return value 3221225477 ...

这个问题好多次出现，现在想，估计是当时的图的邻接矩阵有问题，或是放入到txt文件中时，没有加上阶数，或者是生成的时候，（i，j）和（j，i）对应的数值不一样，导致的内存问题；