最小生成树算法，最短路径算法，网络流算法

andalousie

大家万事如意，大家心想事成。这里给出最小生成树的两种算法的C++版本。这里来列一下清单
主测试文件：
MST.cpp
图的头文件和实现文件
graph.h graph.cc
Prim算法的补充文件
List.h list.cc //用于实现一个简易的双向循环链优先队列
Kruskal算法的补充文件
DisjointSet.h DisjointSet.cc //用于实现并查集

MST.cpp

1. #include <iostream>
   
2. #include "graph.h"
   
3. 
   
4. int main(){   
   
5.         /** Creates a graph with 12 vertices */
   
6.     Graph g1(10);
   
7. 
   
8.     /** Adds edges to the graph */
   
9.     g1.addEdge(1, 2, 5); g1.addEdge(1, 3, 7);
   
10.     g1.addEdge(2, 3, 9); g1.addEdge(2, 6, 6);
    
11.     g1.addEdge(2, 5, 15); g1.addEdge(3, 4, 8);
    
12.     g1.addEdge(3, 5, 7); g1.addEdge(4, 5, 5);
    
13.     g1.addEdge(5, 6, 8); g1.addEdge(5, 7, 9);
    
14.     g1.addEdge(6, 7, 11);
    
15. 
    
16.     /** Explores all vertices findable from vertex 1 */
    
17.     g1.Prim(2);
    
18.     g1.Kruskal(2);
    
19. }

复制代码

graph.h

1. #if !defined (GRAPH_H)
   
2. #define GRAPH_H
   
3. 
   
4. /************************************************************
   
5. 
   
6. Class Graph represents a Graph [V,E] having vertices V and
   
7. edges E.
   
8. 
   
9. ************************************************************/
   
10. class Graph {
    
11.     private:
    
12.         int    _n;  /// n is the number of vertices in the graph
    
13.         int ** _A;  /// A stores the edges between two vertices
    
14.     public:
    
15.         Graph(int size = 2);
    
16.         ~Graph();
    
17.         bool isConnected(int, int);
    
18.         void addEdge(int x, int y, int d);
    
19.         void Prim(int s);
    
20.         void Kruskal(int s);
    
21. };
    
22. 
    
23. #endif

复制代码

graph.cc

1. #include <iostream>
   
2. #include "graph.h"
   
3. #include "List.h"
   
4. #include "DisjointSet.h"
   
5. 
   
6. Graph::Graph(int size) {
   
7.     int i, j;
   
8.     if (size < 2) _n = 2;
   
9.     else _n = size;
   
10.     _A = new int*[_n];
    
11.     for (i = 0; i < _n; ++i)
    
12.         _A[i] = new int[_n];
    
13.     for (i = 0; i < _n; ++i)
    
14.         for (j = 0; j < _n; ++j)
    
15.             _A[i][j] = 0;
    
16. }
    
17. 
    
18. Graph::~Graph() {
    
19.     for (int i = 0; i < _n; ++i)
    
20.     delete [] _A[i];
    
21.     delete [] _A;
    
22. }
    
23. 
    
24. /******************************************************
    
25. Checks if two given vertices are connected by an edge
    
26. @param u vertex
    
27. @param v vertex
    
28. @return true if connected false if not connected
    
29. ******************************************************/
    
30. bool Graph::isConnected(int x, int y) {
    
31.     return (_A[x-1][y-1] != 0);
    
32. }
    
33. 
    
34. /*****************************************************
    
35. adds an edge E to the graph G.
    
36. @param u vertex
    
37. @param v vertex
    
38. *****************************************************/
    
39. void Graph::addEdge(int x, int y, int d) {
    
40.     _A[x-1][y-1] = d; _A[y-1][x-1] = d;
    
41. }
    
42. 
    
43. /*****************************************************
    
44. performs Prim's algorithm
    
45. @param s initial vertex
    
46. *****************************************************/
    
47. void Graph::Prim(int s) {
    
48.     Queue Q;
    
49. 
    
50.     /** Keeps track of explored vertices */
    
51.     int  *explored = new int [_n+1];
    
52.     int  *grown    = new int [_n+1];
    
53.     bool *done     = new bool[_n+1];
    
54. 
    
55.     /** Initailized all vertices */
    
56.     for (int i = 1; i <= _n; ++i)
    
57.     {
    
58.         grown[i] = 0;
    
59.         done [i] = false;
    
60.                 if(isConnected(s, i))
    
61.                 {
    
62.                   prior D1(s, i, _A[s-1][i-1]);
    
63.                   Q.Put(D1);
    
64.                   explored[i] = _A[s-1][i-1];
    
65.                 }
    
66.                 else
    
67.                   explored[i] = 0;
    
68.     }
    
69.    
    
70.     grown   [1] = s;
    
71.     explored[s] = 1;
    
72.     done    [s] = true;
    
73. 
    
74.     int t = 2;
    
75.         /** Unless the queue is empty */
    
76.     while (!Q.isEmpty()) {
    
77.         
    
78.         prior e = Q.Get();
    
79.                 /** Pop the vertex from the queue */
    
80.         grown[t] = e.val;
    
81. 
    
82.                 /** display the explored vertices */
    
83.         std::cout << e.fval << "-" << e.val << " ";
    
84.         done[grown[t]] = true;
    
85. 
    
86.         /** From the explored vertex v try to explore all the
    
87.         connected vertices */
    
88.         for (int w = 1; w <= _n; ++w)
    
89. 
    
90.             /** Explores the vertex w if it is connected to v */
    
91.             if (isConnected(grown[t], w)) {
    
92.                 if(!explored[w])
    
93.                 {
    
94.                         prior D2(grown[t], w, _A[grown[t]-1][w-1]);
    
95.                                         /** adds the vertex w to the queue */
    
96.                         Q.Put(D2);
    
97.                         /** marks the vertex w as visited */
    
98.                         explored[w] = _A[grown[t]-1][w-1];
    
99.                 }
    
100.                                 else
     
101.                                 {
     
102.                                         if(!done[w] && _A[grown[t]-1][w-1] < explored[w])
     
103.                                         {
     
104.                                                 prior D3(grown[t], w, _A[grown[t]-1][w-1]);
     
105.                                                 Q.Push(D3);
     
106.                                                 explored[w] = _A[grown[t]-1][w-1];
     
107.                                         }
     
108.                                 }
     
109.             }
     
110.         t++;
     
111.     }
     
112.     std::cout << std::endl;
     
113.     delete [] explored;
     
114.     delete [] grown;
     
115.     delete [] done;
     
116. }
     
117. 
     
118. void Graph::Kruskal(int s) {
     
119.         Queue Q;
     
120.         DisjointSet UF(_n);
     
121.         for (int i=1; i<_n; ++i)
     
122.         {
     
123.                 for(int j=i+1; j<_n; ++j)
     
124.                 if(isConnected(i, j))
     
125.                 {
     
126.                   prior D1(i, j, _A[i-1][j-1]);
     
127.                   Q.Put(D1);
     
128.                 }
     
129.         }
     
130.         
     
131.         while (!Q.isEmpty() && UF.Count() != 1) {
     
132.                 prior e = Q.Get();
     
133.                 int v = e.fval; int w = e.val;
     
134.                 if(UF.Find(v, w)) continue;
     
135.                 UF.Unite(v, w);
     
136.                 std::cout << v << "-" << w << " ";
     
137.         }
     
138. }

