我正在尝试实现Prim的算法。我从一个文件中获取输入，如下所示。
3 3 // Number of vertices and edges
1 2 3 // edge 1 edge 2 cost
2 3 4 // edge 2 edge 3 cost
1 3 4 // edge 1 edge 3 cost
我创建成本矩阵如下。最初，成本矩阵中的每个权重都是无穷大（在这种情况下为9999）。
for(i = 0; i < n; i++)
{
for( j = 0; j < n; j++)
{
cost[i][j] = 9999;
}
}
现在，我需要通过从文件中读取权重来更新成本矩阵的权重。因此，我正在读取文件，如下所示。
ifstream fin;
fin.open("input.txt",ios::in);
fin >> n; //nodes
fin >> e; //edges
while(fin)
{
fin>>a>>b>>w;
cost[a-1][b-1] =cost[b-1][a-1]= w;
}
fin.close();
因此，a和b是边缘，w是该边缘的权重。因此，假设我有边缘（1,2），其重量为3。所以，我的成本矩阵cost[1][2]，并cost[2][1]应更新为3。我无法弄清楚，我应该如何使用文件操作更新成本矩阵。
再说一次，我有一个文本文件，就像我上面提到的文件一样。文件的第一行包含边缘中的顶点数。我想读取变量v中的顶点和变量e中的边。然后，我有了一个初始成本矩阵cost[i][i]，其中所有值都是无穷大。我想从文件更新此成本矩阵中的边。因此，我将从文件中读取第二行并更新cost[1][2]=3。我仍然不知道该怎么做。
这是我现在拥有的完整程序：
#include<iostream>
#include<fstream>
using namespace std;
int n,e,a,b,w;
int **cost = new int*[n];
void prim()
{
int i,j,k,l,x,nr[10],temp,min_cost=0;
int **tree = new int*[n];
for(i = 0; i < n; i++)
tree[i]=new int[n];
/* For first smallest edge */
temp=cost[0][0];
for(i=0;i< n;i++)
{
for(j=0;j< n;j++)
{
if(temp>cost[i][j])
{
temp=cost[i][j];
k=i;
l=j;
}
}
}
/* Now we have fist smallest edge in graph */
tree[0][0]=k;
tree[0][1]=l;
tree[0][2]=temp;
min_cost=temp;
/* Now we have to find min dis of each
vertex from either k or l
by initialising nr[] array
*/
for(i=0;i< n;i++)
{
if(cost[i][k]< cost[i][l])
nr[i]=k;
else
nr[i]=l;
}
/* To indicate visited vertex initialise nr[] for them to 100 */
nr[k]=100;
nr[l]=100;
/* Now find out remaining n-2 edges */
temp=99;
for(i=1;i< n-1;i++)
{
for(j=0;j< n;j++)
{
if(nr[j]!=100 && cost[j][nr[j]] < temp)
{
temp=cost[j][nr[j]];
x=j;
}
}
/* Now i have got next vertex */
tree[i][0]=x;
tree[i][1]=nr[x];
tree[i][2]=cost[x][nr[x]];
min_cost=min_cost+cost[x][nr[x]];
nr[x]=100;
/* Now find if x is nearest to any vertex
than its previous near value */
for(j=0;j< n;j++)
{
if(nr[j]!=100 && cost[j][nr[j]] > cost[j][x])
nr[j]=x;
}
temp=9999;
}
/* Now i have the answer, just going to print it */
cout<<"\n The minimum spanning tree is:"<<endl;
for(i=0;i< n-1;i++)
{
for(j=0;j< 3;j++)
cout<<tree[i][j];
cout<<endl;
}
cout<<"\nMinimum cost:";
cout<<min_cost;
}
int main()
{
int i,j;
for(i = 0; i < n; i++)
cost[i]=new int[n];
for(i = 0; i < n; i++)
{
for( j = 0; j < n; j++)
{
cost[i][j] = 9999;
}
}
ifstream fin;
fin.open("input.txt",ios::in);
//cout<<n<<e;
fin>>n>>e;
while(fin>>a>>b>>w)
{
cost[a-1][b-1] = w;
}
fin.close();
prim();
system("pause");
}
后来添加到OP中的读取代码的改编：
#include<vector>
typedef int Cost;
typedef std::vector<std::vector<Cost> > Matrix;
typedef Matrix::value_type Row;
不变prim以cost引用方式取矩阵：
void prim(Matrix const& cost)
阅读成为：
int main()
{
ifstream fin;
fin.open("input.txt", ios::in);
unsigned n, e;
if (fin >> n >> e)
{
Matrix cost(n, Row(n, 9999));
unsigned a, b;
Cost w;
while(fin >> a >> b >> w)
{
cost[a - 1][b - 1] = w;
}
prim(cost);
}
fin.close();
}
你看，
假设数据结构为：
typedef unsigned Vertex;
typedef std::pair<Vertex, Vertex> Edge;
typedef double Cost;
typedef std::map<Edge, Cost> Graph;
typedef Graph::value_type Entry;
这是readGraph仅使用标准库工具的非常干净的版本：
Graph readGraph(std::istream& is)
{
size_t vertices, edges;
if (is >> vertices >> edges)
{
is.ignore(1024, '\n'); // assume not overly long lines
Graph graph;
while (edges--)
{
std::string line;
if (is && std::getline(is, line))
{
Vertex from, to;
Cost cost;
std::istringstream line_stream(line);
if (line_stream >> from >> to >> cost)
{
if (!(graph.insert({ { from, to }, cost }).second))
throw std::runtime_error("Duplicate edge");
} else
{
is.setstate(is.rdstate() | std::ios::badbit);
}
}
}
if (!is.bad())
return graph;
}
throw std::runtime_error("Invalid input");
}
看到它住在Coliru
Graph const graph = readGraph(std::cin);
for (auto& entry: graph)
{
Edge const& edge = ::get_edge(entry);
Cost cost = ::get_cost(entry);
std::cout << "Edge(" << get_source(edge) << ", " << get_destination(edge) << "): cost " << cost << "\n";
}
输出：
Edge(1, 2): cost 3
Edge(1, 3): cost 4
Edge(2, 3): cost 4
使用Boost Spirit进行解析。这是一个即用型替换和数据结构，并且main()完全不变：
Graph readGraph(std::istream& is)
{
typedef boost::spirit::istream_iterator It;
is.unsetf(std::ios::skipws);
It f(is), l;
size_t vertices = 0, edges = 0;
Graph graph;
using namespace boost::spirit::qi;
static const rule<It, Edge(), blank_type> edge_rule = uint_ >> uint_;
bool ok = phrase_parse(f, l,
uint_ >> uint_ >> eol >>
(edge_rule >> double_) % eol >> (*eol > eoi),
blank,
vertices, edges, graph);
assert(ok && f==l && graph.size() == edges);
return graph;
}
也可以在Coliru上观看。
（以防Coliru不复存在）：
#include <iostream>
#include <fstream>
#include <iterator>
#include <algorithm>
#include <sstream>
#include <map>
#include <cassert>
#include <stdexcept>
typedef unsigned Vertex;
typedef std::pair<Vertex, Vertex> Edge;
typedef double Cost;
typedef std::map<Edge, Cost> Graph;
typedef Graph::value_type Entry;
Graph readGraph(std::istream& is)
{
size_t vertices, edges;
if (is >> vertices >> edges)
{
is.ignore(1024, '\n'); // assume not overly long lines
Graph graph;
while (edges--)
{
std::string line;
if (is && std::getline(is, line))
{
Vertex from, to;
Cost cost;
std::istringstream line_stream(line);
if (line_stream >> from >> to >> cost)
{
if (!(graph.insert({ { from, to }, cost }).second))
throw std::runtime_error("Duplicate edge");
} else
{
is.setstate(is.rdstate() | std::ios::badbit);
}
}
}
if (!is.bad())
return graph;
}
throw std::runtime_error("Invalid input");
}
static inline Vertex get_source (Edge const& e) { return e.first; }
static inline Vertex get_destination(Edge const& e) { return e.second; }
static inline Edge const& get_edge (Entry const& e) { return e.first; }
static inline double get_cost (Entry const& e) { return e.second; }
static inline Vertex& get_source (Edge & e) { return e.first; }
static inline Vertex& get_destination(Edge & e) { return e.second; }
static inline double& get_cost (Entry & e) { return e.second; }
int main()
{
Graph const graph = readGraph(std::cin);
for (auto& entry: graph)
{
Edge const& edge = ::get_edge(entry);
Cost cost = ::get_cost(entry);
std::cout << "Edge(" << get_source(edge) << ", " << get_destination(edge) << "): cost " << cost << "\n";
}
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句