tree.h

算法中图算法的详细实现

#ifndef HUGANG_TREE
#define HUGANG_TREE

#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>

using namespace std;

const int WHITE = 0;
const int GRAY = 1;
const int BLACK = 2;
class treenode
{
	public:
		int id;
		int value;
		int key;
		int color;
		treenode* parent;
		int distence;
		/*DFS*/
		int firsttime;
		int endtime;
		treenode();
		treenode( int id , int value = 1 )
		{
			this->id = id;
			this->value = value;
		}
		int getId()
		{
			return id;
		}
		void setId( int id )
		{
			this->id = id;
		}
		int getValue()
		{
			return value;
		}
		void setValue( int value )
		{
			this->value = value;
		}
};
class pair_cmp
{
	public:
	bool operator()(const pair< int , int >& p1 , const pair< int , int >& p2) const
	{
		if( p1.first == p2.first )
			return p1.second < p2.second;
		else
			return p1.first < p2.first;
	}
};
class value_cmp
{
	public:
		bool operator() ( const treenode* node1 , const treenode* node2 ) const
		{
			if( node1->value == node2->value )
				return node1->id < node2->id;
			else
				return node1->value < node2->value;
		}
};
class qnode
{
	public:
	int id;
	int key;
	qnode( int mid , int mkey ):id( mid ) , key( mkey ){}
	bool operator < ( qnode const& q ) const
	{
		if( key == q.key )
			return id < q.id;
		else
			return key < q.key;
	}
	/*
	bool operator == ( qnode const& q ) const
	{
		return ( id == q.id ) && ( key == q.key );
	}*/
};
class Tree
{
	private:
		vector< list< treenode* > > myTree;
		vector< list< treenode* > > myGT;
		int nnode;
		int myTime;
		int caseno;
		queue< treenode* >  myQueue;
		list< int > topologicalList;
		map< pair< int , int > , int , pair_cmp > edge;
		vector< vector< int > > matrix;
		vector< vector< int > > parent;

		public: Tree(int nnode);
		~Tree();
		void addOneEdge(int from , int to , int value = 1);
		void addOneEdge( int from , treenode* node); 
		void removeOneEdge( int from , int to );
		void BFS(int s);
		void DFS( );
		void dfs_visit( int root , vector< list< treenode* > >&G);
		void print_path( int root , int end ); 
		void print(int root ,  int end );
		void printTopologic(); 
		void getGT();
		void strongly_connected();
		void MST_PRIM(int root);
		int getEdgeValue( int from , int to );
		void initialize_single_source();
		void relax( int u , int v , set< treenode* , value_cmp >& myQueue );
		void dijkstra(int s);
		void print_all_single_source_path(int s);
		int print_single_source_path(int e);
		bool bellman_ford(int s);
		void slow_all_pairs_shortest_paths();
		void extend_shortest_paths();
		void print_all_pairs_shortest_paths();
		bool print_one_pair_shortest_path( int i , int j );
		void Floyd_Warshall();
		void setNnode( int n )
		{
			nnode = n;
		}
		int getNnode( )
		{
			return nnode;
		}
};

#endif