复制代码

List.h

1. #if !defined (LIST_H)
   
2. #define LIST_H
   
3. 
   
4. class prior{
   
5. public:
   
6.         prior(int u, int v, int p)
   
7.          :fval(u), val(v), priority(p)
   
8.         {}
   
9.         int        fval;
   
10.         int        val;
    
11.         const int  priority;
    
12. };
    
13. 
    
14. class DLink
    
15. {
    
16. public:
    
17.         DLink (prior id)
    
18.                 : _id (id)
    
19.         {
    
20.                 _pPrev = this;
    
21.                 _pNext = this;
    
22.         }
    
23.         DLink *  Prev () const { return _pPrev; }
    
24.         DLink *  Next () const { return _pNext; }
    
25.         void    SetPrev (DLink* pPrev) { _pPrev = pPrev; }
    
26.         void    SetNext (DLink* pNext) { _pNext = pNext; }
    
27.         prior   Id () const { return _id; }
    
28.         void    Unlink();
    
29. private:
    
30.         DLink *  _pPrev;
    
31.         DLink *  _pNext;
    
32.         prior     _id;
    
33. };
    
34. 
    
35. class Queue
    
36. {
    
37. public:
    
38.         Queue (): _pHead (0) {}
    
39.         ~Queue ();
    
40.         void    Put ( prior id );
    
41.         void    Push ( prior id );
    
42.         prior   Get ();
    
43.         bool    isEmpty () { return _pHead == 0; }
    
44.         DLink * GetHead () const { return _pHead; }
    
45. protected:
    
46.         DLink*  _pHead;
    
47. };
    
48. 
    
49. #endif

复制代码

list.cc

1. #include "list.h"
   
2. #include <iostream>
   
3. #include <cassert>
   
4. 
   
5. void DLink::Unlink()
   
6. {
   
7.   assert (_pNext != 0);
   
8.   assert (_pPrev != 0);
   
9.   _pNext->SetPrev (_pPrev);
   
10.   _pPrev->SetNext (_pNext);
    
11.   _pPrev = this;
    
12.   _pNext = this;
    
13. }
    
14. 
    
15. void Queue::Put (prior id)
    
16. {
    
17.   DLink * pLink = new DLink (id);
    
18.   if (_pHead == 0)
    
19.     _pHead = pLink;
    
20.   else if(_pHead->Next () == _pHead)
    
21.   {
    
22.         pLink->SetNext (_pHead);
    
23.     pLink->SetPrev (_pHead->Prev ());
    
24.     _pHead->SetNext (pLink);
    
25.     _pHead->SetPrev (pLink);
    
26.     if(id.priority >= _pHead->Id().priority)
    
27.       _pHead = pLink;
    
28.   }
    
29.   else
    
30.   {
    
31.           DLink * tLink;
    
32.           for (tLink = GetHead();
    
33.          id.priority < tLink->Id().priority;
    
34.          tLink = tLink->Next ())
    
35.     {
    
36.             if(tLink == _pHead->Prev())
    
37.             {
    
38.                     if(id.priority < tLink->Id().priority)
    
39.                     {
    
40.                             pLink->SetNext (_pHead);
    
41.                             pLink->SetPrev (_pHead->Prev ());
    
42.                             _pHead->Prev ()->SetNext (pLink);
    
43.                             _pHead->SetPrev (pLink);
    
44.                             return;
    
45.                     }
    
46.                     break;
    
47.             }
    
48.     }
    
49.     pLink->SetNext (tLink);
    
50.     pLink->SetPrev (tLink->Prev ());
    
51.     pLink->Prev ()->SetNext (pLink);
    
52.     pLink->Next ()->SetPrev (pLink);
    
53.     if(tLink == _pHead)
    
54.                 _pHead = pLink;
    
55.   }
    
56. }
    
57. 
    
58. void Queue::Push (prior id)
    
59. {
    
60.   DLink * nLink = new DLink (id);
    
61.   if (_pHead == 0)
    
62.     _pHead = nLink;
    
63.   else if(_pHead->Next () == _pHead)
    
64.   {
    
65.           if(id.val == _pHead->Id().val)
    
66.           {
    
67.             _pHead = nLink;
    
68.             return;
    
69.           }
    
70.           else
    
71.             Put(id);
    
72.   }
    
73.   else
    
74.   {
    
75.           bool flag = false;
    
76.           for (DLink * fLink = GetHead();;
    
77.              fLink = fLink->Next ())
    
78.         {
    
79.                 if(fLink == _pHead->Prev())
    
80.                 {
    
81.                         if(id.val == fLink->Id().val)
    
82.                         {
    
83.                                 fLink->Unlink();
    
84.                                 flag = true;
    
85.                         }
    
86.                         flag = true;
    
87.                 }
    
88.                 if(id.val == fLink->Id().val)
    
89.                 {
    
90.                         if(fLink == _pHead)
    
91.                                 _pHead = _pHead->Next();
    
92.                         fLink->Unlink();
    
93.                         flag = true;
    
94.                 }
    
95.                 if(flag) break;
    
96.         }
    
97.         Put(id);
    
98.   }
    
99. }
    
100. 
     
101. prior Queue::Get ()
     
102. {
     
103.   assert (_pHead != 0);
     
104.   DLink * pLink = _pHead->Prev ();
     
105.   if (pLink == _pHead) // last one
     
106.     _pHead = 0;
     
107.   pLink->Unlink ();
     
108.   prior result = pLink->Id ();
     
109.   delete pLink;
     
110.   return result;
     
111. }
     
112. 
     
113. Queue::~Queue ()
     
114. {
     
115.   // free the Queue
     
116.   while ( _pHead != 0 )
     
117.   {
     
118.     DLink * pLink = _pHead->Prev ();
     
119.     if (pLink == _pHead)
     
120.       _pHead = 0;
     
121.     pLink->Unlink (); // unlink pLink
     
122.     delete pLink;
     
123.   }
     
124. }

复制代码

DisjointSet.h

1. #if !defined (DISJOINTSET_H)
   
2. #define DISJOINTSET_H
   
3. 
   
4. class DisjointSet
   
5. {
   
6. private:
   
7.         int *_id;   // parent link (site indexed)
   
8.         int *_sz;   // size of component for roots (site indexed)
   
9.         int _count; // number of components
   
10.         int _root(int i);
    
11. public:
    
12.         DisjointSet(int N);
    
13.         int Count() { return _count; }
    
14.         bool Find(int p,int q);
    
15.         void Unite(int p,int q);
    
16.         ~DisjointSet(void);
    
17. };
    
18. 
    
19. #endif

复制代码

DisjointSet.cc

1. #include "DisjointSet.h"
   
2. 
   
3. DisjointSet::DisjointSet(int N)
   
4. : _count(N)
   
