c++ - 我怎么知道拓扑排序是否有效？

Question

我有这个 1...n 的图，现在我找到了一个拓扑排序的解决方案，我怎么知道它是否是一个有效的解决方案？例如，对于 n = 5；和这种连接1->2,2->3,1->3,1->5,

我有一个解决方案 4->1->5->2->3 。它有效吗？可能是我对topsort的想法不清楚。

为了方便起见，这是我的代码

int incoming[n],A[n][n];
priority_queue<int> Q;
while(m--){
    int i,j;
    cin>>i>>j;
    A[i][j] = 1;
    ++incoming[j];
}
for(int i=1;i<=n;++i)
    if(!incoming[i])
        Q.push(i);
vector<int> toplist;
while(!Q.empty()){
    int u = Q.top(); Q.pop();
    toplist.push_back(u);
    for(int i = 1;i<=n;++i)
    {
        if(A[u][i])
        {
            A[u][i] = 0;
            --incoming[i];
            if(!incoming[i])
                Q.push(i);
        }

    }
}
for(int i=0;i<toplist.size();++i)
    cout<<toplist[i]<<" ";

Answer 1

我在做拓扑排序时遇到了完全相同的问题。 有一个名为 bValidateTopSortResult() 的函数可以验证结果。 如果从 U 到 V 存在一条边，则 U 必须在最高排序中排在 V 之前。 重要的是要跟踪所有相邻的顶点。我已经存储在一个列表中。

#include <iostream>
#include <list>
#include <stack>
#include <map>

using namespace std;

struct GRAPH{
    int iVertices;

list<int> *ptrAdj;  //Has structure like ptrAdj[i]={j,k,l}.  This means that
                    //i is from-vertex and j,k,l are to-vertices.
}; 

int iTopSortOrder[10];
map<int, int> mapTopSort;

//
//Recursive function.
//Key is iterating  list<>*ptrAdj.
//
void
vTopSortRecursive( GRAPH* pG, int iVertexID, bool *bVisited, stack<int>& stResult )
{
   bVisited[iVertexID] = true;

   //Goes thru all adjacent vertices. 
   for( auto it : pG->ptrAdj[iVertexID]){
       if(bVisited[it] == false) 
           vTopSortRecursive( pG, it, bVisited, stResult );
   }

    //Pushes the vertex ID after all its children adjacent vertices are already 
   pushed.
   stResult.push(iVertexID);
}

void
vTopSort( GRAPH* ptrGraph )
{
    stack<int> stResult;
    bool bVisited[ptrGraph->iVertices];
    int iTopSortIndex = 0;

    for(int i=0; i < ptrGraph->iVertices; ++i )
        bVisited[i] = false;


    for(int i=0; i < ptrGraph->iVertices; ++i )
        if(bVisited[i] == false )
            vTopSortRecursive( ptrGraph, i, bVisited, stResult );

    cout << "Top sort result" << endl;
    while( !stResult.empty() ){
        int iTop = stResult.top();
        cout << iTop << endl;
        //Keeps track of the order of the vertex top sort.
        //mapTopSort[i] = j means vertex ID 'i' is in jth order in array.
        mapTopSort[iTop] = iTopSortIndex;
        //Keeps the top sort order in an array.
        iTopSortOrder[iTopSortIndex] = stResult.top();;
        stResult.pop();
        iTopSortIndex++;
    }
}
//All parent ID must come befoe children ID in top sort.
//mapTopSort[i] = j;  means that vertex ID 'i' is in jth place in the order.
bool
bValidateTopSortResult( GRAPH* ptrGraph )
{
    bool bValid=true;

    for(int iVertexID=0; iVertexID<ptrGraph->iVertices;iVertexID++)
    {
        for(auto it: ptrGraph->ptrAdj[iVertexID] ){
            if( mapTopSort[iVertexID] > mapTopSort[it] ){

                bValid = false;
                cout << "Invalid sort" << endl;
                cout << iVertexID << " must come before " << mapTopSort[it] << endl;
            }
        }
    }
    return bValid;
}

int
main(void)
{
    GRAPH *ptrGraph = new GRAPH;
    ptrGraph->iVertices = 6;

    ptrGraph->ptrAdj = new list<int>[6];
    ptrGraph->ptrAdj[5].push_back(2); 
    ptrGraph->ptrAdj[5].push_back(0); 
    ptrGraph->ptrAdj[4].push_back(0); 
    ptrGraph->ptrAdj[4].push_back(1); 
    ptrGraph->ptrAdj[2].push_back(3); 
    ptrGraph->ptrAdj[3].push_back(1); 

    vTopSort( ptrGraph );

    if (bValidateTopSortResult( ptrGraph ))
        cout << "Sort is valid";
    else
        cout <<"Sort is INVALID";

    return 0;
}