学步园

#include <map>
#include <stack>
#include <queue>
#include <list>
#include <utility>
#include <string>
#include <cassert>
#include <iostream>

using namespace std;

namespace topsort
{
	static string INVALID_VNAME = "NULL";
	const static int INVALID_TOPNUM = -1;
	const static int INVALID_INDEGREE = -1;

	typedef struct _Node
	{
		int topNum;
		int inDegree;
		list<string > adjList;
		string vName;

		_Node(const string &_vName=INVALID_VNAME, int _inDegree=INVALID_INDEGREE, int _topNum=INVALID_TOPNUM )
			: vName(_vName), inDegree(_inDegree), topNum(_topNum)
		{}
	}Node, *pNode;

	class Cmp
	{
	public:
		bool operator()( const Node *li, const Node *ri)
		{
			return li->topNum > ri->topNum;
		}
	};
	map<string, Node* > mGraph;

	void topSort(void)
	{
		deque<string> sTmp;
		Node *node(NULL);
		int tn(0);

		for ( map<string, Node*>::iterator it=mGraph.begin(); it!=mGraph.end(); ++it )
		{
			if ( it->second->inDegree==0 )
			{
				it->second->topNum = tn++;
				sTmp.push_back(it->second->vName);
			}
		}

		while ( !sTmp.empty())
		{
			node = mGraph[sTmp.front()];
			assert( node->inDegree==0 );
			sTmp.pop_front();
			for ( list<string>::iterator it=node->adjList.begin(); 
										it!=node->adjList.end(); ++it)
			{
				if ( --mGraph[*it]->inDegree==0 )
				{
					mGraph[*it]->topNum = tn++;
					sTmp.push_back(*it);
				}
			}
		}
	}

	void Print(void)
	{
		cout << "top sort result: " << endl;
		priority_queue<Node*, vector<Node*>, Cmp> pQ;
		Node *pN;

		for ( map<string, Node*>::iterator it=mGraph.begin(); it!=mGraph.end(); ++it)
			pQ.push( it->second );

		while (!pQ.empty())
		{
			pN = pQ.top();
			pQ.pop();
			cout << pN->vName.c_str() << "-" << pN->topNum << endl;
		}

		cout << endl;
	}
};

#include <cstdlib>
#include "topSort.h"

using namespace topsort;

int main()
{
	list<string> lpN;
	mGraph.clear();
	
	//
	mGraph["v1"] = new Node("v1", 0);
	mGraph["v2"] = new Node("v2", 1);
	mGraph["v3"] = new Node("v3", 2);
	mGraph["v4"] = new Node("v4", 3);
	mGraph["v5"] = new Node("v5", 1);
	mGraph["v6"] = new Node("v6", 3);
	mGraph["v7"] = new Node("v7", 2);

	lpN.clear();
	lpN.push_back("v2");
	lpN.push_back("v3");
	lpN.push_back("v4");
	mGraph["v1"]->adjList.assign( lpN.begin(), lpN.end());

	lpN.clear();
	lpN.push_back("v4");
	lpN.push_back("v5");
	mGraph["v2"]->adjList.assign( lpN.begin(), lpN.end());

	lpN.clear();
	lpN.push_back("v6");
	mGraph["v3"]->adjList.assign( lpN.begin(), lpN.end());

	lpN.clear();
	lpN.push_back("v3");
	lpN.push_back("v6");
	lpN.push_back("v7");
	mGraph["v4"]->adjList.assign( lpN.begin(), lpN.end());

	lpN.clear();
	lpN.push_back("v4");
	lpN.push_back("v7");
	mGraph["v5"]->adjList.assign( lpN.begin(), lpN.end());

// 	lpN.clear();
// 	mGraph["v6"]->adjList.assign( lpN.begin(), lpN.end());

	lpN.clear();
	lpN.push_back("v6");
	mGraph["v7"]->adjList.assign( lpN.begin(), lpN.end());

	//
	topSort();
	Print();

	//
	for ( map<string, pNode>::iterator it=mGraph.begin(); it!=mGraph.end(); ++it)
		delete it->second;

	system("pause");
	return 0;
}