5. {
   
6.     _id = new int[N];
   
7.     _sz = new int[N];
   
8.     for(int i=0; i<N; ++i)
   
9.     {
   
10.         _id[i] = i;
    
11.         _sz[i] = 1;
    
12.     }
    
13. }
    
14. 
    
15. int DisjointSet::_root(int i)
    
16. {
    
17.     while (i != _id[i])
    
18.     {
    
19.         _id[i] = _id[_id[i]]; //Path compression.
    
20.         i = _id[i];
    
21.     }
    
22.     return i;
    
23. }
    
24. 
    
25. bool DisjointSet::Find(int p, int q)
    
26. {
    
27.     return _root(p) == _root(q);
    
28. }
    
29. 
    
30. void DisjointSet::Unite(int p, int q)
    
31. {
    
32.     //Link root of smaller tree to root of larger tree.
    
33.     int i = _root(p);
    
34.     int j = _root(q);
    
35.     if(_sz[i] < _sz[j])
    
36.     {
    
37.         _id[i] = j; _sz[j] += _sz[i];
    
38.     }
    
39.     else
    
40.     {
    
41.         _id[j] = i; _sz[i] += _sz[j];
    
42.     }
    
43.     _count--;
    
44. }
    
45. 
    
46. DisjointSet::~DisjointSet(void)
    
47. {
    
48.     delete [] _id;
    
49.     delete [] _sz;
    
50. }

复制代码

结果输出

1. 2-1 2-6 1-3 3-5 5-4 5-7
   
2. 1-2 4-5 2-6 1-3 3-5 5-7

复制代码

第二个更新版本见4楼。改良了代码，还增加了Dijkstra最短路径算法。第三个更新版本见5楼，修改了代码以适应vc6.0，增加了网络流算法，修改了GenericPQ中null和Comp的实现。

andalousie

更新了算法，补充了Kruskal算法。 来看看吧

andalousie

其实大家应该发现我的山寨优先队列把复杂度直接拖到O(n^2)了吧。。。
可以看看这个，虽然只把顶点的遍历顺序输出出来了，但是这回的优先队列可是O(logn)的，这个代码段用了新的优先队列。

1. void Graph::Prim(int s) {
   
2.     PriorityQueue Q(24);
   
3. 
   
4.     /** Keeps track of explored vertices */
   
5.     int  *explored = new int [_n+1];
   
6.     int  *grown    = new int [_n+1];
   
7. 
   
8.     /** Initailized all vertices */
   
9.     for (int i = 1; i <= _n; ++i)
   
10.     {
    
11.         grown[i] = 0;
    
12.                 if(isConnected(s, i))
    
13.                 {
    
14.                   Q.insert(i, _A[s-1][i-1]);
    
15.                   explored[i] = _A[s-1][i-1];
    
16.                 }
    
17.                 else
    
18.                   explored[i] = 0;
    
19.     }
    
20.    
    
21.     grown   [1] = s;
    
22.     explored[s] = 1;
    
23.     std::cout << grown[1] << " ";
    
24. 
    
25.     int t = 2;
    
26.         /** Unless the queue is empty */
    
27.     while (!Q.isEmpty()) {
    
28.         
    
29.         /** Pop the vertex from the queue */
    
30.         grown[t] = Q.pop();
    
31. 
    
32.                 /** display the explored vertices */
    
33.         std::cout << grown[t] << " ";
    
34. 
    
35.         /** From the explored vertex v try to explore all the
    
36.         connected vertices */
    
37.         for (int w = 1; w <= _n; ++w)
    
38. 
    
39.             /** Explores the vertex w if it is connected to v */
    
40.             if (isConnected(grown[t], w)) {
    
41.                 if(!explored[w])
    
42.                 {
    
43.                                         /** adds the vertex w to the queue */
    
44.                         Q.insert(w, _A[grown[t]-1][w-1]);
    
45.                         /** marks the vertex w as visited */
    
46.                         explored[w] = _A[grown[t]-1][w-1];
    
47.                 }
    
48.                                 else
    
49.                                 {
    
50.                                         if(Q.contains(w) && _A[grown[t]-1][w-1] < explored[w])
    
51.                                         {
    
52.                                                 Q.change(w, _A[grown[t]-1][w-1]);
    
53.                                                 explored[w] = _A[grown[t]-1][w-1];
    
54.                                         }
    
55.                                 }
    
56.             }
    
57.         t++;
    
58.     }
    
59.     std::cout << std::endl;
    
60.     delete [] explored;
    
61.     delete [] grown;
    
62. }

复制代码

优先队列
PQ.h

1. #if !defined (PQ_H)
   
2. #define PQ_H
   
3. 
   
4. class PriorityQueue{
   
5. private:
   
6.         int  _N = 0;
   
7.         int  *_pq;
   
8.         int  *_index;
   
9.         int  *_prior;
   
10. public:
    
11.         PriorityQueue(int capacity);
    
12.         ~PriorityQueue();
    
13.         bool  isEmpty() const { return _N == 0; }
    
14.         bool  contains(int k) const { return _index[k] != -1; }
    
15.         void  insert(int k, int priority);
    
16.         void  change(int i, int priority);
    
17.         int   pop();
    
18. private:
    
19.         void swim(int k);
    
20.         void sink(int k);
    
21.         bool comp(int i, int j) { return _prior[_pq[i]] > _prior[_pq[j]]; }
    
22.         void swap(int i, int j)
    
23.         {
    
24.                 int ex = _pq[i];
    
25.                 _pq[i] = _pq[j];
    
26.                 _pq[j] = ex;
    
27.                 _index[_pq[i]] = i;
    
28.                 _index[_pq[j]] = j;
    
29.         }
    
30. };
    
31. 
    
32. PriorityQueue::PriorityQueue(int capacity)
    
33. {
    
34.         _prior = new int[capacity+1];
    
35.         _pq    = new int[capacity+1];
    
36.         _index = new int[capacity+1];
    
37.         for (int i = 0; i <= capacity; ++i) _index[i] = -1;
    
38. }
    
39. 
    
40. PriorityQueue::~PriorityQueue(void)
    
41. {
    
42.         delete [] _pq;
    
43.         delete [] _index;
    
44.         delete [] _prior;
    
45. }
    
46. 
    
47. void PriorityQueue::swim(int k)
    
48. {
    
49.         while (k > 1 && comp(k/2, k))
    
50.         {
    
51.                 swap(k, k/2);
    
52.                 k = k/2;
    
53.         }
    
54. }
    
55. 
    
56. void PriorityQueue::insert(int k, int priority)
    
57. {
    
58.         _N++;
    
59.         _index[k] = _N;
    
60.         _pq[_N]   = k;
    
61.         _prior[k] = priority;
    
62.         swim(_N);
    
63. }
    
64. 
    
65. void PriorityQueue::change(int i, int priority)
    
66. {
    
67.         _prior[i] = priority;
    
68.         swim(_index[i]);
    
69.         sink(_index[i]);
    
70. }
    
71. 
    
72. void PriorityQueue::sink(int k)
    
