数据结构实验代码普利姆算法.rar

#include<iostream> #include<cstring> #define Infinite 1000 #define Max 10 using namespace std; struct{ char adjvex; int lowcost; }closedge[Max]; class Graph { private: int vexnum;//点数 int arcnum;//弧数 public: int **arcs;//邻接矩阵 char *vexs; Graph(); int LocateVex(char ch); void print(); int getvexnum(); }; Graph::Graph() { cout<<"请输入点数："; cin>>vexnum; cout<<"请输入各点："; vexs = new char[vexnum]; for(int i=0;i<vexnum;i++) cin>>vexs[i]; arcs = new int*[vexnum]; for(int i=0;i<vexnum;i++) arcs[i] = new int[vexnum]; for(int i=0;i<vexnum;i++) for(int j=0;j<vexnum;j++) arcs[i][j] = Infinite; cout<<"请输入边数："; cin>>arcnum; cout<<"请为各边赋值"<<endl; int v1, v2; int cost; for(int i=0;i<arcnum;i++) { cout<<"请输入边的顶点："; cin>>v1; cin>>v2; cout<<"请输入权值："; cin>>cost; arcs[v1-1][v2-1] = cost; arcs[v2-1][v1-1] = cost; } } int Graph::LocateVex(char ch) { for(int i=0;i<vexnum;i++) { if(vexs[i]==ch) return i; } } void Graph::print() { for(int i=0;i<vexnum;i++) { for(int j=0;j<vexnum;j++) cout<<arcs[i][j]<<" "; cout<<endl; } } int Graph::getvexnum() { return vexnum; } void Prim() { Graph g; cout<<"起始点："; char u; cin>>u; int k = g.LocateVex(u); for(int i=0;i<g.getvexnum();i++) if(i!=k) closedge[i] = {u, g.arcs[k][i]}; closedge[k].lowcost = 0; cout<<endl; for(int j=1;j<g.getvexnum();j++) { int min = Infinite; for(int i=0;i<g.getvexnum();i++) { if(closedge[i].lowcost!=0&&closedge[i].lowcost<min) { min = closedge[i].lowcost; k = i; } } cout<<closedge[k].adjvex<<"--"<<g.vexs[k]<<endl; closedge[k].lowcost = 0; for(int j=0;j<g.getvexnum();j++)//辅助数组初始化 if(g.arcs[k][j]<closedge[j].lowcost) closedge[j] = {g.vexs[k], g.arcs[k][j]}; } } int main() { Prim(); return 0; }