// ------------------------Prim()-----------------------------
/*
最小生成树算法
从Prim_in.txt文件中读入数据，将结果输出到Prim_out.txt中
输入格式：（以邻接矩阵为存储结构）
6
0 5 6 4 7 8
1 0 2 5 8 7
4 1 0 3 5 8
1 4 7 0 2 9
2 5 4 1 0 6
8 5 7 4 6 0
输出格式：
234 为最小生成树的边的权值之和
*/
#include<fstream>#define MaxNum 765432100;using namespace std;
ifstream fin("Prim_in.txt");// //以输入文件方式输入数据ofstream fout("Prim_out.txt");// //以输出文件方式输出结果
int p,q;bool is_arrived[501];// 用来判断该点是否已经被选入MST中int Length,Vertex,SetNum,State;int Map[501][501],Dist[501]; //Map[][]存放的是两点之间的距离Dist[]//Map[i][j]表示的是i到j的距离----->Dist[i]
//------------------------------------------------------------------- int FindMin(){int p;int Minm,Temp;Minm=MaxNum;Temp=0;for (p=1;p<=Vertex;p++) if ((Dist[p]<Minm)&&(!is_arrived[p])) { Minm=Dist[p]; Temp=p; }return Temp;// 返回P，也就是节点序号}
//---------------------------------------------------------------------int main(){memset(is_arrived,0,sizeof(is_arrived));//函数原型：void *memset(void *s, int ch, unsigned n);//将s所指向的某一块内存中的每个字节的内容全部设置为ch指定的ASCII值, 块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作//其返回值为指向S的指针，此处的作用是将所有节点在初始标记为：未加入MST集合fin >> Vertex;// 从文件读入一个整数赋值给Vertexfor (p=1;p<=Vertex;p++) for (q=1;q<=Vertex;q++) { fin >> Map[p][q]; //把Prim_in.txt中预先给定的数组赋值给Map[][]，表示的是点到点的距离 if (Map[p][q]==0) Map[p][q]=MaxNum; }Length=0; //初始总距离为0is_arrived[1]=true;// //把第一个节点纳入MST集合中，并标记为已加入for (p=1;p<=Vertex;p++) Dist[p]=Map[1][p]; // //Dist[p]存放的是1号节点到其他各点的距离 SetNum=1;//********************************************************************//**************以上所做全为初始工作，下面开始为核心******************//******************************************************************** do { State=FindMin();// //开始新一轮的遍历 if (State!=0)// //如果找到有未加入MST集合的点... { SetNum=SetNum+1;// //SetNum用来统计已经加入MST集合的点总数 is_arrived[State]=true;// //把该节点标记为：已加入MST集合 Length=Length+Dist[State];///总的权值 for (p=1;p<=Vertex;p++) if ((Map[State][p]<Dist[p])&&(!is_arrived[p]))//接着从这个节点开始计算 //它到与它相连的其他各点的权值最小者 Dist[p]=Map[State][p]; } else// 如果所有节点都加入MST集了，FindMin()返回的是Temp=0； break; } while (SetNum!=Vertex);// //当SetNum=Vertex时，所有点已经加入MST集合 //******************************至此为核心部分*****************************
//MST成功--->输出错误消息，失败--->输出总路径之和 if (SetNum!=Vertex) fout << "The graph is not connected!"; else fout << Length; fin.close(); fout.close(); return 0;}