73. {
    
74.         while (2*k <= _N)
    
75.         {
    
76.                 int j = 2*k;
    
77.                 if (j < _N && comp(j, j+1)) j++;
    
78.                 if (!comp(k, j)) break;
    
79.                 swap(k, j);
    
80.                 k = j;
    
81.         }
    
82. }
    
83. 
    
84. int PriorityQueue::pop()
    
85. {
    
86.         int min = _pq[1];
    
87.         swap(1, _N--);
    
88.         sink(1);
    
89.         _prior[_pq[_N+1]] = 0;
    
90.         _index[_pq[_N+1]] = -1;
    
91.         return min;
    
92. }
    
93. 
    
94. #endif

复制代码

andalousie

一个更新版本
主测试文件：
MST.cpp
图的头文件和实现文件
graph.h graph.cc
Prim算法的补充文件
PQ.h //用堆实现一个含索引的最小优先队列
Kruskal算法的补充文件
DisjointSet.h DisjointSet.cc //用于实现并查集，文件不变。
GPQ.h //用于实现泛型最小优先队列。
Dijkstra最短路径算法
PQ.h //和Prim算法一样
stack.h, stack.cc //实现栈结构。文件参考我另一篇文章的代码
下面就是需要列出的文件
graph.h

1. #if !defined (GRAPH_H)
   
2. #define GRAPH_H
   
3. 
   
4. /************************************************************
   
5. 
   
6. Class Graph represents a Graph [V,E] having vertices V and
   
7. edges E.
   
8. 
   
9. ************************************************************/
   
10. class Graph {
    
11.     private:
    
12.         int    _n;  /// n is the number of vertices in the graph
    
13.         int ** _A;  /// A stores the edges between two vertices
    
14.     public:
    
15.         Graph(int size = 2);
    
16.         ~Graph();
    
17.         bool isConnected(int, int);
    
18.         void addEdge(int x, int y, int d);
    
19.         void Prim(int s);
    
20.         void Kruskal(int s);
    
21.         void Dijkstra(int s, int q);
    
22. };
    
23. 
    
24. struct Edge{
    
25.         Edge() {};
    
26.         Edge(int u, int v, int d)
    
27.         : fval(u), val(v), weight(d)
    
28.         {}
    
29.         int fval;
    
30.         int val;
    
31.         int weight;
    
32. };
    
33. 
    
34. #endif

复制代码

graph.cc

1. #include <iostream>
   
2. #include "graph.h"
   
3. #include "PQ.h"
   
4. #include "GPQ.h"
   
5. #include "DisjointSet.h"
   
6. #include "stack.h"
   
7. 
   
8. Graph::Graph(int size) {
   
9.     int i, j;
   
10.     if (size < 2) _n = 2;
    
11.     else _n = size;
    
12.     _A = new int*[_n];
    
13.     for (i = 0; i < _n; ++i)
    
14.         _A[i] = new int[_n];
    
15.     for (i = 0; i < _n; ++i)
    
16.         for (j = 0; j < _n; ++j)
    
17.             _A[i][j] = 0;
    
18. }
    
19. 
    
20. Graph::~Graph() {
    
21.     for (int i = 0; i < _n; ++i)
    
22.     delete [] _A[i];
    
23.     delete [] _A;
    
24. }
    
25. 
    
26. /******************************************************
    
27. Checks if two given vertices are connected by an edge
    
28. @param u vertex
    
29. @param v vertex
    
30. @return true if connected false if not connected
    
31. ******************************************************/
    
32. bool Graph::isConnected(int x, int y) {
    
33.     return (_A[x-1][y-1] != 0);
    
34. }
    
35. 
    
36. /*****************************************************
    
37. adds an edge E to the graph G.
    
38. @param u vertex
    
39. @param v vertex
    
40. *****************************************************/
    
41. void Graph::addEdge(int x, int y, int d) {
    
42.     _A[x-1][y-1] = d; _A[y-1][x-1] = d;
    
43. }
    
44. 
    
45. /*****************************************************
    
46. performs Prim's algorithm
    
47. @param s initial vertex
    
48. *****************************************************/
    
49. void Graph::Prim(int s) {
    
50.     PriorityQueue Q(24);
    
51. 
    
52.     /** Keeps track of explored vertices */
    
53.     int  *explored = new int [_n+1];
    
54.     int  *grown    = new int [_n+1];
    
55.     int  *prev     = new int [_n+1];
    
56. 
    
57.     /** Initailized all vertices */
    
58.     for (int i = 1; i <= _n; ++i)
    
59.     {
    
60.         grown[i] = 0;
    
61.                 if(isConnected(s, i))
    
62.                 {
    
63.                   Q.insert(i, _A[s-1][i-1]);
    
64.                   explored[i] = _A[s-1][i-1];
    
65.                   prev    [i] = s;
    
66.                 }
    
67.                 else
    
68.                 {
    
69.                   explored[i] = 0;
    
70.                   prev    [i] = 0;
    
71.                 }
    
72.     }
    
73.    
    
74.     grown   [1] = s;
    
75.     explored[s] = 1;
    
76. 
    
77.     int t = 2;
    
78.         /** Unless the queue is empty */
    
79.     while (!Q.isEmpty()) {
    
80.         
    
81.         /** Pop the vertex from the queue */
    
82.         grown[t] = Q.pop();
    
83. 
    
84.                 /** display the explored vertices */
    
85.         std::cout << prev[grown[t]] << "-" << grown[t] << " ";
    
86. 
    
87.         /** From the explored vertex v try to explore all the
    
88.         connected vertices */
    
89.         for (int w = 1; w <= _n; ++w)
    
90. 
    
91.             /** Explores the vertex w if it is connected to v */
    
92.             if (isConnected(grown[t], w)) {
    
93.                 if(!explored[w])
    
94.                 {
    
95.                                         /** adds the vertex w to the queue */
    
96.                         Q.insert(w, _A[grown[t]-1][w-1]);
    
97.                         /** marks the vertex w as visited */
    
98.                         explored[w] = _A[grown[t]-1][w-1];
    
99.                         prev    [w] = grown[t];
    
100.                 }
     
101.                                 else
     
102.                                 {
     
103.                                         if(Q.contains(w) && _A[grown[t]-1][w-1] < explored[w])
     
104.                                         {
     
105.                                                 Q.change(w, _A[grown[t]-1][w-1]);
     
106.                                                 explored[w] = _A[grown[t]-1][w-1];
     
107.                                                 prev    [w] = grown[t];
     
108.                                         }
     
109.                                 }
     
110.             }
     
111.         t++;
     
112.     }
     
113.     std::cout << std::endl;
     
114.     delete [] explored;
     
115.     delete [] grown;
     
116.     delete [] prev;
     
117. }
     
118. 
     
119. /*****************************************************
     
120. performs Kruskal's algorithm
     
121. @param s initial vertex
     
122. *****************************************************/
     
