topologicalorder.h

data+structures+using+c的源码

#ifndef H_TopOrder
#define H_TopOrder

#include <iostream>
#include <iomanip>
#include "graphType.h"

using namespace std;

template <class vType, int size>
class topologicalOrderT: public graphType<vType,size>
{
public:
	void bfTopOrder();
	  //Function to output the vertice in breadth first 
	  //topological order.
};


template<class vType, int size>
void topologicalOrderT<vType, size>::bfTopOrder()
{
   linkedQueueType<vType> queue;

   vType u;
   int ind, j;

   int *topologicalOrder;
   topologicalOrder = new int[gSize];

   for(ind = 0; ind < gSize; ind++)
	topologicalOrder[ind] = -1;

   int topIndex = 0;

   vType *adjacencyList; //array to store the adjacent vertices
   adjacencyList = new vType[gSize];
   int alLength = 0;

   int *predCount;
   predCount = new int[gSize];

   for(ind = 0; ind < gSize; ind++)
	predCount[ind] = 0;

   for(ind = 0; ind < gSize; ind++)
   {
	graph[ind].getAdjacentVertices(adjacencyList, alLength);

	for(j = 0; j < alLength; j++)
		predCount[adjacencyList[j]]++;
   }

   for(ind = 0; ind < gSize; ind++)
	if(predCount[ind] == 0)
  	   queue.addQueue(ind);


   while(!queue.isEmptyQueue())
   {
	   u = queue.front();
	   queue.deleteQueue();
	topologicalOrder[topIndex++] = u;

	graph[u].getAdjacentVertices(adjacencyList, alLength);
	for(int w = 0; w < alLength; w++)
	{
		predCount[adjacencyList[w]]--;
		if(predCount[adjacencyList[w]] == 0)
			queue.addQueue(adjacencyList[w]);
	}
   }//end while

	//output the vertices in breadth first topological order
   for(ind = 0; ind < gSize; ind++)
	cout<<topologicalOrder[ind]<<" ";
   cout<<endl;

   delete [] topologicalOrder;
   delete [] predCount;
   delete [] adjacencyList;

}//bfTopOrder

#endif