第76课最小生成树（Prim）

图解：

添加prim函数：

  1 #ifndef GRAPH_H
  2 #define GRAPH_H
  3 
  4 #include "Object.h"
  5 #include "SharedPointer.h"
  6 #include "Array.h"
  7 #include "DynamicArray.h"
  8 #include "LinkQueue.h"
  9 #include "LinkStack.h"
 10 
 11 namespace DTLib
 12 {
 13 
 14 template < typename E >
 15 struct Edge : public Object
 16 {
 17     int b;
 18     int e;
 19     E data;
 20 
 21     Edge(int i=-1, int j=-1)
 22     {
 23         b = i;
 24         e = j;
 25     }
 26 
 27     Edge(int i, int j, const E& value)
 28     {
 29         b = i;
 30         e = j;
 31         data = value;
 32     }
 33 
 34     bool operator == (const Edge<E>& obj)
 35     {
 36         return (b == obj.b) && (e == obj.e);  //在这里不关注权值大小
 37     }
 38 
 39     bool operator != (const Edge<E>& obj)
 40     {
 41         return !(*this == obj);
 42     }
 43 };
 44 
 45 template < typename V, typename E >
 46 class Graph : public Object
 47 {
 48 protected:
 49     template < typename T >
 50     DynamicArray<T>* toArray(LinkQueue<T>& queue)
 51     {
 52         DynamicArray<T>* ret = new DynamicArray<T>(queue.length());
 53 
 54         if( ret != NULL )
 55         {
 56             for(int i=0; i<ret->length(); i++, queue.remove())
 57             {
 58                 ret->set(i, queue.front());
 59             }
 60         }
 61         else
 62         {
 63             THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create ret object...");
 64         }
 65 
 66         return ret;
 67     }
 68 public:
 69     virtual V getVertex(int i) = 0;
 70     virtual bool getVertex(int i, V& value) = 0;
 71     virtual bool setVertex(int i, const V& value) = 0;
 72     virtual SharedPointer< Array<int> > getAdjacent(int i) = 0;
 73     virtual bool isAdjacent(int i, int j) = 0;
 74     virtual E getEdge(int i, int j) = 0;
 75     virtual bool getEdge(int i, int j, E& value) = 0;
 76     virtual bool setEdge(int i, int j, const E& value) = 0;
 77     virtual bool removeEdge(int i, int j) = 0;
 78     virtual int vCount() = 0;
 79     virtual int eCount() = 0;
 80     virtual int OD(int i) = 0;
 81     virtual int ID(int i) = 0;
 82 
 83     virtual int TD(int i)
 84     {
 85         return ID(i) + OD(i);
 86     }
 87 
 88     bool asUndirected()
 89     {
 90         bool ret = true;
 91 
 92         for(int i=0; i<vCount(); i++)
 93         {
 94             for(int j=0; j<vCount(); j++)
 95             {
 96                 if( isAdjacent(i, j) )
 97                 {
 98                     ret = ret && isAdjacent(j, i) && (getEdge(i, j) == getEdge(j, i));
 99                 }
100             }
101         }
102 
103         return ret;
104     }
105 
106     SharedPointer< Array< Edge<E > > > prim(const E& LIMIT) //参数为理论上的最大权值
107     {
108         LinkQueue< Edge<E> > ret;
109 
110         if( asUndirected() )
111         {
112             DynamicArray<int> adjVex(vCount());
113             DynamicArray<bool> mark(vCount());
114             DynamicArray<E> cost(vCount());
115             SharedPointer< Array<int> > aj = NULL;
116             bool end = false;
117             int v = 0;
118 
119             for(int i=0; i<vCount(); i++)
120             {
121                 adjVex[i] = -1;
122                 mark[i] = false;
123                 cost[i] = LIMIT;
124             }
125 
126             mark[v] = true;
127 
128             aj = getAdjacent(v);
129 
130             for(int j=0; j<aj->length(); j++)
131             {
132                 cost[(*aj)[j]] = getEdge(v, (*aj)[j]);
133                 adjVex[(*aj)[j]] = v;
134             }
135 
136             for(int i=0; (i<vCount()) && !end; i++)
137             {
138                 E m = LIMIT;
139                 int k = -1;
140 
141                 for(int j=0; j<vCount(); j++)
142                 {
143                     if( !mark[j] && (cost[j] < m))
144                     {
145                         m = cost[j];
146                         k = j;
147                     }
148                 }
149 
150                 end = (k == -1);
151 
152                 if( !end )
153                 {
154                     ret.add(Edge<E>(adjVex[k], k, getEdge(adjVex[k], k)));
155 
156                     mark[k] = true;
157 
158                     aj = getAdjacent(k);
159 
160                     for(int j=0; j<aj->length(); j++)
161                     {
162                         if( !mark[(*aj)[j]] && (getEdge(k, (*aj)[j]) < cost[(*aj)[j]]) )
163                         {
164                             cost[(*aj)[j]] = getEdge(k, (*aj)[j]);
165                             adjVex[(*aj)[j]] = k;
166                         }
167                     }
168                 }
169             }
170         }
171         else
172         {
173             THROW_EXCEPTION(InvalidOperationException, "Prim operator is for undirected graph only...");
174         }
175 
176         if( ret.length() != (vCount() - 1) )
177         {
178             THROW_EXCEPTION(InvalidOperationException, "No enough edge for prim operation...");
179         }
180 
181         return toArray(ret);
182     }
183 
184     SharedPointer< Array<int> > BFS(int i)
185     {
186         DynamicArray<int>* ret = NULL;
187 
188         if( (0 <= i) && (i < vCount()) )
189         {
190             LinkQueue<int> q;
191             LinkQueue<int> r;
192             DynamicArray<bool> visited(vCount());
193 
194             for(int i=0; i<visited.length(); i++)
195             {
196                 visited[i] = false;
197             }
198 
199             q.add(i);
200 
201             while( q.length() > 0 )
202             {
203                 int v = q.front();
204 
205                 q.remove();
206 
207                 if( !visited[v] )
208                 {
209                     SharedPointer< Array<int> > aj = getAdjacent(v);
210 
211                     for(int j=0; j<aj->length(); j++)
212                     {
213                         q.add((*aj)[j]);
214                     }
215 
216                     r.add(v);
217 
218                     visited[v] = true;
219                 }
220             }
221 
222             ret = toArray(r);
223         }
224         else
225         {
226             THROW_EXCEPTION(InvalidParameterException, "Index i is invalid...");
227         }
228 
229         return ret;
230     }
231 
232     SharedPointer< Array<int> > DFS(int i)
233     {
234         DynamicArray<int>* ret = NULL;
235 
236         if( (0 <= i) && (i < vCount()) )
237         {
238             LinkStack<int> s;
239             LinkQueue<int> r;
240             DynamicArray<bool> visited(vCount());
241 
242             for(int j=0; j<visited.length(); j++)
243             {
244                 visited[j] = false;
245             }
246 
247             s.push(i);
248 
249             while( s.size() > 0 )
250             {
251                 int v = s.top();
252 
253                 s.pop();
254 
255                 if( !visited[v] )
256                 {
257                     SharedPointer< Array<int> > aj = getAdjacent(v);
258 
259                     for(int j=aj->length() - 1; j>=0; j--)
260                     {
261                         s.push((*aj)[j]);
262                     }
263 
264                     r.add(v);
265 
266                     visited[v] = true;
267                 }
268             }
269 
270             ret = toArray(r);
271         }
272         else
273         {
274             THROW_EXCEPTION(InvalidParameterException, "Index i is invalid...");
275         }
276 
277         return ret;
278     }
279 
280 };
281 
282 }
283 
284 #endif // GRAPH_H