123. void Graph::Kruskal(int s) {
     
124.         GenericPQ<Edge> Q(16);
     
125.         DisjointSet UF(_n);
     
126.         for (int i=1; i<_n; ++i)
     
127.         {
     
128.                 for(int j=i+1; j<_n; ++j)
     
129.                 if(isConnected(i, j))
     
130.                 {
     
131.                   Edge e(i, j, _A[i-1][j-1]);
     
132.                   Q.insert(e);
     
133.                 }
     
134.         }
     
135.         
     
136.         while (!Q.isEmpty() && UF.Count() != 1) {
     
137.                 Edge e = Q.pop();
     
138.                 int  v = e.fval;
     
139.                 int  w = e.val;
     
140.                 if(UF.Find(v, w)) continue;
     
141.                 UF.Unite(v, w);
     
142.                 std::cout << v << "-" << w << " ";
     
143.         }
     
144.         std::cout << std::endl;
     
145. }
     
146. 
     
147. /*****************************************************
     
148. performs Dijkstra's algorithm
     
149. @param s initial vertex
     
150. *****************************************************/
     
151. void Graph::Dijkstra(int s, int q) {
     
152.     PriorityQueue Q(16);
     
153.     IStack stack;
     
154. 
     
155.     /** Keeps track of explored vertices */
     
156.     int  *explored = new int [_n+1];
     
157.     int  *grown    = new int [_n+1];
     
158.     int  *prev     = new int [_n+1];
     
159. 
     
160.     /** Initailized all vertices */
     
161.     for (int i = 1; i <= _n; ++i)
     
162.     {
     
163.         grown[i] = 0;
     
164.                 if(isConnected(s, i))
     
165.                 {
     
166.                   Q.insert(i, _A[s-1][i-1]);
     
167.                   explored[i] = _A[s-1][i-1];
     
168.                   prev    [i] = s;
     
169.                 }
     
170.                 else
     
171.                 {
     
172.                   explored[i] = 0;
     
173.                   prev    [i] = 0;
     
174.                 }
     
175.     }
     
176.    
     
177.     grown   [1] = s;
     
178.     explored[s] = 1;
     
179. 
     
180.     int t = 2;
     
181.         /** Unless the queue is empty */
     
182.     while (!Q.isEmpty()) {
     
183.         
     
184.         /** Pop the vertex from the queue */
     
185.         grown[t] = Q.pop();
     
186. 
     
187.         /** From the explored vertex v try to explore all the
     
188.         connected vertices */
     
189.         for (int w = 1; w <= _n; ++w)
     
190. 
     
191.             /** Explores the vertex w if it is connected to v */
     
192.             if (isConnected(grown[t], w)) {
     
193.                 if(!explored[w])
     
194.                 {
     
195.                                         /** adds the vertex w to the queue */
     
196.                         Q.insert(w, explored[t] + _A[grown[t]-1][w-1]);
     
197.                         /** marks the vertex w as visited */
     
198.                         explored[w] = explored[t] + _A[grown[t]-1][w-1];
     
199.                         prev    [w] = grown[t];
     
200.                 }
     
201.                                 else
     
202.                                 {
     
203.                                         if(Q.contains(w) && explored[t] + _A[grown[t]-1][w-1] < explored[w])
     
204.                                         {
     
205.                                                 Q.change(w, explored[t] + _A[grown[t]-1][w-1]);
     
206.                                                 explored[w] = explored[t] + _A[grown[t]-1][w-1];
     
207.                                                 prev    [w] = grown[t];
     
208.                                         }
     
209.                                 }
     
210.             }
     
211.         t++;
     
212.     }
     
213.    
     
214.     t = q;
     
215.     while(prev[t])
     
216.     {
     
217.             stack.push(t);
     
218.                 t = prev[t];
     
219.     }
     
220.    
     
221.     std::cout << s;
     
222.     while(!stack.isEmpty())
     
223.     {
     
224.             std::cout << "-" << stack.pop();
     
225.     }
     
226.     std::cout << std::endl;
     
227.    
     
228.     delete [] explored;
     
229.     delete [] grown;
     
230.     delete [] prev;
     
231. }

复制代码

PQ.h

1. #if !defined (PQ_H)
   
2. #define PQ_H
   
3. 
   
4. class PriorityQueue{
   
5. private:
   
6.         int  _N = 0;
   
7.         int  *_pq;
   
8.         int  *_index;
   
9.         int  *_prior;
   
10. public:
    
11.         PriorityQueue(int capacity);
    
12.         ~PriorityQueue();
    
13.         bool  isEmpty() const { return _N == 0; }
    
14.         bool  contains(int k) const { return _index[k] != -1; }
    
15.         void  insert(int k, int priority);
    
16.         void  change(int i, int priority);
    
17.         int   pop();
    
18. private:
    
19.         void swim(int k);
    
20.         void sink(int k);
    
21.         bool comp(int i, int j) { return _prior[_pq[i]] > _prior[_pq[j]]; }
    
22.         void swap(int i, int j)
    
23.         {
    
24.                 int ex = _pq[i];
    
25.                 _pq[i] = _pq[j];
    
26.                 _pq[j] = ex;
    
27.                 _index[_pq[i]] = i;
    
28.                 _index[_pq[j]] = j;
    
29.         }
    
30. };
    
31. 
    
32. PriorityQueue::PriorityQueue(int capacity)
    
33. {
    
34.         _prior = new int[capacity+1];
    
35.         _pq    = new int[capacity+1];
    
36.         _index = new int[capacity+1];
    
37.         for (int i = 0; i <= capacity; ++i) _index[i] = -1;
    
38. }
    
39. 
    
40. PriorityQueue::~PriorityQueue(void)
    
41. {
    
42.         delete [] _pq;
    
43.         delete [] _index;
    
44.         delete [] _prior;
    
45. }
    
46. 
    
47. void PriorityQueue::swim(int k)
    
48. {
    
49.         while (k > 1 && comp(k/2, k))
    
50.         {
    
51.                 swap(k, k/2);
    
52.                 k = k/2;
    
53.         }
    
54. }
    
55. 
    
56. void PriorityQueue::insert(int k, int priority)
    
57. {
    
58.         _N++;
    
59.         _index[k] = _N;
    
60.         _pq[_N]   = k;
    
61.         _prior[k] = priority;
    
62.         swim(_N);
    
63. }
    
64. 
    
65. void PriorityQueue::change(int i, int priority)
    
66. {
    
67.         _prior[i] = priority;
    
68.         swim(_index[i]);
    
69.         sink(_index[i]);
    
70. }
    
71. 
    
72. void PriorityQueue::sink(int k)
    
73. {
    
74.         while (2*k <= _N)
    
75.         {
    
76.                 int j = 2*k;
    
77.                 if (j < _N && comp(j, j+1)) j++;
    
78.                 if (!comp(k, j)) break;
    
79.                 swap(k, j);
    
80.                 k = j;
    
81.         }
    
82. }
    
83. 
    
84. int PriorityQueue::pop()
    
85. {
    
86.         int min = _pq[1];
    
87.         swap(1, _N--);
    
88.         sink(1);
    
89.         _prior[_pq[_N+1]] = 0;
    
90.         _index[_pq[_N+1]] = -1;
    
91.         return min;
    
92. }
    
93. 
    
94. #endif

复制代码

GPQ.h

1. #if !defined (GPQ_H)
   
