最小生成树（prim）

  1 #include <iostream>
  2 #include <vector>
  3 #include <queue>
  4 #include <list>
  5 using namespace std;
  6 
  7 vector<pair<int,int> > eg[100];
  8 
  9 vector<pair<int,int> > result;
 10 
 11 typedef pair<int,int> pa;
 12 
 13 bool visit[100];
 14 
 15 list<int> setOfPrim;
 16 
 17 list<int> outOfPrim;
 18 
 19 int lowcost[100] = {0};
 20 
 21 void prim(int n,int d)
 22 {
 23           int min,aim,sta;
 24           bool is;
 25 
 26           list<int>::iterator sop;//最小树集合
 27           list<int>::iterator oop;//其他集合
 28           vector<pair<int,int> >::iterator it;
 29 
 30           setOfPrim.push_back(0);//放入起始点0进最小树集合
 31 
 32           //初始化其他集合
 33           for(int i = 1;i<n;i++)
 34                    outOfPrim.push_back(i);
 35 
 36           while(!outOfPrim.empty())//其他集合不为空
 37           {
 38                     //遍历最小树集合，sop，寻找与集合最近的点
 39                     min = 1<<16;
 40                     for(sop = setOfPrim.begin();sop!=setOfPrim.end();sop++)
 41                     {
 42                               //遍历sop邻接点
 43                               for(int i = 0;i<eg[*sop].size();i++)
 44                               {
 45                                         pa x = eg[*sop][i];
 46                                         is = false;
 47 
 48                                         //如果点属于oop集合
 49                                         for(oop = outOfPrim.begin();oop!=outOfPrim.end();oop++)
 50                                         {
 51                                                   if(*oop == x.first)
 52                                                   {
 53                                                             is = true;
 54                                                   }
 55                                         }
 56 
 57                                         if(is)
 58                                         {
 59                                                   if(x.second<min)
 60                                                   {
 61                                                             min = x.second;
 62                                                             aim = x.first;
 63                                                             sta = *sop;
 64                                                   }
 65                                                   //min存放了离sop集合最近的点的距离
 66                                                   //aim存放了点的序号
 67                                         }
 68                               }
 69                     }
 70 
 71                     setOfPrim.push_back(aim);
 72                     result.push_back(make_pair(sta,aim));
 73                     for(oop = outOfPrim.begin(); oop != outOfPrim.end(); )
 74                     {
 75                               if(*oop == aim)
 76                               {
 77                                         oop = outOfPrim.erase(oop);
 78                                         if(outOfPrim.empty())
 79                                                   break;
 80                               }
 81                               else
 82                                         oop++;
 83                     }
 84                     cout<<"The set of prim:\n";
 85                     for(sop = setOfPrim.begin(); sop != setOfPrim.end();sop++)
 86                     {
 87                               cout<<*sop<<" ";
 88                     }
 89                     cout<<"\nThe set of not prim:\n";
 90                     for(oop = outOfPrim.begin(); oop != outOfPrim.end();oop++)
 91                     {
 92                               cout<<*oop<<" ";
 93                     }
 94                     cout<<endl;
 95 
 96                     for(it = result.begin();it!=result.end();it++)
 97                     {
 98 
 99                               cout<<"("<<(*it).first<<","<<(*it).second<<")";
100                     }
101                     cout<<endl<<endl;
102           }
103 }
104 
105 
106 int main()
107 {
108           int n,d;
109           cin>>n>>d;
110           for(int i = 0;i<d;i++)
111           {
112                     int t,s,w;
113                     cin>>t>>s>>w;
114                     eg[t].push_back(make_pair(s,w));
115                     eg[s].push_back(make_pair(t,w));
116           }
117           prim(n,d);
118 
119 
120 
121 }
122 /*
123 6 8
124 0 1 2
125 0 3 4
126 1 4 4
127 2 0 5
128 2 5 2
129 3 4 3
130 3 5 7
131 5 4 3
132 */