编辑代码


#include<iostream>
#include<string>
#include<vector>
#include <climits>
using  namespace std;

//首先是使用邻接矩阵完成Prim算法
struct Graph {
    int vexnum;  //顶点个数
    int edge;   //边的条数
    int** arc; //邻接矩阵
    string* information; //记录每个顶点名称
};

//创建图
void createGraph(Graph& g) {
    cout << "请输入顶点数:";
    cin >> g.vexnum;
    cout << "请输入边的条数:";
    cin >> g.edge;

    g.information = new string[g.vexnum];
    g.arc = new int* [g.vexnum];
    for (int i = 0; i < g.vexnum; i++) {
        g.arc[i] = new int[g.vexnum];
        cout << "请输入顶点 " << i + 1 << " 的城市名: ";
        getline(cin, g.information[i]); // 使用 getline 来允许城市名包含空格
        for (int k = 0; k < g.vexnum; k++) {
            g.arc[i][k] = INT_MAX; // 初始化邻接矩阵
        }
    }

    cout << "请输入每条边的起点和终点城市名(输入完成后输入两个空字符串结束):" << endl;
    string start, end;
    while (cin >> start >> end) {
        if (start.empty() || end.empty()) break;
        int start_index = -1, end_index = -1;
        for (int i = 0; i < g.vexnum; ++i) {
            if (g.information[i] == start) start_index = i;
            if (g.information[i] == end) end_index = i;
        }
        if (start_index == -1 || end_index == -1) {
            cout << "城市名输入错误,请输入有效的城市名。" << endl;
            continue;
        }
        int weight;
        cin >> weight;
        g.arc[start_index][end_index] = weight;
        g.arc[end_index][start_index] = weight; // 因为是无向图
    }
}

//打印图
void print(Graph g) {
    cout << "城市名\t";
    for (int i = 0; i < g.vexnum; i++) {
        cout << g.information[i] << "\t";
    }
    cout << endl;

    for (int i = 0; i < g.vexnum; i++) {
        cout << g.information[i] << "\t";  // 打印上三角矩阵
        for (int j = 0; j < g.vexnum; j++) {
            if (g.arc[i][j] == INT_MAX)
                cout << "∞\t";  // 表示不存在直接的连接
            else
                cout << g.arc[i][j] << "\t";  // 打印权重
        }
        cout << endl;
    }
}

//作为记录边的信息,这些边都是达到end的所有边中,权重最小的那个
struct Assis_array {
    int start; //边的终点
    int end;  //边的起点
    int weight;  //边的权重
};
//进行prim算法实现,使用的邻接矩阵的方法实现。
void Prim(Graph g, int begin) {
    // close_edge数组记录到达某个顶点的最小权重边
    Assis_array* close_edge = new Assis_array[g.vexnum];
    int min, end, start;

    // 初始化close_edge数组
    for (int j = 0; j < g.vexnum; j++) {
        if (j != begin) {
            close_edge[j].start = begin;
            close_edge[j].end = j;
            close_edge[j].weight = g.arc[begin][j];
        }
    }
    close_edge[begin].weight = INT_MAX;  // 起点不与自己相连

    // 构建最小生成树
    for (int j = 1; j < g.vexnum; j++) {
        min = INT_MAX;
        end = start = -1;

        // 寻找最小权重边
        for (int k = 0; k < g.vexnum; k++) {
            if (close_edge[k].weight < min) {
                min = close_edge[k].weight;
                end = close_edge[k].end;
                start = close_edge[k].start;
            }
        }

        // 将找到的最小权重边加入到最小生成树中
        if (min != INT_MAX) {
            cout << g.information[start] << " - " << g.information[end]
                << " : " << min << endl;
            close_edge[end].weight = INT_MAX;  // 标记为已访问
        }
        else {
            break;  // 没有更多的边可以加入
        }

        // 更新cross_edge数组
        for (int k = 0; k < g.vexnum; k++) {
            if (g.arc[end][k] < close_edge[k].weight && close_edge[k].weight != INT_MAX) {
                close_edge[k].weight = g.arc[end][k];
                close_edge[k].start = end;
            }
        }
    }

    delete[] close_edge;  // 释放内存
}



int main()
{
    Graph g;
    createGraph(g);
    print(g);
    Prim(g, 1);
    system("pause");
    return 0;
}