Как узнать, допустима ли топологическая сортировка?

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]<<" ";

1

c++topological-sort

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

У меня был точно такой же вопрос, как я работал над топологической сортировкой.
Существует функция 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;
}

0