拓撲排序的C++實現

今天早上我正在做我的C++類的分配，一個拓撲排序的實現。編譯時沒有錯誤，但根本無法運行。由於我不太熟悉指針或STL，也沒有VS調試器......我只是無法弄清楚哪裏出了問題。如果有人能指出我的錯誤，這將幫助我很多。好感謝！拓撲排序的C++實現

這裏是我的代碼：

#include<iostream> 
#include<vector> 
#include<queue> 

using namespace std; 

typedef struct Vertex{ 
    int index; 
    int indegree; // indegree of vertex v is the total num of edges like(u,v) 
    vector<Vertex>adjacent; 
    int topoNum; // topological order of this vertex. 
}Vertex; 
typedef struct Edge{ 
    Vertex start; 
    Vertex in; 
}Edge; 

Vertex*InDegrees(int numVertex,int numEdge,Edge*edges) // calculate indegrees of all vertices. 
{ 
    Vertex*vertices=new Vertex[numVertex]; 
    for(int i=0;i<numVertex;i++){ vertices[i].index=i; vertices[i].indegree=0;} 
    for(int i=0;i<numEdge;i++) 
    { 
     int j=edges[i].in.index; 
     vertices[j].indegree++; 
     vertices[j].adjacent.push_back(edges[i].start); 
    } 
    return vertices; 
} 

int*topoSort(int numVertex,int numEdge,Edge*edges) 
{ 
    edges=new Edge[numEdge]; 
    Vertex*Vertices=new Vertex[numVertex]; 
    Vertices=InDegrees(numVertex,numEdge,edges); 

    queue<Vertex>q; 
    for(int i=0;i<numVertex;i++) 
    { 
     if(Vertices[i].indegree==0) 
      q.push(Vertices[i]); 
    } 

    int count=0; 
    while(!q.empty()) // Ordering completed when queue is empty. 
    { 
     Vertex v=q.front(); // get the vertex whose indegree==0 
     q.pop(); 
     v.topoNum=++count; 
     vector<Vertex>::iterator iter; 
     for(iter=v.adjacent.begin();iter!=v.adjacent.end();iter++) 
     { 
      Vertex w=*iter; 
      if(--w.indegree==0) 
       q.push(w); 
     } 
    } 
    int*topoOrder=new int[numVertex]; 
    for(int i=0;i<numVertex;i++) 
    { 
     int j=Vertices[i].topoNum; 
     topoOrder[j]=-1; // initial value, in case cycle existed. 
     topoOrder[j]=Vertices[i].index; 
    } 
    delete[]Vertices; 
    delete[]edges; 
    return topoOrder; 
} 

int main() 
{ 
    int numVertex,numEdge; 
    cin>>numVertex>>numEdge; 
    Edge*Edges=new Edge[numEdge]; 
    int indexStart,indexIn; 
    for(int i=0;i<numEdge;i++) 
    { 
     cin>>indexStart>>indexIn; 
     Edges[i].in.index=--indexIn; 
     Edges[i].start.index=--indexStart; 
    } 

    int*topoOrder=new int[numVertex]; 
    topoOrder=topoSort(numVertex,numEdge,Edges); 
    for(int i=0;i<numVertex-1;i++) 
    { 
     if(topoOrder[i]==-1) 
     { 
      cout<<"Cycle exists, not a DAG!"; 
      return 0; 
     } 
     cout<<topoOrder[i]<<","; 
    } 
    cout<<topoOrder[numVertex-1]<<endl; 

    delete[]Edges; 
    return 0; 
}

來源

2012-10-16 Sol

當你運行這個程序時會發生什麼？ –

爲什麼不使用向量而不是手動分配/刪除指針內存？ – undefined

@undefined：你的意思是，而不是像瘋了一樣泄露？ –

一個明顯的起點，你的問題是Edges分配：分配使用未初始化值numEdge這很可能是零。也就是說，你會得到一個指向沒有元素的指針。您只有在閱讀numEdge後纔可能要分配Edges。我沒有真正看看實際算法中會發生什麼。

我也強烈建議您驗證輸入操作是成功的：

if (std::cin >> numVertex >> numEdge) { 
    use_successfully_read(numVertex, numEdge); 
}

如果輸入失敗的變量保持不變，該值也將導致有趣的行爲。

來源

2012-10-16 17:50:32

非常感謝您的建議它確實解決了我的一個問題。 – Sol

拓撲排序的C++實現

回答

相關問題