最小生成树算法，最短路径算法，网络流算法
本帖最后由 andalousie 于 2014-3-16 08:38 编辑大家万事如意，大家心想事成。这里给出最小生成树的两种算法的C++版本。这里来列一下清单
主测试文件：
MST.cpp
图的头文件和实现文件
graph.h graph.cc
Prim算法的补充文件
List.h list.cc //用于实现一个简易的双向循环链优先队列
Kruskal算法的补充文件
DisjointSet.h DisjointSet.cc //用于实现并查集
MST.cpp#include <iostream>
#include "graph.h"
int main(){
/** Creates a graph with 12 vertices */
Graph g1(10);
/** Adds edges to the graph */
g1.addEdge(1, 2, 5); g1.addEdge(1, 3, 7);
g1.addEdge(2, 3, 9); g1.addEdge(2, 6, 6);
g1.addEdge(2, 5, 15); g1.addEdge(3, 4, 8);
g1.addEdge(3, 5, 7); g1.addEdge(4, 5, 5);
g1.addEdge(5, 6, 8); g1.addEdge(5, 7, 9);
g1.addEdge(6, 7, 11);
/** Explores all vertices findable from vertex 1 */
g1.Prim(2);
g1.Kruskal(2);
}graph.h#if !defined (GRAPH_H)
#define GRAPH_H
/************************************************************
Class Graph represents a Graph having vertices V and
edges E.
************************************************************/
class Graph {
private:
int _n;/// n is the number of vertices in the graph
int ** _A;/// A stores the edges between two vertices
public:
Graph(int size = 2);
~Graph();
bool isConnected(int, int);
void addEdge(int x, int y, int d);
void Prim(int s);
void Kruskal(int s);
};
#endifgraph.cc#include <iostream>
#include "graph.h"
#include "List.h"
#include "DisjointSet.h"
Graph::Graph(int size) {
int i, j;
if (size < 2) _n = 2;
else _n = size;
_A = new int*;
for (i = 0; i < _n; ++i)
_A = new int;
for (i = 0; i < _n; ++i)
for (j = 0; j < _n; ++j)
_A = 0;
}
Graph::~Graph() {
for (int i = 0; i < _n; ++i)
delete [] _A;
delete [] _A;
}
/******************************************************
Checks if two given vertices are connected by an edge
@param u vertex
@param v vertex
@return true if connected false if not connected
******************************************************/
bool Graph::isConnected(int x, int y) {
return (_A != 0);
}
/*****************************************************
adds an edge E to the graph G.
@param u vertex
@param v vertex
*****************************************************/
void Graph::addEdge(int x, int y, int d) {
_A = d; _A = d;
}
/*****************************************************
performs Prim's algorithm
@param s initial vertex
*****************************************************/
void Graph::Prim(int s) {
Queue Q;
/** Keeps track of explored vertices */
int*explored = new int ;
int*grown = new int ;
bool *done = new bool;
/** Initailized all vertices */
for (int i = 1; i <= _n; ++i)
{
grown = 0;
done = false;
if(isConnected(s, i))
{
prior D1(s, i, _A);
Q.Put(D1);
explored = _A;
}
else
explored = 0;
}
grown = s;
explored = 1;
done = true;
int t = 2;
/** Unless the queue is empty */
while (!Q.isEmpty()) {
prior e = Q.Get();
/** Pop the vertex from the queue */
grown = e.val;
/** display the explored vertices */
std::cout << e.fval << "-" << e.val << " ";
done] = true;
/** From the explored vertex v try to explore all the
connected vertices */
for (int w = 1; w <= _n; ++w)
/** Explores the vertex w if it is connected to v */
if (isConnected(grown, w)) {
if(!explored)
{
prior D2(grown, w, _A-1]);
/** adds the vertex w to the queue */
Q.Put(D2);
/** marks the vertex w as visited */
explored = _A-1];
}
else
{
if(!done && _A-1] < explored)
{
prior D3(grown, w, _A-1]);
Q.Push(D3);
explored = _A-1];
}
}
}
t++;
}
std::cout << std::endl;
delete [] explored;
delete [] grown;
delete [] done;
}
void Graph::Kruskal(int s) {
Queue Q;
DisjointSet UF(_n);
for (int i=1; i<_n; ++i)
{
for(int j=i+1; j<_n; ++j)
if(isConnected(i, j))
{
prior D1(i, j, _A);
Q.Put(D1);
}
}
while (!Q.isEmpty() && UF.Count() != 1) {
prior e = Q.Get();
int v = e.fval; int w = e.val;
if(UF.Find(v, w)) continue;
UF.Unite(v, w);
std::cout << v << "-" << w << " ";
}
}List.h#if !defined (LIST_H)
#define LIST_H
class prior{
public:
prior(int u, int v, int p)
:fval(u), val(v), priority(p)
{}
int fval;
int val;
const intpriority;
};
class DLink
{
public:
DLink (prior id)
: _id (id)
{
_pPrev = this;
_pNext = this;
}
DLink *Prev () const { return _pPrev; }
DLink *Next () const { return _pNext; }
void SetPrev (DLink* pPrev) { _pPrev = pPrev; }
void SetNext (DLink* pNext) { _pNext = pNext; }
prior Id () const { return _id; }
void Unlink();
private:
DLink *_pPrev;
DLink *_pNext;
prior _id;
};
class Queue
{
public:
Queue (): _pHead (0) {}
~Queue ();
void Put ( prior id );
void Push ( prior id );
prior Get ();
bool isEmpty () { return _pHead == 0; }
DLink * GetHead () const { return _pHead; }
protected:
DLink*_pHead;
};
#endiflist.cc#include "list.h"
#include <iostream>
#include <cassert>
void DLink::Unlink()
{
assert (_pNext != 0);
assert (_pPrev != 0);
_pNext->SetPrev (_pPrev);
_pPrev->SetNext (_pNext);
_pPrev = this;
_pNext = this;
}
void Queue::Put (prior id)
{
DLink * pLink = new DLink (id);
if (_pHead == 0)
_pHead = pLink;
else if(_pHead->Next () == _pHead)
{
pLink->SetNext (_pHead);
pLink->SetPrev (_pHead->Prev ());
_pHead->SetNext (pLink);
_pHead->SetPrev (pLink);
if(id.priority >= _pHead->Id().priority)
_pHead = pLink;
}
else
{
DLink * tLink;
for (tLink = GetHead();
id.priority < tLink->Id().priority;
tLink = tLink->Next ())
{
if(tLink == _pHead->Prev())
{
if(id.priority < tLink->Id().priority)
{
pLink->SetNext (_pHead);
pLink->SetPrev (_pHead->Prev ());
_pHead->Prev ()->SetNext (pLink);
_pHead->SetPrev (pLink);
return;
}
break;
}
}
pLink->SetNext (tLink);
pLink->SetPrev (tLink->Prev ());
pLink->Prev ()->SetNext (pLink);
pLink->Next ()->SetPrev (pLink);
if(tLink == _pHead)
_pHead = pLink;
}
}
void Queue::Push (prior id)
{
DLink * nLink = new DLink (id);
if (_pHead == 0)
_pHead = nLink;
else if(_pHead->Next () == _pHead)
{
if(id.val == _pHead->Id().val)
{
_pHead = nLink;
return;
}
else
Put(id);
}
else
{
bool flag = false;
for (DLink * fLink = GetHead();;
fLink = fLink->Next ())
{
if(fLink == _pHead->Prev())
{
if(id.val == fLink->Id().val)
{
fLink->Unlink();
flag = true;
}
flag = true;
}
if(id.val == fLink->Id().val)
{
if(fLink == _pHead)
_pHead = _pHead->Next();
fLink->Unlink();
flag = true;
}
if(flag) break;
}
Put(id);
}
}
prior Queue::Get ()
{
assert (_pHead != 0);
DLink * pLink = _pHead->Prev ();
if (pLink == _pHead) // last one
_pHead = 0;
pLink->Unlink ();
prior result = pLink->Id ();
delete pLink;
return result;
}
Queue::~Queue ()
{
// free the Queue
while ( _pHead != 0 )
{
DLink * pLink = _pHead->Prev ();
if (pLink == _pHead)
_pHead = 0;
pLink->Unlink (); // unlink pLink
delete pLink;
}
}DisjointSet.h#if !defined (DISJOINTSET_H)
#define DISJOINTSET_H
class DisjointSet
{
private:
int *_id; // parent link (site indexed)
int *_sz; // size of component for roots (site indexed)
int _count; // number of components
int _root(int i);
public:
DisjointSet(int N);
int Count() { return _count; }
bool Find(int p,int q);
void Unite(int p,int q);
~DisjointSet(void);
};
#endifDisjointSet.cc#include "DisjointSet.h"
DisjointSet::DisjointSet(int N)
: _count(N)
{
_id = new int;
_sz = new int;
for(int i=0; i<N; ++i)
{
_id = i;
_sz = 1;
}
}
int DisjointSet::_root(int i)
{
while (i != _id)
{
_id = _id]; //Path compression.
i = _id;
}
return i;
}
bool DisjointSet::Find(int p, int q)
{
return _root(p) == _root(q);
}
void DisjointSet::Unite(int p, int q)
{
//Link root of smaller tree to root of larger tree.
int i = _root(p);
int j = _root(q);
if(_sz < _sz)
{
_id = j; _sz += _sz;
}
else
{
_id = i; _sz += _sz;
}
_count--;
}
DisjointSet::~DisjointSet(void)
{
delete [] _id;
delete [] _sz;
}结果输出2-1 2-6 1-3 3-5 5-4 5-7
1-2 4-5 2-6 1-3 3-5 5-7第二个更新版本见4楼。改良了代码，还增加了Dijkstra最短路径算法。第三个更新版本见5楼，修改了代码以适应vc6.0，增加了网络流算法，修改了GenericPQ中null和Comp的实现。
更新了算法，补充了Kruskal算法。{:5_95:} 来看看吧 本帖最后由 andalousie 于 2014-2-18 16:49 编辑
其实大家应该发现我的山寨优先队列把复杂度直接拖到O(n^2)了吧。。。
可以看看这个，虽然只把顶点的遍历顺序输出出来了，但是这回的优先队列可是O(logn)的，这个代码段用了新的优先队列。void Graph::Prim(int s) {
PriorityQueue Q(24);
/** Keeps track of explored vertices */
int*explored = new int ;
int*grown = new int ;
/** Initailized all vertices */
for (int i = 1; i <= _n; ++i)
{
grown = 0;
if(isConnected(s, i))
{
Q.insert(i, _A);
explored = _A;
}
else
explored = 0;
}
grown = s;
explored = 1;
std::cout << grown << " ";
int t = 2;
/** Unless the queue is empty */
while (!Q.isEmpty()) {
/** Pop the vertex from the queue */
grown = Q.pop();
/** display the explored vertices */
std::cout << grown << " ";
/** From the explored vertex v try to explore all the
connected vertices */
for (int w = 1; w <= _n; ++w)
/** Explores the vertex w if it is connected to v */
if (isConnected(grown, w)) {
if(!explored)
{
/** adds the vertex w to the queue */
Q.insert(w, _A-1]);
/** marks the vertex w as visited */
explored = _A-1];
}
else
{
if(Q.contains(w) && _A-1] < explored)
{
Q.change(w, _A-1]);
explored = _A-1];
}
}
}
t++;
}
std::cout << std::endl;
delete [] explored;
delete [] grown;
}优先队列
PQ.h
#if !defined (PQ_H)
#define PQ_H
class PriorityQueue{
private:
int_N = 0;
int*_pq;
int*_index;
int*_prior;
public:
PriorityQueue(int capacity);
~PriorityQueue();
boolisEmpty() const { return _N == 0; }
boolcontains(int k) const { return _index != -1; }
voidinsert(int k, int priority);
voidchange(int i, int priority);
int pop();
private:
void swim(int k);
void sink(int k);
bool comp(int i, int j) { return _prior] > _prior]; }
void swap(int i, int j)
{
int ex = _pq;
_pq = _pq;
_pq = ex;
_index] = i;
_index] = j;
}
};
PriorityQueue::PriorityQueue(int capacity)
{
_prior = new int;
_pq = new int;
_index = new int;
for (int i = 0; i <= capacity; ++i) _index = -1;
}
PriorityQueue::~PriorityQueue(void)
{
delete [] _pq;
delete [] _index;
delete [] _prior;
}
void PriorityQueue::swim(int k)
{
while (k > 1 && comp(k/2, k))
{
swap(k, k/2);
k = k/2;
}
}
void PriorityQueue::insert(int k, int priority)
{
_N++;
_index = _N;
_pq = k;
_prior = priority;
swim(_N);
}
void PriorityQueue::change(int i, int priority)
{
_prior = priority;
swim(_index);
sink(_index);
}
void PriorityQueue::sink(int k)
{
while (2*k <= _N)
{
int j = 2*k;
if (j < _N && comp(j, j+1)) j++;
if (!comp(k, j)) break;
swap(k, j);
k = j;
}
}
int PriorityQueue::pop()
{
int min = _pq;
swap(1, _N--);
sink(1);
_prior] = 0;
_index] = -1;
return min;
}
#endif
本帖最后由 andalousie 于 2014-2-19 11:53 编辑
一个更新版本
主测试文件：
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#if !defined (GRAPH_H)
#define GRAPH_H
/************************************************************
Class Graph represents a Graph having vertices V and
edges E.
************************************************************/
class Graph {
private:
int _n;/// n is the number of vertices in the graph
int ** _A;/// A stores the edges between two vertices
public:
Graph(int size = 2);
~Graph();
bool isConnected(int, int);
void addEdge(int x, int y, int d);
void Prim(int s);
void Kruskal(int s);
void Dijkstra(int s, int q);
};
struct Edge{
Edge() {};
Edge(int u, int v, int d)
: fval(u), val(v), weight(d)
{}
int fval;
int val;
int weight;
};
#endifgraph.cc#include <iostream>
#include "graph.h"
#include "PQ.h"
#include "GPQ.h"
#include "DisjointSet.h"
#include "stack.h"
Graph::Graph(int size) {
int i, j;
if (size < 2) _n = 2;
else _n = size;
_A = new int*;
for (i = 0; i < _n; ++i)
_A = new int;
for (i = 0; i < _n; ++i)
for (j = 0; j < _n; ++j)
_A = 0;
}
Graph::~Graph() {
for (int i = 0; i < _n; ++i)
delete [] _A;
delete [] _A;
}
/******************************************************
Checks if two given vertices are connected by an edge
@param u vertex
@param v vertex
@return true if connected false if not connected
******************************************************/
bool Graph::isConnected(int x, int y) {
return (_A != 0);
}
/*****************************************************
adds an edge E to the graph G.
@param u vertex
@param v vertex
*****************************************************/
void Graph::addEdge(int x, int y, int d) {
_A = d; _A = d;
}
/*****************************************************
performs Prim's algorithm
@param s initial vertex
*****************************************************/
void Graph::Prim(int s) {
PriorityQueue Q(24);
/** Keeps track of explored vertices */
int*explored = new int ;
int*grown = new int ;
int*prev = new int ;
/** Initailized all vertices */
for (int i = 1; i <= _n; ++i)
{
grown = 0;
if(isConnected(s, i))
{
Q.insert(i, _A);
explored = _A;
prev = s;
}
else
{
explored = 0;
prev = 0;
}
}
grown = s;
explored = 1;
int t = 2;
/** Unless the queue is empty */
while (!Q.isEmpty()) {
/** Pop the vertex from the queue */
grown = Q.pop();
/** display the explored vertices */
std::cout << prev] << "-" << grown << " ";
/** From the explored vertex v try to explore all the
connected vertices */
for (int w = 1; w <= _n; ++w)
/** Explores the vertex w if it is connected to v */
if (isConnected(grown, w)) {
if(!explored)
{
/** adds the vertex w to the queue */
Q.insert(w, _A-1]);
/** marks the vertex w as visited */
explored = _A-1];
prev = grown;
}
else
{
if(Q.contains(w) && _A-1] < explored)
{
Q.change(w, _A-1]);
explored = _A-1];
prev = grown;
}
}
}
t++;
}
std::cout << std::endl;
delete [] explored;
delete [] grown;
delete [] prev;
}
/*****************************************************
performs Kruskal's algorithm
@param s initial vertex
*****************************************************/
void Graph::Kruskal(int s) {
GenericPQ<Edge> Q(16);
DisjointSet UF(_n);
for (int i=1; i<_n; ++i)
{
for(int j=i+1; j<_n; ++j)
if(isConnected(i, j))
{
Edge e(i, j, _A);
Q.insert(e);
}
}
while (!Q.isEmpty() && UF.Count() != 1) {
Edge e = Q.pop();
intv = e.fval;
intw = e.val;
if(UF.Find(v, w)) continue;
UF.Unite(v, w);
std::cout << v << "-" << w << " ";
}
std::cout << std::endl;
}
/*****************************************************
performs Dijkstra's algorithm
@param s initial vertex
*****************************************************/
void Graph::Dijkstra(int s, int q) {
PriorityQueue Q(16);
IStack stack;
/** Keeps track of explored vertices */
int*explored = new int ;
int*grown = new int ;
int*prev = new int ;
/** Initailized all vertices */
for (int i = 1; i <= _n; ++i)
{
grown = 0;
if(isConnected(s, i))
{
Q.insert(i, _A);
explored = _A;
prev = s;
}
else
{
explored = 0;
prev = 0;
}
}
grown = s;
explored = 1;
int t = 2;
/** Unless the queue is empty */
while (!Q.isEmpty()) {
/** Pop the vertex from the queue */
grown = Q.pop();
/** From the explored vertex v try to explore all the
connected vertices */
for (int w = 1; w <= _n; ++w)
/** Explores the vertex w if it is connected to v */
if (isConnected(grown, w)) {
if(!explored)
{
/** adds the vertex w to the queue */
Q.insert(w, explored + _A-1]);
/** marks the vertex w as visited */
explored = explored + _A-1];
prev = grown;
}
else
{
if(Q.contains(w) && explored + _A-1] < explored)
{
Q.change(w, explored + _A-1]);
explored = explored + _A-1];
prev = grown;
}
}
}
t++;
}
t = q;
while(prev)
{
stack.push(t);
t = prev;
}
std::cout << s;
while(!stack.isEmpty())
{
std::cout << "-" << stack.pop();
}
std::cout << std::endl;
delete [] explored;
delete [] grown;
delete [] prev;
}PQ.h#if !defined (PQ_H)
#define PQ_H
class PriorityQueue{
private:
int_N = 0;
int*_pq;
int*_index;
int*_prior;
public:
PriorityQueue(int capacity);
~PriorityQueue();
boolisEmpty() const { return _N == 0; }
boolcontains(int k) const { return _index != -1; }
voidinsert(int k, int priority);
voidchange(int i, int priority);
int pop();
private:
void swim(int k);
void sink(int k);
bool comp(int i, int j) { return _prior] > _prior]; }
void swap(int i, int j)
{
int ex = _pq;
_pq = _pq;
_pq = ex;
_index] = i;
_index] = j;
}
};
PriorityQueue::PriorityQueue(int capacity)
{
_prior = new int;
_pq = new int;
_index = new int;
for (int i = 0; i <= capacity; ++i) _index = -1;
}
PriorityQueue::~PriorityQueue(void)
{
delete [] _pq;
delete [] _index;
delete [] _prior;
}
void PriorityQueue::swim(int k)
{
while (k > 1 && comp(k/2, k))
{
swap(k, k/2);
k = k/2;
}
}
void PriorityQueue::insert(int k, int priority)
{
_N++;
_index = _N;
_pq = k;
_prior = priority;
swim(_N);
}
void PriorityQueue::change(int i, int priority)
{
_prior = priority;
swim(_index);
sink(_index);
}
void PriorityQueue::sink(int k)
{
while (2*k <= _N)
{
int j = 2*k;
if (j < _N && comp(j, j+1)) j++;
if (!comp(k, j)) break;
swap(k, j);
k = j;
}
}
int PriorityQueue::pop()
{
int min = _pq;
swap(1, _N--);
sink(1);
_prior] = 0;
_index] = -1;
return min;
}
#endifGPQ.h#if !defined (GPQ_H)
#define GPQ_H
struct Edge nulledge;
template<class T>
class GenericPQ{
private:
T *_pq; // heap-ordered complete binary tree
int_N = 0; // in pq with pq unused
public:
GenericPQ(int capacity);
~GenericPQ();
bool isEmpty() { return _N == 0; }
void insert(T x);
T pop();
private:
void swim(int k);
void sink(int k);
//Compare and exchange methods for heap implementations
bool comp(int i, int j) { return _pq.weight > _pq.weight; }
void swap(int i, int j)
{
T ex = _pq;
_pq = _pq;
_pq = ex;
}
};
template<class T>
GenericPQ<T>::GenericPQ(int capacity)
{
_pq = new T;
}
template<class T>
GenericPQ<T>::~GenericPQ(void)
{
delete [] _pq;
}
/** Bottom-up reheapify (swim) implementation */
template<class T>
void GenericPQ<T>::swim(int k)
{
while (k > 1 && comp(k/2, k))
{
swap(k, k/2);
k = k/2;
}
}
template<class T>
void GenericPQ<T>::insert(T x)
{
_pq[++_N] = x;
swim(_N);
}
/** Top-down reheapify (sink) implementation **/
template<class T>
void GenericPQ<T>::sink(int k)
{
while (2*k <= _N)
{
int j = 2*k;
if (j < _N && comp(j, j+1)) j++;
if (!comp(k, j)) break;
swap(k, j);
k = j;
}
}
template<class T>
T GenericPQ<T>::pop()
{
T min = _pq; // Retrieve max key from top.
swap(1, _N--); // Exchange with last item.
sink(1); // Avoid loitering.
_pq = nulledge; // Restore heap property.
return min;
}
#endifMST.h#include <iostream>
#include "graph.h"
int main(){
/** Creates a graph with 12 vertices */
Graph g1(10);
/** Adds edges to the graph */
g1.addEdge(1, 2, 5); g1.addEdge(1, 3, 7);
g1.addEdge(2, 3, 9); g1.addEdge(2, 6, 6);
g1.addEdge(2, 5, 15); g1.addEdge(3, 4, 8);
g1.addEdge(3, 5, 7); g1.addEdge(4, 5, 5);
g1.addEdge(5, 6, 8); g1.addEdge(5, 7, 9);
g1.addEdge(6, 7, 11);
/** Explores all vertices findable from vertex 1 */
g1.Prim(2);
g1.Kruskal(2);
g1.Dijkstra(1, 6);
} 第三个版本
为了在vc6.0上面能够支持，稍做了修改。增加了最大流算法，但没有验证是否正确。
graph.h#if !defined (GRAPH_H)
#define GRAPH_H
/************************************************************
Class Graph represents a Graph having vertices V and
edges E.
************************************************************/
class Graph {
private:
int _n;/// n is the number of vertices in the graph
int ** _A;/// A stores the edges between two vertices
public:
Graph(int size = 2);
~Graph();
bool isConnected(int, int);
void addEdge(int x, int y, int d);
void Prim(int s);
void Kruskal(int s);
void Dijkstra(int s, int q);
bool BFS(int **residual, int s, int required, int *parent);
intMaxflow(int s, int q);
};
struct Edge{
Edge() {}
Edge(int null) {}
Edge(int u, int v, int d)
: fval(u), val(v), weight(d)
{}
bool operator > (Edge& other)
{
return weight > other.weight;
}
int fval;
int val;
int weight;
};
#endifqueue.h和queue.cpp参见http://bbs.fishc.com/thread-43422-1-1.html
GPQ.h#if !defined (GPQ_H)
#define GPQ_H
template<class T>
class GenericPQ{
private:
T *_pq; // heap-ordered complete binary tree
T _null;
int_N; // in pq with pq unused
public:
GenericPQ(int capacity);
~GenericPQ();
bool isEmpty() { return _N == 0; }
void insert(T x);
T pop();
private:
void swim(int k);
void sink(int k);
//Compare and exchange methods for heap implementations
bool comp(int i, int j) { return _pq > _pq; }
void swap(int i, int j)
{
T ex = _pq;
_pq = _pq;
_pq = ex;
}
};
template<class T>
GenericPQ<T>::GenericPQ(int capacity)
:_N(0), _null(0)
{
_pq = new T;
}
template<class T>
GenericPQ<T>::~GenericPQ(void)
{
delete [] _pq;
}
/** Bottom-up reheapify (swim) implementation */
template<class T>
void GenericPQ<T>::swim(int k)
{
while (k > 1 && comp(k/2, k))
{
swap(k, k/2);
k = k/2;
}
}
template<class T>
void GenericPQ<T>::insert(T x)
{
_pq[++_N] = x;
swim(_N);
}
/** Top-down reheapify (sink) implementation **/
template<class T>
void GenericPQ<T>::sink(int k)
{
while (2*k <= _N)
{
int j = 2*k;
if (j < _N && comp(j, j+1)) j++;
if (!comp(k, j)) break;
swap(k, j);
k = j;
}
}
template<class T>
T GenericPQ<T>::pop()
{
T min = _pq; // Retrieve max key from top.
swap(1, _N--); // Exchange with last item.
sink(1); // Avoid loitering.
_pq = _null; // Restore heap property.
return min;
}
#endifgraph.cc#include <iostream>
#include "graph.h"
#include "queue.h"
#include "PQ.h"
#include "GPQ.h"
#include "DisjointSet.h"
#include "stack.h"
Graph::Graph(int size) {
int i, j;
if (size < 2) _n = 2;
else _n = size;
_A = new int*;
for (i = 0; i < _n; ++i)
_A = new int;
for (i = 0; i < _n; ++i)
for (j = 0; j < _n; ++j)
_A = 0;
}
Graph::~Graph() {
for (int i = 0; i < _n; ++i)
delete [] _A;
delete [] _A;
}
/******************************************************
Checks if two given vertices are connected by an edge
@param u vertex
@param v vertex
@return true if connected false if not connected
******************************************************/
bool Graph::isConnected(int x, int y) {
return (_A != 0);
}
/*****************************************************
adds an edge E to the graph G.
@param u vertex
@param v vertex
*****************************************************/
void Graph::addEdge(int x, int y, int d) {
_A = d; _A = d;
}
/*****************************************************
performs Prim's algorithm
@param s initial vertex
*****************************************************/
void Graph::Prim(int s) {
PriorityQueue Q(24);
/** Keeps track of explored vertices */
int*explored = new int ;
int*grown = new int ;
int*prev = new int ;
/** Initailized all vertices */
for (int i = 1; i <= _n; ++i)
{
grown = 0;
if(isConnected(s, i))
{
Q.insert(i, _A);
explored = _A;
prev = s;
}
else
{
explored = 0;
prev = 0;
}
}
grown = s;
explored = 1;
int t = 2;
/** Unless the queue is empty */
while (!Q.isEmpty()) {
/** Pop the vertex from the queue */
grown = Q.pop();
/** display the explored vertices */
std::cout << prev] << "-" << grown << " ";
/** From the explored vertex v try to explore all the
connected vertices */
for (int w = 1; w <= _n; ++w)
/** Explores the vertex w if it is connected to v */
if (isConnected(grown, w)) {
if(!explored)
{
/** adds the vertex w to the queue */
Q.insert(w, _A-1]);
/** marks the vertex w as visited */
explored = _A-1];
prev = grown;
}
else
{
if(Q.contains(w) && _A-1] < explored)
{
Q.change(w, _A-1]);
explored = _A-1];
prev = grown;
}
}
}
t++;
}
std::cout << std::endl;
delete [] explored;
delete [] grown;
delete [] prev;
}
/*****************************************************
performs Kruskal's algorithm
@param s initial vertex
*****************************************************/
void Graph::Kruskal(int s) {
GenericPQ<Edge> Q(16);
DisjointSet UF(_n);
for (int i=1; i<_n; ++i)
{
for(int j=i+1; j<_n; ++j)
if(isConnected(i, j))
{
Edge e(i, j, _A);
Q.insert(e);
}
}
while (!Q.isEmpty() && UF.Count() != 1) {
Edge e = Q.pop();
intv = e.fval;
intw = e.val;
if(UF.Find(v, w)) continue;
UF.Unite(v, w);
std::cout << v << "-" << w << " ";
}
std::cout << std::endl;
}
/*****************************************************
performs Dijkstra's algorithm
@param s initial vertex
*****************************************************/
void Graph::Dijkstra(int s, int q) {
PriorityQueue Q(16);
IStack stack;
/** Keeps track of explored vertices */
int*explored = new int ;
int*grown = new int ;
int*prev = new int ;
/** Initailized all vertices */
for (int i = 1; i <= _n; ++i)
{
grown = 0;
if(isConnected(s, i))
{
Q.insert(i, _A);
explored = _A;
prev = s;
}
else
{
explored = 0;
prev = 0;
}
}
grown = s;
explored = 1;
int t = 2;
/** Unless the queue is empty */
while (!Q.isEmpty()) {
/** Pop the vertex from the queue */
grown = Q.pop();
/** From the explored vertex v try to explore all the
connected vertices */
for (int w = 1; w <= _n; ++w)
/** Explores the vertex w if it is connected to v */
if (isConnected(grown, w)) {
if(!explored)
{
/** adds the vertex w to the queue */
Q.insert(w, explored + _A-1]);
/** marks the vertex w as visited */
explored = explored + _A-1];
prev = grown;
}
else
{
if(Q.contains(w) && explored + _A-1] < explored)
{
Q.change(w, explored + _A-1]);
explored = explored + _A-1];
prev = grown;
}
}
}
t++;
}
t = q;
while(prev)
{
stack.push(t);
t = prev;
}
std::cout << s;
while(!stack.isEmpty())
{
std::cout << "-" << stack.pop();
}
std::cout << std::endl;
delete [] explored;
delete [] grown;
delete [] prev;
}
/*****************************************************
performs Breadth First Search
@param s initial vertex
*****************************************************/
bool Graph::BFS(int **residual, int s, int required, int *parent) {
Queue Q;
/** Keeps track of explored vertices */
bool *explored = new bool;
/** Initailized all vertices as unexplored */
for (int i = 1; i <= _n; ++i)
explored = false;
/** Push initial vertex to the queue */
Q.enqueue(s);
explored = true; /** mark it as explored */
parent = -1;
/** Unless the queue is empty */
while (!Q.isEmpty()) {
/** Pop the vertex from the queue */
int v = Q.dequeue();
if(v == required)
{
delete [] explored;
return true;
}
/** From the explored vertex v try to explore all the
connected vertices */
for (int w = 1; w <= _n; ++w)
/** Explores the vertex w if it is connected to v
and and if it is unexplored */
if (residual && !explored) {
/** adds the vertex w to the queue */
Q.enqueue(w);
parent = v;
/** marks the vertex w as visited */
explored = true;
}
}
delete [] explored;
return false;
}
/*****************************************************
performs Edmonds–Karp algorithm
@param s initial vertex
*****************************************************/
int Graph::Maxflow(int s, int q)
{
// Create a residual graph and fill the residual graph with
// given capacities in the original graph as residual capacities
// in residual graph
int **residual = new int*;
for (int i = 0; i < _n; ++i)
residual = new int;
// Residual graph where residual indicates
// residual capacity of edge from i to j (if there
// is an edge. If residual is 0, then there is not)
for (int u = 0; u < _n; u++)
for (int w = 0; w < _n; w++)
residual = _A;
int *parent = new int ;// This queue is filled by BFS and to store path
int max_flow = 0;// There is no flow initially
// Augment the flow while tere is path from source to sink
int v = 0;
while (BFS(residual, s, q, parent))
{
// Find minimum residual capacity of the edhes along the
// path filled by BFS. Or we can say find the maximum flow
// through the path found.
GenericPQ<int> cf(25);
for (v = q; v != s; v = parent)
{
u = parent;
cf.insert(residual);
}
int path_flow = cf.pop();
// update residual capacities of the edges and reverse edges
// along the path
for (v = q; v != s; v = parent)
{
u = parent;
residual -= path_flow;
residual += path_flow;
}
// Add path flow to overall flow
max_flow += path_flow;
}
for (int j = 0; j < _n; ++j)
delete [] residual;
delete [] residual;
delete [] parent;
// Return the overall flow
return max_flow;
} 看一看 看一看 看看。。。。。。。了解 感谢楼主分享，不错学习学习！ 看看学习一下 ........
页:
[1]