2. #define GPQ_H
   
3. 
   
4. struct Edge nulledge;
   
5. 
   
6. template<class T>
   
7. class GenericPQ{
   
8. private:
   
9.         T    *_pq;               // heap-ordered complete binary tree
   
10.         int  _N = 0;             // in pq[1..N] with pq[0] unused
    
11. public:
    
12.         GenericPQ(int capacity);
    
13.         ~GenericPQ();
    
14.         bool isEmpty() { return _N == 0; }
    
15.         void insert(T x);
    
16.         T    pop();
    
17. private:
    
18.         void swim(int k);
    
19.         void sink(int k);
    
20.         //Compare and exchange methods for heap implementations
    
21.         bool comp(int i, int j) { return _pq[i].weight > _pq[j].weight; }
    
22.         void swap(int i, int j)
    
23.         {
    
24.                 T ex   = _pq[i];
    
25.                 _pq[i] = _pq[j];
    
26.                 _pq[j] = ex;
    
27.         }
    
28. };
    
29. 
    
30. template<class T>
    
31. GenericPQ<T>::GenericPQ(int capacity)
    
32. {
    
33.         _pq = new T[capacity+1];
    
34. }
    
35. 
    
36. template<class T>
    
37. GenericPQ<T>::~GenericPQ(void)
    
38. {
    
39.         delete [] _pq;
    
40. }
    
41. 
    
42. /** Bottom-up reheapify (swim) implementation */
    
43. template<class T>
    
44. void GenericPQ<T>::swim(int k)
    
45. {
    
46.         while (k > 1 && comp(k/2, k))
    
47.         {
    
48.                 swap(k, k/2);
    
49.                 k = k/2;
    
50.         }
    
51. }
    
52. 
    
53. template<class T>
    
54. void GenericPQ<T>::insert(T x)
    
55. {
    
56.         _pq[++_N] = x;
    
57.         swim(_N);
    
58. }
    
59. 
    
60. /** Top-down reheapify (sink) implementation **/
    
61. template<class T>
    
62. void GenericPQ<T>::sink(int k)
    
63. {
    
64.         while (2*k <= _N)
    
65.         {
    
66.                 int j = 2*k;
    
67.                 if (j < _N && comp(j, j+1)) j++;
    
68.                 if (!comp(k, j)) break;
    
69.                 swap(k, j);
    
70.                 k = j;
    
71.         }
    
72. }
    
73. 
    
74. template<class T>
    
75. T GenericPQ<T>::pop()
    
76. {
    
77.         T min = _pq[1];          // Retrieve max key from top.
    
78.         swap(1, _N--);           // Exchange with last item.
    
79.         sink(1);                 // Avoid loitering.
    
80.         _pq[_N+1] = nulledge;    // Restore heap property.
    
81.         return min;
    
82. }
    
83. 
    
84. #endif

复制代码

MST.h

1. #include <iostream>
   
2. #include "graph.h"
   
3. 
   
4. int main(){
   
5.         /** Creates a graph with 12 vertices */
   
6.     Graph g1(10);
   
7. 
   
8.     /** Adds edges to the graph */
   
9.     g1.addEdge(1, 2, 5); g1.addEdge(1, 3, 7);
   
10.     g1.addEdge(2, 3, 9); g1.addEdge(2, 6, 6);
    
11.     g1.addEdge(2, 5, 15); g1.addEdge(3, 4, 8);
    
12.     g1.addEdge(3, 5, 7); g1.addEdge(4, 5, 5);
    
13.     g1.addEdge(5, 6, 8); g1.addEdge(5, 7, 9);
    
14.     g1.addEdge(6, 7, 11);
    
15. 
    
16.     /** Explores all vertices findable from vertex 1 */
    
17.     g1.Prim(2);
    
18.     g1.Kruskal(2);
    
19.     g1.Dijkstra(1, 6);
    
20. }

复制代码

andalousie

第三个版本
为了在vc6.0上面能够支持，稍做了修改。增加了最大流算法，但没有验证是否正确。
graph.h

1. #if !defined (GRAPH_H)
   
2. #define GRAPH_H
   
3. 
   
4. /************************************************************
   
5. 
   
6. Class Graph represents a Graph [V,E] having vertices V and
   
7. edges E.
   
8. 
   
9. ************************************************************/
   
10. class Graph {
    
11.     private:
    
12.         int    _n;  /// n is the number of vertices in the graph
    
13.         int ** _A;  /// A stores the edges between two vertices
    
14.     public:
    
15.         Graph(int size = 2);
    
16.         ~Graph();
    
17.         bool isConnected(int, int);
    
18.         void addEdge(int x, int y, int d);
    
19.         void Prim(int s);
    
20.         void Kruskal(int s);
    
21.         void Dijkstra(int s, int q);
    
22.                 bool BFS(int **residual, int s, int required, int *parent);
    
23.                 int  Maxflow(int s, int q);
    
24. };
    
25. 
    
26. struct Edge{
    
27.         Edge() {}
    
28.         Edge(int null) {}
    
29.         Edge(int u, int v, int d)
    
30.         : fval(u), val(v), weight(d)
    
31.         {}
    
32.         bool operator > (Edge& other)
    
33.         {
    
34.                 return weight > other.weight;
    
35.         }
    
36.         int fval;
    
37.         int val;
    
38.         int weight;
    
39. };
    
40. 
    
41. #endif

复制代码

queue.h和queue.cpp参见http://bbs.fishc.com/thread-43422-1-1.html
GPQ.h

1. #if !defined (GPQ_H)
   
2. #define GPQ_H
   
3. 
   
4. template<class T>
   
5. class GenericPQ{
   
6. private:
   
7.         T    *_pq;               // heap-ordered complete binary tree
   
8.         T    _null;
   
9.         int  _N;             // in pq[1..N] with pq[0] unused
   
10. public:
    
11.         GenericPQ(int capacity);
    
12.         ~GenericPQ();
    
13.         bool isEmpty() { return _N == 0; }
    
14.         void insert(T x);
    
15.         T    pop();
    
16. private:
    
17.         void swim(int k);
    
18.         void sink(int k);
    
19.         //Compare and exchange methods for heap implementations
    
20.         bool comp(int i, int j) { return _pq[i] > _pq[j]; }
    
21.         void swap(int i, int j)
    
22.         {
    
23.                 T ex   = _pq[i];
    
24.                 _pq[i] = _pq[j];
    
25.                 _pq[j] = ex;
    
26.         }
    
27. };
    
28. 
    
29. template<class T>
    
30. GenericPQ<T>::GenericPQ(int capacity)
    
31. :_N(0), _null(0)
    
32. {
    
33.         _pq = new T[capacity+1];
    
34. }
    
35. 
    
36. template<class T>
    
37. GenericPQ<T>::~GenericPQ(void)
    
38. {
    
39.         delete [] _pq;
    
40. }
    
41. 
    
42. /** Bottom-up reheapify (swim) implementation */
    
43. template<class T>
    
44. void GenericPQ<T>::swim(int k)
    
