Kruskal算法（排序）

我正在讀取文件中的表示並將其存儲在鄰接列表中。然後我以「graphviz格式」輸出圖形，並在圖形上執行MST算法。最後，我以「graphviz格式」輸出MST。我在C++中這樣做。Kruskal算法（排序）

我的主要問題是與算法。我正在實現Kruskals算法，並且排序功能不起作用。

當我編譯它，我得到這個錯誤：

instantiated from ‘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; 
}

來源

2011-11-11 kay

不行嗎？大多數SO用戶不會通讀所有代碼來調試可能是單線問題的內容。 – Alex

請發佈整個錯誤消息。 – Erbureth

的問題是，這是在範圍上調用kruskals的是全球，聲明爲vector<pair<int,Edges> >。所以你不能用EdgeLess來排序它，因爲EdgeLess比較Edges es，而不是pair<int,Edges> es。

我可能會建議它了不必要的混亂有一個名爲一個全局變量的類型是vector<pair<int,Edges> >一起命名具有類型vector<pair<Edges> >各種局部變量？如果真的需要需要所有這些不同的變量，以及它們的當前範圍和當前類型，那麼您應該將全局變量重命名爲表明它是全局變量。

來源

2011-11-11 21:34:09 ruakh

所以你建議我重命名圖形命名爲一個全局變量.. – kay

Kruskal算法（排序）

回答

相關問題