1

我正在尝试实现 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");
  }
4

1 回答 1

3

更新

稍后添加到 OP 的读取代码的改编：

#include<vector>

typedef int Cost;
typedef std::vector<std::vector<Cost> > Matrix;
typedef Matrix::value_type Row;

不更改prim以cost通过 ref 获取矩阵：

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";
    }
}
于 2013-10-18T18:36:07.327 回答