45. {
    
46.         while (k > 1 && comp(k/2, k))
    
47.         {
    
48.                 swap(k, k/2);
    
49.                 k = k/2;
    
50.         }
    
51. }
    
52. 
    
53. template<class T>
    
54. void GenericPQ<T>::insert(T x)
    
55. {
    
56.         _pq[++_N] = x;
    
57.         swim(_N);
    
58. }
    
59. 
    
60. /** Top-down reheapify (sink) implementation **/
    
61. template<class T>
    
62. void GenericPQ<T>::sink(int k)
    
63. {
    
64.         while (2*k <= _N)
    
65.         {
    
66.                 int j = 2*k;
    
67.                 if (j < _N && comp(j, j+1)) j++;
    
68.                 if (!comp(k, j)) break;
    
69.                 swap(k, j);
    
70.                 k = j;
    
71.         }
    
72. }
    
73. 
    
74. template<class T>
    
75. T GenericPQ<T>::pop()
    
76. {
    
77.         T min = _pq[1];          // Retrieve max key from top.
    
78.         swap(1, _N--);           // Exchange with last item.
    
79.         sink(1);                 // Avoid loitering.
    
80.         _pq[_N+1] = _null;    // Restore heap property.
    
81.         return min;
    
82. }
    
83. 
    
84. #endif

复制代码

graph.cc

1. #include <iostream>
   
2. #include "graph.h"
   
3. #include "queue.h"
   
4. #include "PQ.h"
   
5. #include "GPQ.h"
   
6. #include "DisjointSet.h"
   
7. #include "stack.h"
   
8. 
   
9. Graph::Graph(int size) {
   
10.     int i, j;
    
11.     if (size < 2) _n = 2;
    
12.     else _n = size;
    
13.     _A = new int*[_n];
    
14.     for (i = 0; i < _n; ++i)
    
15.         _A[i] = new int[_n];
    
16.     for (i = 0; i < _n; ++i)
    
17.         for (j = 0; j < _n; ++j)
    
18.             _A[i][j] = 0;
    
19. }
    
20. 
    
21. Graph::~Graph() {
    
22.     for (int i = 0; i < _n; ++i)
    
23.     delete [] _A[i];
    
24.     delete [] _A;
    
25. }
    
26. 
    
27. /******************************************************
    
28. Checks if two given vertices are connected by an edge
    
29. @param u vertex
    
30. @param v vertex
    
31. @return true if connected false if not connected
    
32. ******************************************************/
    
33. bool Graph::isConnected(int x, int y) {
    
34.     return (_A[x-1][y-1] != 0);
    
35. }
    
36. 
    
37. /*****************************************************
    
38. adds an edge E to the graph G.
    
39. @param u vertex
    
40. @param v vertex
    
41. *****************************************************/
    
42. void Graph::addEdge(int x, int y, int d) {
    
43.     _A[x-1][y-1] = d; _A[y-1][x-1] = d;
    
44. }
    
45. 
    
46. /*****************************************************
    
47. performs Prim's algorithm
    
48. @param s initial vertex
    
49. *****************************************************/
    
50. void Graph::Prim(int s) {
    
51.     PriorityQueue Q(24);
    
52. 
    
53.     /** Keeps track of explored vertices */
    
54.     int  *explored = new int [_n+1];
    
55.     int  *grown    = new int [_n+1];
    
56.     int  *prev     = new int [_n+1];
    
57. 
    
58.     /** Initailized all vertices */
    
59.     for (int i = 1; i <= _n; ++i)
    
60.     {
    
61.         grown[i] = 0;
    
62.                 if(isConnected(s, i))
    
63.                 {
    
64.                   Q.insert(i, _A[s-1][i-1]);
    
65.                   explored[i] = _A[s-1][i-1];
    
66.                   prev    [i] = s;
    
67.                 }
    
68.                 else
    
69.                 {
    
70.                   explored[i] = 0;
    
71.                   prev    [i] = 0;
    
72.                 }
    
73.     }
    
74.    
    
75.     grown   [1] = s;
    
76.     explored[s] = 1;
    
77. 
    
78.     int t = 2;
    
79.         /** Unless the queue is empty */
    
80.     while (!Q.isEmpty()) {
    
81.         
    
82.         /** Pop the vertex from the queue */
    
83.         grown[t] = Q.pop();
    
84. 
    
85.                 /** display the explored vertices */
    
86.         std::cout << prev[grown[t]] << "-" << grown[t] << " ";
    
87. 
    
88.         /** From the explored vertex v try to explore all the
    
89.         connected vertices */
    
90.         for (int w = 1; w <= _n; ++w)
    
91. 
    
92.             /** Explores the vertex w if it is connected to v */
    
93.             if (isConnected(grown[t], w)) {
    
94.                 if(!explored[w])
    
95.                 {
    
96.                                         /** adds the vertex w to the queue */
    
97.                         Q.insert(w, _A[grown[t]-1][w-1]);
    
98.                         /** marks the vertex w as visited */
    
99.                         explored[w] = _A[grown[t]-1][w-1];
    
100.                         prev    [w] = grown[t];
     
101.                 }
     
102.                                 else
     
103.                                 {
     
104.                                         if(Q.contains(w) && _A[grown[t]-1][w-1] < explored[w])
     
105.                                         {
     
106.                                                 Q.change(w, _A[grown[t]-1][w-1]);
     
107.                                                 explored[w] = _A[grown[t]-1][w-1];
     
108.                                                 prev    [w] = grown[t];
     
109.                                         }
     
110.                                 }
     
111.             }
     
112.         t++;
     
113.     }
     
114.     std::cout << std::endl;
     
115.     delete [] explored;
     
116.     delete [] grown;
     
117.     delete [] prev;
     
118. }
     
119. 
     
120. /*****************************************************
     
121. performs Kruskal's algorithm
     
122. @param s initial vertex
     
123. *****************************************************/
     
124. void Graph::Kruskal(int s) {
     
125.         GenericPQ<Edge> Q(16);
     
126.         DisjointSet UF(_n);
     
127.         for (int i=1; i<_n; ++i)
     
128.         {
     
129.                 for(int j=i+1; j<_n; ++j)
     
130.                 if(isConnected(i, j))
     
131.                 {
     
132.                   Edge e(i, j, _A[i-1][j-1]);
     
133.                   Q.insert(e);
     
134.                 }
     
135.         }
     
136.        
     
137.         while (!Q.isEmpty() && UF.Count() != 1) {
     
138.                 Edge e = Q.pop();
     
139.                 int  v = e.fval;
     
140.                 int  w = e.val;
     
141.                 if(UF.Find(v, w)) continue;
     
142.                 UF.Unite(v, w);
     
143.                 std::cout << v << "-" << w << " ";
     
144.         }
     
145.         std::cout << std::endl;
     
146. }
     
147. 
     
148. /*****************************************************
     
149. performs Dijkstra's algorithm
     
150. @param s initial vertex
     
151. *****************************************************/
     
