1

今朝、トポロジー順序付けの実装である C++ クラスの割り当てを行っていました。コンパイル中にエラーはありませんが、単に実行できません。私はポインターや STL にも、VS デバッガーにもあまり詳しくないので、どこが間違っていたのかわかりません。誰かが私の間違いを指摘してくれると、とても助かります。たくさんのありがとう！

これが私のコードです：

#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;
}
4

1 に答える 1

2

問題の明らかな出発点は、の割り当てです。割り当ては、ゼロである可能性が高い初期化されEdgesていない値を使用します。numEdgeつまり、要素へのポインターを取得しません。Edgesおそらく、読み取り後にのみ割り当てたいと思うでしょうnumEdge。実際のアルゴリズムで何が起こるかを実際に見ていませんでした。

また、入力操作が成功したことを確認することを強くお勧めします。

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

入力が失敗した場合、変数は変更されず、値も興味深い動作につながります。

于 2012-10-16T17:50:32.850 に答える