最小生成树的PRIM算法（即时版本）

  1 #include 
  2 #include 
  3 #include 
  4 #include <set>
  5 #include 
  6 #include 
  7 
  8 using namespace std;
  9 
 10 
 11 class edge{
 12 private:
 13     double weight;
 14     int v;
 15     int w;
 16 public:
 17     edge() = default;  // 用 = default 来告诉编译器要为我们创建默认构造函数 （因为自定义了有参数的构造函数后编译器就不会创建默认构造函数）
 18     edge(const edge&) = default;   // !!!
 19     edge(edge &e){weight = e.weight;v = e.v; w = e.w;}
 20     edge(int _v, int _w, double _weight):v(_v),w(_w),weight(_weight){}
 21     double getWeight() const {return weight;}   // 为什么要在后面加const? 因为当edge是一个const实例时，也调用这个函数（否则报错）
 22     int either(){return v;}
 23     int another(int k) const {if(k == v)return w;else if(k == w)return v;}
 24     bool operator<(const edge &ed) const;  //should be friend?(不用，因为是自己的成员运算符，所以可以访问ed的私有成员)
 25     bool operator>(const edge &ed){return !operator<(ed);}
 26     void show() const {cout << "v: " << v << " w: " << w << " weight: " << weight << endl;}  // 没有const会报错： passing ‘const edge’ as ‘this’ argument discards qualifiers [-fpermissive]: ed.show();
 27     virtual ~edge(){}
 28 };
 29 
 30 bool edge::operator<(const edge &ed) const{
 31     return weight < ed.weight;
 32 }
 33 
 34 class graph{
 35 private:
 36     map<int, set> adj;  //这样直接把edge存放到set中有什么不妥吗？是不是应该用智能指针管理？
 37     int V;
 38     int E;
 39 public:
 40     graph(ifstream &in);
 41     map<int, set> getAdj();
 42     void show();
 43     int getv(){return V;}
 44     set<int> getAlle();
 45     set getEdge(int v);
 46     ~graph(){}
 47 };
 48 
 49 graph::graph(ifstream &in){
 50     in >> V >> E;
 51     int v, w;
 52     double weight;
 53     while(in >> v >> w >> weight){
 54         //edge temp(v,w,weight);
 55         auto v_iter = adj.find(v);
 56         if(v_iter != adj.end()){
 57             v_iter->second.emplace(v,w,weight);
 58         }
 59         else{
 60             set temps;
 61             temps.emplace(v,w,weight);
 62             adj[v] = temps;
 63         }
 64         auto w_iter = adj.find(w);
 65         if(w_iter != adj.end()){
 66             w_iter->second.emplace(v,w,weight);
 67         }
 68         else{
 69             set temps;
 70             temps.emplace(v,w,weight);
 71             adj[w] = temps;
 72         }
 73     }
 74 }
 75 
 76 set<int> graph::getAlle(){
 77     set<int> temp;
 78     for(auto &item : adj){
 79         temp.insert(item.first);
 80     }
 81 
 82     return temp;
 83 }
 84 
 85 set graph::getEdge(int v){
 86     return adj[v];
 87 }
 88 
 89 void graph::show(){
 90     for(auto & item : adj){
 91         cout << "node: " << item.first << endl;
 92         for(auto &ed : item.second){
 93             ed.show();
 94         }
 95 
 96     }
 97 }
 98 
 99 class primMST
100 {
101 private:
102     graph gp;
103     map<int, bool> marked;
104     map<int, edge> edgeTo;  
105     map<int, double> dist;  //edgeTo, dist 必须同时更新，因为他们是同一个节点对应的2个值
106     set<int> que;
107 public:
108     primMST() = delete;
109     int getMin();
110     primMST(graph &_gp);
111     void visit(int v);
112     void show() const;
113     ~primMST(){}
114 };
115 
116 primMST::primMST(graph &_gp):gp(_gp){
117     int num = gp.getv();
118     set<int> alle = gp.getAlle();
119     for(auto &item : alle){
120         dist[item] = INT32_MAX;
121     }
122     int seed = *(alle.begin());
123     cout << "seed: " << seed << endl;
124     dist[seed] = 0.0;
125     que.insert(seed);
126     while (que.size()!=0)
127     {
128         visit(getMin());
129     }
130 
131 }
132 
133 int primMST::getMin(){
134     int minior;
135     double weight = INT32_MAX;
136     for_each(que.begin(), que.end(), [&](const int &item){if(this->dist[item] < weight){minior=item;weight = this->dist[item];}});
137     que.erase(minior);
138     return minior;
139 }
140 
141 void primMST::visit(int v){
142     marked[v]= true;
143     auto allEdge = gp.getEdge(v);
144     for(auto &e : allEdge){  // 因为这里迭代的每一项e是个const对象，所以下面使用e的类方法必须确保不会改变e的成员变量（所以这些类方法必须在声名式和定义式后加const（即表示不会修改类内成员））
145         int w = e.another(v);
146         if(marked.find(w)!=marked.end())continue;
147         if(e.getWeight() < dist[w]){  //  dist[w] == edgeTo[w].getWeight()
148             edgeTo[w] = e;  // 注意不能用 edgeTo.insert(make_pair(w, e)); 当w重复时就会插入失败， 不像 edgeTo[w] = e 一样会更新
149             dist[w] = e.getWeight();
150         }
151         if(que.find(w)==que.end()){
152             que.insert(w);
153         }
154     }
155 }
156 
157 void primMST::show() const{
158     cout << "the selected edge: " << endl;
159     for_each(edgeTo.begin(), edgeTo.end(), [](auto &item){cout << "node " << item.first << ": "; item.second.show();});
160 }
161 
162 
163 int main(){
164     edge a(1,2,3);
165     edge b(4,5,6);
166     if(a>b) cout << "a" << endl;
167 
168     ifstream file("/home/tanweimin/code/program_practice/ALGORITHM/sort/MST.txt");
169     graph gp(file);
170     gp.show();
171     primMST pm(gp);
172     pm.show();
173 
174     return 0;
175 }

预期结果：

the selected edge: 
node 1: v: 1 w: 7 weight: 0.19
node 2: v: 0 w: 2 weight: 0.26
node 3: v: 2 w: 3 weight: 0.17
node 4: v: 4 w: 5 weight: 0.35
node 5: v: 5 w: 7 weight: 0.28
node 6: v: 6 w: 2 weight: 0.4
node 7: v: 0 w: 7 weight: 0.16

MST.txt

算法

最小生成树的PRIM算法（即时版本）

相关

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

【莫队算法】

算法第四章实践报告

关于tarjan算法的一些整理

【基础】排序算法学习笔记

常用的排序算法介绍和在JAVA的实现（一）

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

标签