152. void Graph::Dijkstra(int s, int q) {
     
153.     PriorityQueue Q(16);
     
154.     IStack stack;
     
155. 
     
156.     /** Keeps track of explored vertices */
     
157.     int  *explored = new int [_n+1];
     
158.     int  *grown    = new int [_n+1];
     
159.     int  *prev     = new int [_n+1];
     
160. 
     
161.     /** Initailized all vertices */
     
162.     for (int i = 1; i <= _n; ++i)
     
163.     {
     
164.         grown[i] = 0;
     
165.                 if(isConnected(s, i))
     
166.                 {
     
167.                   Q.insert(i, _A[s-1][i-1]);
     
168.                   explored[i] = _A[s-1][i-1];
     
169.                   prev    [i] = s;
     
170.                 }
     
171.                 else
     
172.                 {
     
173.                   explored[i] = 0;
     
174.                   prev    [i] = 0;
     
175.                 }
     
176.     }
     
177.    
     
178.     grown   [1] = s;
     
179.     explored[s] = 1;
     
180. 
     
181.     int t = 2;
     
182.         /** Unless the queue is empty */
     
183.     while (!Q.isEmpty()) {
     
184.         
     
185.         /** Pop the vertex from the queue */
     
186.         grown[t] = Q.pop();
     
187. 
     
188.         /** From the explored vertex v try to explore all the
     
189.         connected vertices */
     
190.         for (int w = 1; w <= _n; ++w)
     
191. 
     
192.             /** Explores the vertex w if it is connected to v */
     
193.             if (isConnected(grown[t], w)) {
     
194.                 if(!explored[w])
     
195.                 {
     
196.                                         /** adds the vertex w to the queue */
     
197.                         Q.insert(w, explored[t] + _A[grown[t]-1][w-1]);
     
198.                         /** marks the vertex w as visited */
     
199.                         explored[w] = explored[t] + _A[grown[t]-1][w-1];
     
200.                         prev    [w] = grown[t];
     
201.                 }
     
202.                                 else
     
203.                                 {
     
204.                                         if(Q.contains(w) && explored[t] + _A[grown[t]-1][w-1] < explored[w])
     
205.                                         {
     
206.                                                 Q.change(w, explored[t] + _A[grown[t]-1][w-1]);
     
207.                                                 explored[w] = explored[t] + _A[grown[t]-1][w-1];
     
208.                                                 prev    [w] = grown[t];
     
209.                                         }
     
210.                                 }
     
211.             }
     
212.         t++;
     
213.     }
     
214.    
     
215.     t = q;
     
216.     while(prev[t])
     
217.     {
     
218.             stack.push(t);
     
219.                 t = prev[t];
     
220.     }
     
221.    
     
222.     std::cout << s;
     
223.     while(!stack.isEmpty())
     
224.     {
     
225.             std::cout << "-" << stack.pop();
     
226.     }
     
227.     std::cout << std::endl;
     
228.    
     
229.     delete [] explored;
     
230.     delete [] grown;
     
231.     delete [] prev;
     
232. }
     
233. 
     
234. /*****************************************************
     
235. performs Breadth First Search
     
236. @param s initial vertex
     
237. *****************************************************/
     
238. bool Graph::BFS(int **residual, int s, int required, int *parent) {
     
239.     Queue Q;
     
240. 
     
241.     /** Keeps track of explored vertices */
     
242.     bool *explored = new bool[_n+1];
     
243. 
     
244.     /** Initailized all vertices as unexplored */
     
245.     for (int i = 1; i <= _n; ++i)
     
246.         explored[i] = false;
     
247. 
     
248.     /** Push initial vertex to the queue */
     
249.     Q.enqueue(s);
     
250.     explored[s] = true; /** mark it as explored */
     
251.         parent[s] = -1;
     
252. 
     
253.     /** Unless the queue is empty */
     
254.     while (!Q.isEmpty()) {
     
255.         /** Pop the vertex from the queue */
     
256.         int v = Q.dequeue();
     
257. 
     
258.         if(v == required)
     
259.                 {
     
260.                         delete [] explored;
     
261.                         return true;
     
262.                 }
     
263. 
     
264.         /** From the explored vertex v try to explore all the
     
265.         connected vertices */
     
266.         for (int w = 1; w <= _n; ++w)
     
267. 
     
268.             /** Explores the vertex w if it is connected to v
     
269.             and and if it is unexplored */
     
270.             if (residual[v-1][w-1] && !explored[w]) {
     
271.                 /** adds the vertex w to the queue */
     
272.                 Q.enqueue(w);
     
273.                                 parent[w] = v;
     
274.                 /** marks the vertex w as visited */
     
275.                 explored[w] = true;
     
276.             }
     
277.     }
     
278.     delete [] explored;
     
279.         return false;
     
280. }
     
281. 
     
282. /*****************************************************
     
283. performs Edmonds–Karp algorithm
     
284. @param s initial vertex
     
285. *****************************************************/
     
286. int Graph::Maxflow(int s, int q)
     
287. {
     
288.     // Create a residual graph and fill the residual graph with
     
289.     // given capacities in the original graph as residual capacities
     
290.     // in residual graph
     
291.     int **residual = new int*[_n];
     
292.     for (int i = 0; i < _n; ++i)
     
293.         residual[i] = new int[_n];
     
294.                      // Residual graph where residual[i][j] indicates
     
295.                      // residual capacity of edge from i to j (if there
     
296.                      // is an edge. If residual[i][j] is 0, then there is not)  
     
297.     for (int u = 0; u < _n; u++)
     
298.         for (int w = 0; w < _n; w++)
     
299.              residual[u][w] = _A[u][w];
     
300. 
     
301.     int *parent = new int [_n+1];  // This queue is filled by BFS and to store path
     
302. 
     
303.     int max_flow = 0;  // There is no flow initially
     
304. 
     
305.     // Augment the flow while tere is path from source to sink
     
306.         int v = 0;
     
307.     while (BFS(residual, s, q, parent))
     
308.     {
     
309.         // Find minimum residual capacity of the edhes along the
     
310.         // path filled by BFS. Or we can say find the maximum flow
     
311.         // through the path found.
     
312.                 GenericPQ<int> cf(25);
     
313.         for (v = q; v != s; v = parent[v])
     
314.         {
     
315.             u = parent[v];
     
316.             cf.insert(residual[u-1][v-1]);
     
317.         }
     
318.                 int path_flow = cf.pop();
     
319. 
     
320.         // update residual capacities of the edges and reverse edges
     
321.         // along the path
     
322.         for (v = q; v != s; v = parent[v])
     
323.         {
     
324.             u = parent[v];
     
325.             residual[u-1][v-1] -= path_flow;
     
326.             residual[v-1][u-1] += path_flow;
     
327.         }
     
328. 
     
329.         // Add path flow to overall flow
     
330.         max_flow += path_flow;
     
331.     }
     
332. 
     
333.         for (int j = 0; j < _n; ++j)
     
334.     delete [] residual[j];
     
335.         delete [] residual;
     
336.         delete [] parent;
     
337.     // Return the overall flow
     
338.     return max_flow;
     
339. }

复制代码

qidaoshen

看一看 看一看

じO-联合

看看。。。。。。。了解

无耐的小码

感谢楼主分享，不错学习学习！

猪不是这样爱

看看学习一下 ........