1 无向加权图的数据格式如下
4 5 0.35
4 7 0.37
5 7 0.28
0 7 0.16
1 5 0.32
0 4 0.38
2 3 0.17
1 7 0.19
0 2 0.26
1 2 0.36
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93
2 实现的C++代码如下，包括无向加权边，无向图和Prim算法
Graph.h头文件内容
/*
* Graph.h
*
* Created on: 2014年5月17日
* Author: zhongchao
*/
#ifndef _GRAPH_
#define _GRAPH_
#include <fstream>
#include <iostream>
#include <ext/hash_map>
#include <hash_set>
#include <map>
#include<limits>
#include <stdio.h>
#include <string.h>
using namespace std;
using namespace __gnu_cxx;
//-------------------------最小生成树算法------------------
class WeightEdge
{
private:
int _a; //起点
int _b; //终点
double _weight; //权重
public:
WeightEdge();
WeightEdge(int a, int b, double c);
~WeightEdge();
int one();
int other(int a);
double weight();
};
class WeightGraph
{
private:
hash_map<int, vector<WeightEdge*> > adj; //邻接表
hash_set<int> nodes;
int _eNum; //边的个数
int _vNum; //节点个数
public:
WeightGraph(string path);
~WeightGraph();
void addEdge(int f, int t, double w);
vector<WeightEdge*> getAdj(int n);
int e();
int v();
vector<WeightEdge*> edges(int node);
hash_set<int> getNodes();
};
class Prim
{
private:
bool* mark;
double* distTo;
WeightEdge** edgeTo;
map<double, int> pq;
hash_set<int> pqMark;
WeightGraph* _graph;
int startNode;
public:
Prim(WeightGraph* graph, int n);
void visit(WeightGraph* graph, int n);
vector<WeightEdge*> edges();
double weight();
void printEdges(vector<WeightEdge*> & edges);
};
//----------------------------------------------------------------------
#endif /* _GRAPH_*/
Graph.h对应的源文件
/*
* Graph.cpp
*
* Created on: 2014年5月17日
* Author: zhongchao
*/
#include "Graph.h"
/*
* 无向加权图算法
*/
//-------------------------无向加权边------------------------------
WeightEdge::WeightEdge()
{
}
WeightEdge::WeightEdge(int a, int b, double c)
{
this->_a = a;
this->_b = b;
this->_weight = c;
}
WeightEdge::~WeightEdge()
{}
int WeightEdge::one()
{
return _a;
}
int WeightEdge::other(int a)
{
if(_a == a)
return _b;
else
return _a;
}
double WeightEdge::weight()
{
return _weight;
}
//----------------------------------------------------------------------
//----------------------无向加权图-----------------------------
hash_set<int> WeightGraph::getNodes()
{
return nodes;
}
void WeightGraph::addEdge(int f, int t, double w)
{
WeightEdge* weightEdge = new WeightEdge(f, t, w);
if(adj.find(f) != adj.end())
{
adj.find(f)->second.push_back(weightEdge);
}
else
{
vector<WeightEdge*> edges;
edges.push_back(weightEdge);
adj.insert(pair<int, vector<WeightEdge*> >(f, edges));
}
}
WeightGraph::WeightGraph(string path)
{
this->_eNum = 0;
this->_vNum = 0;
ifstream reader(path.c_str(), ios_base::in);
if(reader.is_open())
{
while(!reader.eof())
{
int f, t;
double w;
reader>>f>>t>>w;
if(reader.fail())
break;
//cout<<f<<" "<<t<<" "<<w<<endl;
nodes.insert(f);
nodes.insert(t);
addEdge(f, t, w);
addEdge(t, f, w);
_eNum++; //边的条数
}
}
}
int WeightGraph::e()
{
return _eNum;
}
int WeightGraph::v()
{
return nodes.size();
}
vector<WeightEdge*> WeightGraph::getAdj(int n)
{
return adj.find(n)->second;
}
WeightGraph::~WeightGraph()
{
for(hash_map<int, vector<WeightEdge*> >::iterator it = adj.begin(); it != adj.end(); it++)
{
for(vector<WeightEdge*>::iterator it1 = it->second.begin(); it1 != it->second.end(); it1++)
{
delete *it1;
}
}
}
//---------------------------------------------------------------------
//-------------------------Prim算法---------------身不由己-------------
Prim::Prim(WeightGraph* graph, int n)
{
startNode = n;
_graph = graph;
mark = new bool[graph->v()];
distTo = new double[graph->v()];
edgeTo = new WeightEdge*[graph->v()];
int tt= graph->v();
for(int i = 0; i < graph->v(); i++)
{
mark[i] = false;
distTo[i] = numeric_limits<double>::max();
}
mark[n] = true;
distTo[n] = 0.0;
pq.insert(pair<double, int>(0.0, n));
pqMark.insert(n);
while(pq.size() > 0)
{
int v = pq.begin()->second;
pq.erase(pq.begin());
visit(graph, v);
}
}
void Prim::visit(WeightGraph* graph, int n)
{
mark[n] = true;
vector<WeightEdge*> edges = graph->getAdj(n);
for(vector<WeightEdge*>::iterator it = edges.begin(); it != edges.end(); it++)
{
int o = (*it)->other(n);
double w = (*it)->weight();
if(mark[o] == true) continue;
if(w < distTo[o])
{
edgeTo[o] = *it;
distTo[o] = w;
if(pqMark.find(o) == pqMark.end())
{
pq.insert(pair<double, int>(w, o));
pqMark.insert(o);
}
else
{
for(map<double, int>::iterator it = pq.begin(); it != pq.end(); it++)
{
if((it)->second == o)
{
pq.erase(it);
pq.insert(pair<double, int>(w, o));
break;
}
}
}
}
}
}
vector<WeightEdge*> Prim::edges()
{
vector<WeightEdge*> es;
for(int i = 0; i < _graph->v(); i++)
{
if(i == startNode) continue;
es.push_back(edgeTo[i]);
}
return es;
}
double Prim::weight()
{
double w = 0.0;
for(int i = 0; i < _graph->v(); i++)
{
if(i == startNode) continue;
w += distTo[i];
}
return w;
}
void Prim::printEdges(vector<WeightEdge*> & edges)
{
cout<<"The MST as follows:"<<endl;
for(vector<WeightEdge*>::iterator it = edges.begin(); it != edges.end(); it++)
{
cout<<(*it)->one()<<" "<<(*it)->other((*it)->one())<<" "<<(*it)->weight()<<endl;
}
cout<<"Total weight is: "<<weight()<<endl;
}
//--------------------------------------------------------------------
测试程序
/*
* Run.cpp
*
* Created on: 2014年5月25日
* Author: zhongchao
*/
#include "Graph.h"
int main(int argc, char** argv)
{
//最小生成树算法
string path("/home/zhongchao/worksapce/cpp/ComputeAlgorithms/data/tinyEWG.txt");
WeightGraph* weightGraph = new WeightGraph(path);
int n = 2;
Prim* prim = new Prim(weightGraph, n);
vector<WeightEdge*> es = prim->edges();
prim->printEdges(es);
return 1;
}
以节点2为起点的最小生成树如下
The MST as follows:
2 0 0.26
7 1 0.19
2 3 0.17
5 4 0.35
7 5 0.28
2 6 0.4
0 7 0.16
Total weight is: 1.81
2 0 0.26
7 1 0.19
2 3 0.17
5 4 0.35
7 5 0.28
2 6 0.4
0 7 0.16
Total weight is: 1.81