克鲁斯卡尔算法(排序)

Question

我正在从文件中读取表示并将其存储在邻接表中。然后以"graphviz格式"输出图，并对图执行MST算法。最后，我以"graphviz格式"输出MST。我在c++中做这个。

我的主要问题是算法。我正在实现Kruskals算法，排序函数不起作用。

当我编译它时，我得到这个错误:

实例化自' void std::sort(_RandomAccessIterator， _RandomAccessIterator， _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator*， std::vector, std::allocator>>>， _Compare = bool (*)(Edges, Edges)] '

下面是我的代码:

#include <iostream>
#include <iomanip>
#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
#include <cstdlib>  
#include <utility>   

using namespace std;

#define egdes pair<int ,int >
#define MAX 9
struct Edges
{
    int weight;
    int first,second;
    char begin,end;
};
    bool EdgeLess(Edges oneE,Edges twoE)
     {
        return oneE.weight < twoE.weight;
     }  
vector<pair<int ,Edges > > graph,MST;
int parent[MAX],total ;

bool openInputFile(ifstream &inFile,char* argv);
bool openOutputFile(ofstream &outFile,char* argv);
void readInputFile(ifstream &inFile,vector<Edges> &graph);
int findSet(int x,int *parent);
void kruskals();
void makeSet();
bool compareEdgW(Edges oneE,Edges twoE);
int main (int argc,char **argv)
{
    ifstream inFile;
    ofstream outFile;
    int u,v,w;
     int nodeCount;
    int edgeCount;
    char nodeName;
    Edges edge;
    vector<Edges> graph;
        cout<<"hey"<<endl;
 if(openInputFile(inFile,argv[1]) && openOutputFile(outFile,argv[2]))
    {
        readInputFile(inFile,graph);
        outFile.close();
    }
    inFile >> nodeCount;
    inFile >> edgeCount;
    for( int i = 0;i < edgeCount; i++)
    {
        cin >> u >> v >> w ; 
//        graph.push_back(pair<int ,Edges >(w,edges(u,v)));
        graph.push_back(edge);
    }
    kruskals();
    makeSet();  
    return 0;
}

bool openInputFile(ifstream &inFile,char* argv)
{
    inFile.open("input.txt");
    if(!inFile)
    {
        cout<<"Oops!Input file did not open.n";
        cout<<"Terminating the program.n";
        return false;
    }
    return true;
}
bool openOutputFile(ofstream &outFile,char* argv)
{
    outFile.open("output.gv");
    if(!outFile)
    {
        cout<<"Hey!Oops!Input file did not open.n";
        cout<<"Terminating the program.n";
        return false;
    }
    return true;
}
void readInputFile(ifstream &inFile,vector<Edges> &graph)
{
    int nodeCount;
    Edges edge;
    inFile >>nodeCount;
    char nodeName;
    for (int i = 0;i < nodeCount;i++)
    {
        inFile >> nodeName;
//        graph.insert(make_pair(nodeName,vector<Edges>()));
    }
    int edgeCount;
    inFile >> edgeCount;
    for (int i = 0;i < edgeCount;i++)
    {
  //      inFile >>nodeName;
        Edges edge;
        inFile >> edge.begin;
        inFile >> edge.weight;
        inFile >> edge.end;
        graph.push_back(edge);
    }
}
int findSet(int x,int *parent)
{
    if( x != parent[x])
        parent [x] = findSet(parent[x],parent);
    return parent[x];
}
void kruskals()
{
    int pu;
    int pv;
    int edgeCount;
    sort(graph.begin(),graph.end (),EdgeLess);
    for (int i = 0;i < edgeCount; i++) 
    {
        pu = findSet(graph[i].second.first,parent);
        pv = findSet(graph[i].second.second,parent);
        if(pu != pv)
        {   
            MST.push_back(graph[i]);
            total += graph[i].first;
            parent[pu] = parent[pv];
        }
    }
}
void makeSet()
{
    unsigned long sizeNum;
    sizeNum = MST.size();
    for(int i = 0;i < sizeNum;i++)
    {
        cout<< MST[i].second.first <<endl;
        cout<< MST[i].second.second <<endl;
        cout<< MST[i].first <<endl;
    }
        cout << total <<endl;
}

Answer 1

问题是在kruskals调用范围内的graph是全局graph，声明为vector<pair<int,Edges> >。所以你不能用EdgeLess来排序，因为EdgeLess比较的是Edges，而不是pair<int,Edges>。

我是否可以建议，有一个名为graph的全局变量，它的类型是vector<pair<int,Edges> >，以及各种名为graph的局部变量，它的类型是vector<pair<Edges> >，这是不必要的混乱?如果真的需要所有这些不同的变量，以及它们当前的作用域和当前的类型，那么您可能应该将全局变量重命名为表明它是全局的东西。