Hi everyone, I am a U.student from China, I would like ask a question about my assignment.
For the directed graph, I would like to perform topological sort for sorting up nodes, but I encountered some problem in queue which is able to be removed or added with certain elements.
My question is how I can perform queue in topological sort function? my algorithm is here
// The topological sort
void DGraph::topologicalSort(){
if(isTPSorted==false){
int j=0;
Queue ts;
while(ts.size()!=0)
/*dequeue() dequeue for queue*/
for(int i=0;i<50;i++){
if (visitedTable[i]>=0 && inDegTable[i] == 0)
/*enqueue(i) enqueue for queue*/
}
while(ts.size()>0){
predTable[j]=dequeue();/*putting into predTable*/
int a=predTable[j];
j++;
for(int k=0;k<50;k++){
if(adjMatrix[a][k]==1){
inDegTable[k]--;
if (inDegTable[k] == 0){
/*enqueue(k) enqueue for queue*/
}
}
}
}
isTPSorted = true;
}
return;
}
my professor gave a hint to perform queue:
In the implementation of the topological sort, a queue data structure is required. he said I can use the queue from the standard template library. Here are some short descriptions of the functions provided by the STL queue.
empty : true if the queue has no elements
front pop: returns a reference to the first
push : element of a queue removes the first element of a queue adds an element to the end of the queue
For example, include header <queue> and declare my queue as std::queue <int> Queue. And use push as Queue.push(int).
I could find some information in
http://www.sgi.com/tech/stl/queue.html. but I don't catch up the point.
Thank you very much
Unsolved 