测试程序如下：

  1 #include <iostream>
  2 #include "MatrixGraph.h"
  3 #include "ListGraph.h"
  4 
  5 using namespace std;
  6 using namespace DTLib;
  7 
  8 template< typename V, typename E >
  9 Graph<V, E>& GraphEasy()
 10 {
 11     static MatrixGraph<4, V, E> g;
 12 
 13     g.setEdge(0, 1, 1);
 14     g.setEdge(1, 0, 1);
 15 
 16     g.setEdge(0, 2, 3);
 17     g.setEdge(2, 0, 3);
 18 
 19     g.setEdge(1, 2, 1);
 20     g.setEdge(2, 1, 1);
 21 
 22     g.setEdge(1, 3, 4);
 23     g.setEdge(3, 1, 4);
 24 
 25     g.setEdge(2, 3, 1);
 26     g.setEdge(3, 2, 1);
 27 
 28     return g;
 29 }
 30 
 31 template< typename V, typename E >
 32 Graph<V, E>& GraphComplex()
 33 {
 34     static ListGraph<V, E> g(9);
 35 
 36     g.setEdge(0, 1, 10);
 37     g.setEdge(1, 0, 10);
 38 
 39     g.setEdge(0, 5, 11);
 40     g.setEdge(5, 0, 11);
 41 
 42     g.setEdge(1, 2, 18);
 43     g.setEdge(2, 1, 18);
 44 
 45     g.setEdge(1, 8, 12);
 46     g.setEdge(8, 1, 12);
 47 
 48     g.setEdge(1, 6, 16);
 49     g.setEdge(6, 1, 16);
 50 
 51     g.setEdge(2, 3, 22);
 52     g.setEdge(3, 2, 22);
 53 
 54     g.setEdge(2, 8, 8);
 55     g.setEdge(8, 2, 8);
 56 
 57     g.setEdge(3, 8, 21);
 58     g.setEdge(8, 3, 21);
 59 
 60     g.setEdge(3, 6, 24);
 61     g.setEdge(6, 3, 24);
 62 
 63     g.setEdge(3, 7, 16);
 64     g.setEdge(7, 3, 16);
 65 
 66     g.setEdge(3, 4, 20);
 67     g.setEdge(4, 3, 20);
 68 
 69     g.setEdge(4, 5, 26);
 70     g.setEdge(5, 4, 26);
 71 
 72     g.setEdge(4, 7, 7);
 73     g.setEdge(7, 4, 7);
 74 
 75     g.setEdge(5, 6, 17);
 76     g.setEdge(6, 5, 17);
 77 
 78     g.setEdge(6, 7, 19);
 79     g.setEdge(7, 6, 19);
 80 
 81     return g;
 82 }
 83 
 84 int main()
 85 {
 86     Graph<int, int>& g = GraphEasy<int, int>();
 87 
 88     SharedPointer< Array< Edge<int> > > sa = g.prim(65535);
 89 
 90     int w = 0;
 91 
 92     for(int i=0; i<sa->length(); i++)
 93     {
 94         w += (*sa)[i].data;
 95         cout << (*sa)[i].b << " " << (*sa)[i].e << " " << (*sa)[i].data << endl;
 96     }
 97 
 98     cout << "Weight: " << w << endl;
 99 
100     return 0;
101 }

