c++ - 拓扑排序的 C++ 实现

Question

今天早上我正在做我的 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;
}

Answer 1

您的问题的一个明显起点是Edges 的分配:分配使用未初始化的值numEdge，它可能为零。也就是说，您将得到一个指向任何元素的指针。您可能只想在读取 numEdge 之后分配 Edges。我并没有真正了解实际算法中发生了什么。

我还强烈建议您验证输入操作是否成功:

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

如果输入失败，变量保持不变，值也会导致有趣的行为。