数据结构-图-最小生成树(1)普利姆算法构造

时间:2022-06-22 17:59:29
/*
 *Date: 17-11-30
 *Author: Qian_Yu
 *Program: 普利姆算法求最小生成树
 */
#include <bits/stdc++.h>
#define MAXVALUE 0x7FFF
#define MAXNUM 0x64
using namespace std;
typedef struct adj_node{
    char vertex[MAXNUM];
    int adjacency_martrix[MAXNUM][MAXNUM];
    int vertex_num,edge_num;
} UNDGraph;
struct node{
    char front_vertex;
    int low_cost;
} Weight[MAXNUM];
void create_adjacency_matrix(UNDGraph &G);
int get_subscript(UNDGraph G,char v);
void ergodic_adjacency_matrix(UNDGraph G);
int minimun_spanning_tree(UNDGraph G,char u);
int main(){
    UNDGraph G;
    cout << "---------创建邻接矩阵---------\n";
    create_adjacency_matrix(G);
    cout << "---------遍历邻接矩阵---------\n";
    ergodic_adjacency_matrix(G);
    cout << "---------最小生成树  ---------\n";
    int ans = minimun_spanning_tree(G,'A');
    cout << "最小权为:" << ans << endl;
    return 0;
}
void create_adjacency_matrix(UNDGraph &G){
    cout << "请输入顶点数(int),边数(int):";
    cin >> G.vertex_num >> G.edge_num;
    cout << "请输入顶点信息(char):";
    for(int i = 0;i < G.vertex_num;i++) {
        cin >> G.vertex[i];
    }
    for(int i = 0;i < G.vertex_num;i++) {
        for(int j = 0;j < G.vertex_num;j++) {
            G.adjacency_martrix[i][j] = MAXVALUE;
        }
    }
    char v1,v2;
    int w;
    cout << "请输入顶点对V1(char),V2(char):\n";
    for(int k = 0;k < G.edge_num;k++) {
        cin >> v1 >> v2 >> w;
        int i = get_subscript(G,v1);
        int j = get_subscript(G,v2);
        G.adjacency_martrix[i][j] = w;
        G.adjacency_martrix[j][i] = w;
    }
}
int get_subscript(UNDGraph G,char v){
    for(int i = 0;i < G.vertex_num;i++) {
        if(G.vertex[i] == v) {
            return i;
        }
    }
    return -1;
}
void ergodic_adjacency_matrix(UNDGraph G){
    for(int i = 0;i < G.vertex_num;i++) {
        for(int j = 0;j < G.vertex_num;j++) {
            printf(j == 0?"%d":"\t%d",G.adjacency_martrix[i][j]);
        }
        cout << endl;
    }
}
int minimun_spanning_tree(UNDGraph G,char u){
    int ans = 0;
    int k = get_subscript(G,u);
    for(int j = 0;j < G.vertex_num;j++) {
       if(j != k) Weight[j] = {u,G.adjacency_martrix[k][j]};
    }
    Weight[k].low_cost = 0;
    for(int i = 1;i < G.vertex_num;i++) {
        int min_value = MAXVALUE;
        for(int ii = 0;ii < G.vertex_num;ii++) {
            if(Weight[ii].low_cost != 0 && Weight[ii].low_cost < min_value) {
                min_value = Weight[ii].low_cost;
                k = ii;
            }
        }
        cout << Weight[k].front_vertex << " " << G.vertex[k] << endl;
        int x = get_subscript(G,Weight[k].front_vertex);
        int y = get_subscript(G,G.vertex[k]);
        ans += G.adjacency_martrix[x][y];
        Weight[k].low_cost = 0;
        for(int j = 0;j < G.vertex_num;j++) {
            if(G.adjacency_martrix[k][j] < Weight[j].low_cost) {
                Weight[j] = {G.vertex[k],G.adjacency_martrix[k][j]};
            }
        }
    }
    return ans;
}