结果如下：

复杂图的结果如下：

改进函数，支持最大生成树：

  1 #ifndef GRAPH_H
  2 #define GRAPH_H
  3 
  4 #include "Object.h"
  5 #include "SharedPointer.h"
  6 #include "Array.h"
  7 #include "DynamicArray.h"
  8 #include "LinkQueue.h"
  9 #include "LinkStack.h"
 10 
 11 namespace DTLib
 12 {
 13 
 14 template < typename E >
 15 struct Edge : public Object
 16 {
 17     int b;
 18     int e;
 19     E data;
 20 
 21     Edge(int i=-1, int j=-1)
 22     {
 23         b = i;
 24         e = j;
 25     }
 26 
 27     Edge(int i, int j, const E& value)
 28     {
 29         b = i;
 30         e = j;
 31         data = value;
 32     }
 33 
 34     bool operator == (const Edge<E>& obj)
 35     {
 36         return (b == obj.b) && (e == obj.e);  //在这里不关注权值大小
 37     }
 38 
 39     bool operator != (const Edge<E>& obj)
 40     {
 41         return !(*this == obj);
 42     }
 43 };
 44 
 45 template < typename V, typename E >
 46 class Graph : public Object
 47 {
 48 protected:
 49     template < typename T >
 50     DynamicArray<T>* toArray(LinkQueue<T>& queue)
 51     {
 52         DynamicArray<T>* ret = new DynamicArray<T>(queue.length());
 53 
 54         if( ret != NULL )
 55         {
 56             for(int i=0; i<ret->length(); i++, queue.remove())
 57             {
 58                 ret->set(i, queue.front());
 59             }
 60         }
 61         else
 62         {
 63             THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create ret object...");
 64         }
 65 
 66         return ret;
 67     }
 68 public:
 69     virtual V getVertex(int i) = 0;
 70     virtual bool getVertex(int i, V& value) = 0;
 71     virtual bool setVertex(int i, const V& value) = 0;
 72     virtual SharedPointer< Array<int> > getAdjacent(int i) = 0;
 73     virtual bool isAdjacent(int i, int j) = 0;
 74     virtual E getEdge(int i, int j) = 0;
 75     virtual bool getEdge(int i, int j, E& value) = 0;
 76     virtual bool setEdge(int i, int j, const E& value) = 0;
 77     virtual bool removeEdge(int i, int j) = 0;
 78     virtual int vCount() = 0;
 79     virtual int eCount() = 0;
 80     virtual int OD(int i) = 0;
 81     virtual int ID(int i) = 0;
 82 
 83     virtual int TD(int i)
 84     {
 85         return ID(i) + OD(i);
 86     }
 87 
 88     bool asUndirected()
 89     {
 90         bool ret = true;
 91 
 92         for(int i=0; i<vCount(); i++)
 93         {
 94             for(int j=0; j<vCount(); j++)
 95             {
 96                 if( isAdjacent(i, j) )
 97                 {
 98                     ret = ret && isAdjacent(j, i) && (getEdge(i, j) == getEdge(j, i));
 99                 }
100             }
101         }
102 
103         return ret;
104     }
105 
106     SharedPointer< Array< Edge<E > > > prim(const E& LIMIT, const bool MINIUM = true) //参数为理论上的最大权值
107     {
108         LinkQueue< Edge<E> > ret;
109 
110         if( asUndirected() )
111         {
112             DynamicArray<int> adjVex(vCount());
113             DynamicArray<bool> mark(vCount());
114             DynamicArray<E> cost(vCount());
115             SharedPointer< Array<int> > aj = NULL;
116             bool end = false;
117             int v = 0;
118 
119             for(int i=0; i<vCount(); i++)
120             {
121                 adjVex[i] = -1;
122                 mark[i] = false;
123                 cost[i] = LIMIT;
124             }
125 
126             mark[v] = true;
127 
128             aj = getAdjacent(v);
129 
130             for(int j=0; j<aj->length(); j++)
131             {
132                 cost[(*aj)[j]] = getEdge(v, (*aj)[j]);
133                 adjVex[(*aj)[j]] = v;
134             }
135 
136             for(int i=0; (i<vCount()) && !end; i++)
137             {
138                 E m = LIMIT;
139                 int k = -1;
140 
141                 for(int j=0; j<vCount(); j++)
142                 {
143                     if( !mark[j] && (MINIUM ? (cost[j] < m) : (cost[j] > m)))
144                     {
145                         m = cost[j];
146                         k = j;
147                     }
148                 }
149 
150                 end = (k == -1);
151 
152                 if( !end )
153                 {
154                     ret.add(Edge<E>(adjVex[k], k, getEdge(adjVex[k], k)));
155 
156                     mark[k] = true;
157 
158                     aj = getAdjacent(k);
159 
160                     for(int j=0; j<aj->length(); j++)
161                     {
162                         if( !mark[(*aj)[j]] && (MINIUM ? (getEdge(k, (*aj)[j]) < cost[(*aj)[j]]) : (getEdge(k, (*aj)[j]) > cost[(*aj)[j]])) )
163                         {
164                             cost[(*aj)[j]] = getEdge(k, (*aj)[j]);
165                             adjVex[(*aj)[j]] = k;
166                         }
167                     }
168                 }
169             }
170         }
171         else
172         {
173             THROW_EXCEPTION(InvalidOperationException, "Prim operator is for undirected graph only...");
174         }
175 
176         if( ret.length() != (vCount() - 1) )
177         {
178             THROW_EXCEPTION(InvalidOperationException, "No enough edge for prim operation...");
179         }
180 
181         return toArray(ret);
182     }
183 
184     SharedPointer< Array<int> > BFS(int i)
185     {
186         DynamicArray<int>* ret = NULL;
187 
188         if( (0 <= i) && (i < vCount()) )
189         {
190             LinkQueue<int> q;
191             LinkQueue<int> r;
192             DynamicArray<bool> visited(vCount());
193 
194             for(int i=0; i<visited.length(); i++)
195             {
196                 visited[i] = false;
197             }
198 
199             q.add(i);
200 
201             while( q.length() > 0 )
202             {
203                 int v = q.front();
204 
205                 q.remove();
206 
207                 if( !visited[v] )
208                 {
209                     SharedPointer< Array<int> > aj = getAdjacent(v);
210 
211                     for(int j=0; j<aj->length(); j++)
212                     {
213                         q.add((*aj)[j]);
214                     }
215 
216                     r.add(v);
217 
218                     visited[v] = true;
219                 }
220             }
221 
222             ret = toArray(r);
223         }
224         else
225         {
226             THROW_EXCEPTION(InvalidParameterException, "Index i is invalid...");
227         }
228 
229         return ret;
230     }
231 
232     SharedPointer< Array<int> > DFS(int i)
233     {
234         DynamicArray<int>* ret = NULL;
235 
236         if( (0 <= i) && (i < vCount()) )
237         {
238             LinkStack<int> s;
239             LinkQueue<int> r;
240             DynamicArray<bool> visited(vCount());
241 
242             for(int j=0; j<visited.length(); j++)
243             {
244                 visited[j] = false;
245             }
246 
247             s.push(i);
248 
249             while( s.size() > 0 )
250             {
251                 int v = s.top();
252 
253                 s.pop();
254 
255                 if( !visited[v] )
256                 {
257                     SharedPointer< Array<int> > aj = getAdjacent(v);
258 
259                     for(int j=aj->length() - 1; j>=0; j--)
260                     {
261                         s.push((*aj)[j]);
262                     }
263 
264                     r.add(v);
265 
266                     visited[v] = true;
267                 }
268             }
269 
270             ret = toArray(r);
271         }
272         else
273         {
274             THROW_EXCEPTION(InvalidParameterException, "Index i is invalid...");
275         }
276 
277         return ret;
278     }
279 
280 };
281 
282 }
283 
284 #endif // GRAPH_H

