#include <iostream>
#include <stdlib.h>
#include<string>
#include<vector>
#define max_vex 6
typedef struct{
string s;
int lowcast;
}mm;
string ss[max_vex]={"v1","v2","v3","v4","v5","v6"};
mm closedge[max_vex];
mm arcs[max_vex][max_vex];
vector<string> G(ss,ss+max_vex); //////初始化
vector<string> U; //用于记录依次添加的结点
int locatevex(vector<string> G,string u)
{
int iter1=0;
while(iter1<G.size())
{
if(u==G[iter1]) return iter1;
++iter1;
}
}
int minimum(mm *closedge)
{
int min=32;
int p;
for(int i=0;i<max_vex;i++)
if(min>closedge[i].lowcast &&closedge[i].s!="NULL") {p=i; min=closedge[i].lowcast;}
return p;
}
int main(int argc, char *argv[])
{
int sum=0;
string u;
int i,j;
cout<<"请输入CARS初始用数组："<<endl;
for(i=0;i<max_vex;i++)
for(j=0;j<max_vex;j++)
cin>>arcs[i][j].s>>arcs[i][j].lowcast;
u="v1";
cout<<u; ////确定第一个结点
cout<<endl;
int k=locatevex(G,u);
for(j=0;j<G.size();j++)
if(j!=k) {closedge[j].s=u; closedge[j].lowcast=arcs[k][j].lowcast;} ////辅助数组的初始化
closedge[k].lowcast=0;
closedge[k].s="NULL";
U.push_back(u); //////将第一个结点加入向量U中
for(i=1;i<G.size();i++)
{
k=minimum(closedge); /////找一个最短边的下标
cout<<closedge[k].lowcast;
cout<<G[k];
cout<<endl;
sum+=closedge[k].lowcast; ///加两结点间的路径和
U.push_back(G[k]);
closedge[k].lowcast=0;
closedge[k].s="NULL";
for(j=0;j<G.size();j++)
if(arcs[k][j].lowcast<closedge[j].lowcast)
{
closedge[j].lowcast=arcs[k][j].lowcast;
closedge[j].s=G[k];
}
}
cout<<endl;
for(i=0;i<U.size();i++)
cout<<U[i]<<" ";
cout<<"输出最小路径为："<<endl;
cout<<sum<<endl;
system("PAUSE");
return 0;
}
最近也许是因为整天在上算法分析，自己的兴趣也随着上课只增不减了，其实最小生成树早在大二一期就学了的。只是因为当时看到那书上的算法就晕，看不懂它是什么意思，也许最主要是自己没下功夫，也没到很冷静地去想那问题了，一直到现在，上节课老师也只是讲了思路，但总感觉自己会想应该就能编吧，下午家教回来本来想早点休息的，但无意看到了数据结构的书，就想到还有上节课的自己还想了一下子的最小生成算法，慢慢编下来，感觉还不错，终于明白很多事情只要开始了，还真的不难，虽然今天没做什么，这个题目也没什么难度感，但也让我更加体会到容器的使用，看来它们还真是个好东西。尽管没什么特大价值，但这个小问题也提升了自己的小小满足感。以后应该会耐心多了。还有很多任务等着呢？慢慢加油咯。