tree-test.cpp

算法中图算法的详细实现

#include <iostream>
#include "Tree.h"

int main()
{
	for( int i = 0; i < 50; i ++ )
		cout << "-- ";
	Tree bfsTree( 8 );
	bfsTree.addOneEdge( 1 , 2 );
	bfsTree.addOneEdge( 1 , 5 );
	bfsTree.addOneEdge( 2 , 6 );
	bfsTree.addOneEdge( 2 , 1 );
	bfsTree.addOneEdge( 3 , 4 );
	bfsTree.addOneEdge( 3 , 6 );
	bfsTree.addOneEdge( 3 , 7 );
	bfsTree.addOneEdge( 4 , 3 );
	bfsTree.addOneEdge( 4 , 7 );
	bfsTree.addOneEdge( 4 , 8 );
	bfsTree.addOneEdge( 5 , 1 );
	bfsTree.addOneEdge( 6 , 2 );
	bfsTree.addOneEdge( 6 , 3 );
	bfsTree.addOneEdge( 6 , 7 );
	bfsTree.addOneEdge( 7 , 3 );
	bfsTree.addOneEdge( 7 , 4 );
	bfsTree.addOneEdge( 7 , 6 );
	bfsTree.addOneEdge( 7 , 8 );
	bfsTree.addOneEdge( 8 , 4 );
	bfsTree.addOneEdge( 8 , 7 );
	cout << "BFS:" << endl;
	for( int i = 1; i <= 8; i ++ )
	{
		cout << "Root vertex: " << i << " :";
		bfsTree.BFS( i );
		cout << endl;
	}
		cout << endl;

	for( int i = 1; i <= 8; i ++ )
	{
		bfsTree.BFS( i );
		cout << endl;
		for( int j = 1; j <= 8; j ++ )
		{
			if( i == j )
				continue;
			cout << "The path from: " << i << " to " << j << " is:" << endl;
			bfsTree.print( i , j );
			cout << endl;
		}
		cout << endl;
	}
	for( int i = 0; i < 50; i ++ )
		cout << "-- ";
	cout << endl;
	cout << "DFS:" << endl;
	Tree dfsTree( 9 );
	dfsTree.addOneEdge( 1 , 4 );
	dfsTree.addOneEdge( 1 , 5 );
	dfsTree.addOneEdge( 2 , 5 );
	dfsTree.addOneEdge( 4 , 5 );
	dfsTree.addOneEdge( 4 , 6 );
	dfsTree.addOneEdge( 7 , 6 );
	dfsTree.addOneEdge( 6 , 9 );
	dfsTree.addOneEdge( 7 , 8 );
	dfsTree.addOneEdge( 8 , 9 );
	dfsTree.DFS();
	cout << "The Topologic sort is:" << endl;
	dfsTree.printTopologic();
	cout << endl;

	for( int i = 0; i < 50; i ++ )
		cout << "-- ";
	cout << endl;
	cout << "Strongly connected components:" << endl;
	Tree sccTree( 8 );
	sccTree.addOneEdge( 1 , 2 );
	sccTree.addOneEdge( 2 , 3 );
	sccTree.addOneEdge( 2 , 5 );
	sccTree.addOneEdge( 2 , 6 );
	sccTree.addOneEdge( 3 , 4 );
	sccTree.addOneEdge( 3 , 7 );
	sccTree.addOneEdge( 4 , 3 );
	sccTree.addOneEdge( 4 , 8 );
	sccTree.addOneEdge( 5 , 1 );
	sccTree.addOneEdge( 5 , 6 );
	sccTree.addOneEdge( 6 , 7 );
	sccTree.addOneEdge( 7 , 6 );
	sccTree.addOneEdge( 7 , 8 );
	sccTree.addOneEdge( 8 , 8 );
	sccTree.strongly_connected();
	cout << endl;
	for( int i = 0; i < 50; i ++ )
		cout << "-- ";
	cout << endl;
	cout << "MST" << endl;
	Tree mstTree( 9 );

	mstTree.addOneEdge( 1 , 2 , 4 );
	mstTree.addOneEdge( 1 , 8 , 8 );
	mstTree.addOneEdge( 2 , 1 , 4 );
	mstTree.addOneEdge( 2 , 3 , 8 );
	mstTree.addOneEdge( 2 , 8 , 11);
	mstTree.addOneEdge( 3 , 2 , 8 );
	mstTree.addOneEdge( 3 , 4 , 7 );
	mstTree.addOneEdge( 3 , 6 , 4 );
	mstTree.addOneEdge( 3 , 9 , 2 );
	mstTree.addOneEdge( 4 , 3 , 7 );
	mstTree.addOneEdge( 4 , 5 , 9 );
	mstTree.addOneEdge( 4 , 6 , 14 );
	mstTree.addOneEdge( 5 , 4 , 9 );
	mstTree.addOneEdge( 5 , 6 , 10 );
	mstTree.addOneEdge( 6 , 3 , 4 );
	mstTree.addOneEdge( 6 , 4 , 14 );
	mstTree.addOneEdge( 6 , 5 , 10 );
	mstTree.addOneEdge( 6 , 7 , 2 );
	mstTree.addOneEdge( 7 , 6 , 2 );
	mstTree.addOneEdge( 7 , 8 , 1 );
	mstTree.addOneEdge( 7 , 9 , 6 );
	mstTree.addOneEdge( 8 , 1 , 8 );
	mstTree.addOneEdge( 8 , 2 , 11 );
	mstTree.addOneEdge( 8 , 7 , 1 );
	mstTree.addOneEdge( 8 , 9 , 7 );
	mstTree.addOneEdge( 9 , 3 , 2 );
	mstTree.addOneEdge( 9 , 7 , 6 );
	mstTree.addOneEdge( 9 , 8 , 7 );
	mstTree.MST_PRIM(1);
	cout << endl;

	for( int i = 0; i < 50; i ++ )
		cout << "-- " ;
	cout << endl;
	cout << "Single Source Shortest Path: " << endl;
	Tree dijTree( 5 );
	dijTree.addOneEdge( 1 , 2 , 10 );
	dijTree.addOneEdge( 1 , 4 , 5 );
	dijTree.addOneEdge( 2 , 4 , 2 );
	dijTree.addOneEdge( 2 , 3 , 1 );
	dijTree.addOneEdge( 3 , 5 , 4 );
	dijTree.addOneEdge( 4 , 2 , 3 );
	dijTree.addOneEdge( 4 , 3 , 9 );
	dijTree.addOneEdge( 4 , 5 , 2 );
	dijTree.addOneEdge( 5 , 1 , 7 );
	dijTree.addOneEdge( 5 , 3 , 6 );
	cout << "Produced by dijkstra algorithm:" << endl;
	dijTree.dijkstra( 1 );
	dijTree.print_all_single_source_path( 1 );
	cout << endl;
	cout << "Produced by bellman-ford algorithm:" << endl;
	if( dijTree.bellman_ford( 1 ) )
		dijTree.print_all_single_source_path( 1 );
	else
		cout << "There exist one or more negtive circle(s)." << endl;

	for( int i = 0; i < 50; i ++ )
		cout << "-- ";
	cout << endl;
	cout << "All pairs shortest paths" << endl;
	Tree allTree( 5 );
	allTree.addOneEdge( 1 , 2 , 3 );
	allTree.addOneEdge( 1 , 3 , 8 );
	allTree.addOneEdge( 1 , 5 , -4 );
	allTree.addOneEdge( 2 , 4 , 1 );
	allTree.addOneEdge( 2 , 5 , 7 );
	allTree.addOneEdge( 3 , 2 , 4 );
	allTree.addOneEdge( 4 , 1 , 2 );
	allTree.addOneEdge( 4 , 3 , -5 );
	allTree.addOneEdge( 5 , 4 , 6 );

	cout << "Produced by \"slow_all_pairs_shortest_paths\"" << endl;
	allTree.slow_all_pairs_shortest_paths();
	allTree.print_all_pairs_shortest_paths();


	cout << "Produced by \"Floyd-Warshall\"" << endl;
	allTree.Floyd_Warshall();
	allTree.print_all_pairs_shortest_paths();
	cout << endl;
	return 0;
}