测试程序如下：

  1 #include <iostream>
  2 #include "MatrixGraph.h"
  3 #include "ListGraph.h"
  4 
  5 using namespace std;
  6 using namespace DTLib;
  7 
  8 template< typename V, typename E >
  9 Graph<V, E>& GraphEasy()
 10 {
 11     static MatrixGraph<4, V, E> g;
 12 
 13     g.setEdge(0, 1, 1);
 14     g.setEdge(1, 0, 1);
 15 
 16     g.setEdge(0, 2, 3);
 17     g.setEdge(2, 0, 3);
 18 
 19     g.setEdge(1, 2, 1);
 20     g.setEdge(2, 1, 1);
 21 
 22     g.setEdge(1, 3, 4);
 23     g.setEdge(3, 1, 4);
 24 
 25     g.setEdge(2, 3, 1);
 26     g.setEdge(3, 2, 1);
 27 
 28     return g;
 29 }
 30 
 31 template< typename V, typename E >
 32 Graph<V, E>& GraphComplex()
 33 {
 34     static ListGraph<V, E> g(9);
 35 
 36     g.setEdge(0, 1, 10);
 37     g.setEdge(1, 0, 10);
 38 
 39     g.setEdge(0, 5, 11);
 40     g.setEdge(5, 0, 11);
 41 
 42     g.setEdge(1, 2, 18);
 43     g.setEdge(2, 1, 18);
 44 
 45     g.setEdge(1, 8, 12);
 46     g.setEdge(8, 1, 12);
 47 
 48     g.setEdge(1, 6, 16);
 49     g.setEdge(6, 1, 16);
 50 
 51     g.setEdge(2, 3, 22);
 52     g.setEdge(3, 2, 22);
 53 
 54     g.setEdge(2, 8, 8);
 55     g.setEdge(8, 2, 8);
 56 
 57     g.setEdge(3, 8, 21);
 58     g.setEdge(8, 3, 21);
 59 
 60     g.setEdge(3, 6, 24);
 61     g.setEdge(6, 3, 24);
 62 
 63     g.setEdge(3, 7, 16);
 64     g.setEdge(7, 3, 16);
 65 
 66     g.setEdge(3, 4, 20);
 67     g.setEdge(4, 3, 20);
 68 
 69     g.setEdge(4, 5, 26);
 70     g.setEdge(5, 4, 26);
 71 
 72     g.setEdge(4, 7, 7);
 73     g.setEdge(7, 4, 7);
 74 
 75     g.setEdge(5, 6, 17);
 76     g.setEdge(6, 5, 17);
 77 
 78     g.setEdge(6, 7, 19);
 79     g.setEdge(7, 6, 19);
 80 
 81     return g;
 82 }
 83 
 84 int main()
 85 {
 86     Graph<int, int>& g = GraphComplex<int, int>();
 87 
 88     SharedPointer< Array< Edge<int> > > sa = g.prim(0, false);
 89 
 90     int w = 0;
 91 
 92     for(int i=0; i<sa->length(); i++)
 93     {
 94         w += (*sa)[i].data;
 95         cout << (*sa)[i].b << " " << (*sa)[i].e << " " << (*sa)[i].data << endl;
 96     }
 97 
 98     cout << "Weight: " << w << endl;
 99 
100     return 0;
101 }

结果如下：

小结：

第76课 最小生成树（Prim）

第76课最小生成树（Prim）