|
|
楼主 |
发表于 2014-2-19 11:51:26
|
显示全部楼层
本帖最后由 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 [V,E] 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;
};
#endif
#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*[_n];
for (i = 0; i < _n; ++i)
_A[i] = new int[_n];
for (i = 0; i < _n; ++i)
for (j = 0; j < _n; ++j)
_A[i][j] = 0;
}
Graph::~Graph() {
for (int i = 0; i < _n; ++i)
delete [] _A[i];
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[x-1][y-1] != 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[x-1][y-1] = d; _A[y-1][x-1] = 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 [_n+1];
int *grown = new int [_n+1];
int *prev = new int [_n+1];
/** Initailized all vertices */
for (int i = 1; i <= _n; ++i)
{
grown[i] = 0;
if(isConnected(s, i))
{
Q.insert(i, _A[s-1][i-1]);
explored[i] = _A[s-1][i-1];
prev [i] = s;
}
else
{
explored[i] = 0;
prev [i] = 0;
}
}
grown [1] = s;
explored[s] = 1;
int t = 2;
/** Unless the queue is empty */
while (!Q.isEmpty()) {
/** Pop the vertex from the queue */
grown[t] = Q.pop();
/** display the explored vertices */
std::cout << prev[grown[t]] << "-" << grown[t] << " ";
/** 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[t], w)) {
if(!explored[w])
{
/** adds the vertex w to the queue */
Q.insert(w, _A[grown[t]-1][w-1]);
/** marks the vertex w as visited */
explored[w] = _A[grown[t]-1][w-1];
prev [w] = grown[t];
}
else
{
if(Q.contains(w) && _A[grown[t]-1][w-1] < explored[w])
{
Q.change(w, _A[grown[t]-1][w-1]);
explored[w] = _A[grown[t]-1][w-1];
prev [w] = grown[t];
}
}
}
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[i-1][j-1]);
Q.insert(e);
}
}
while (!Q.isEmpty() && UF.Count() != 1) {
Edge e = Q.pop();
int v = e.fval;
int w = 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 [_n+1];
int *grown = new int [_n+1];
int *prev = new int [_n+1];
/** Initailized all vertices */
for (int i = 1; i <= _n; ++i)
{
grown[i] = 0;
if(isConnected(s, i))
{
Q.insert(i, _A[s-1][i-1]);
explored[i] = _A[s-1][i-1];
prev [i] = s;
}
else
{
explored[i] = 0;
prev [i] = 0;
}
}
grown [1] = s;
explored[s] = 1;
int t = 2;
/** Unless the queue is empty */
while (!Q.isEmpty()) {
/** Pop the vertex from the queue */
grown[t] = 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[t], w)) {
if(!explored[w])
{
/** adds the vertex w to the queue */
Q.insert(w, explored[t] + _A[grown[t]-1][w-1]);
/** marks the vertex w as visited */
explored[w] = explored[t] + _A[grown[t]-1][w-1];
prev [w] = grown[t];
}
else
{
if(Q.contains(w) && explored[t] + _A[grown[t]-1][w-1] < explored[w])
{
Q.change(w, explored[t] + _A[grown[t]-1][w-1]);
explored[w] = explored[t] + _A[grown[t]-1][w-1];
prev [w] = grown[t];
}
}
}
t++;
}
t = q;
while(prev[t])
{
stack.push(t);
t = prev[t];
}
std::cout << s;
while(!stack.isEmpty())
{
std::cout << "-" << stack.pop();
}
std::cout << std::endl;
delete [] explored;
delete [] grown;
delete [] prev;
}
#if !defined (PQ_H)
#define PQ_H
class PriorityQueue{
private:
int _N = 0;
int *_pq;
int *_index;
int *_prior;
public:
PriorityQueue(int capacity);
~PriorityQueue();
bool isEmpty() const { return _N == 0; }
bool contains(int k) const { return _index[k] != -1; }
void insert(int k, int priority);
void change(int i, int priority);
int pop();
private:
void swim(int k);
void sink(int k);
bool comp(int i, int j) { return _prior[_pq[i]] > _prior[_pq[j]]; }
void swap(int i, int j)
{
int ex = _pq[i];
_pq[i] = _pq[j];
_pq[j] = ex;
_index[_pq[i]] = i;
_index[_pq[j]] = j;
}
};
PriorityQueue::PriorityQueue(int capacity)
{
_prior = new int[capacity+1];
_pq = new int[capacity+1];
_index = new int[capacity+1];
for (int i = 0; i <= capacity; ++i) _index[i] = -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[k] = _N;
_pq[_N] = k;
_prior[k] = priority;
swim(_N);
}
void PriorityQueue::change(int i, int priority)
{
_prior[i] = priority;
swim(_index[i]);
sink(_index[i]);
}
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[1];
swap(1, _N--);
sink(1);
_prior[_pq[_N+1]] = 0;
_index[_pq[_N+1]] = -1;
return min;
}
#endif
#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[1..N] with pq[0] 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[i].weight > _pq[j].weight; }
void swap(int i, int j)
{
T ex = _pq[i];
_pq[i] = _pq[j];
_pq[j] = ex;
}
};
template<class T>
GenericPQ<T>::GenericPQ(int capacity)
{
_pq = new T[capacity+1];
}
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[1]; // Retrieve max key from top.
swap(1, _N--); // Exchange with last item.
sink(1); // Avoid loitering.
_pq[_N+1] = nulledge; // Restore heap property.
return min;
}
#endif
#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);
}
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2014-2-8 22:33:46
置顶卡
千斤顶
显身卡
来看看吧