算法导论 第二十五章：有向图的传递闭包

   已知一有向图G=<V,E>,顶点集合V={1,2,...,n},我们可能希望确定对所有顶点对i,j ∈ V，图G中事发后都存在一条从i到 j 的路径。G的传递闭包定义为图，其中：

                                                       

     在Θ(n^3)时间内计算出图的传递闭包的一种方法是对E中每条边赋以权值1，然后运行Floyd-Warshall算法。如果顶点i到顶点j存在一条路径，则d(i,j)<n，否则d(i,j)=∞。

   另一种方法与Floyd-Warshall类似，可以在Θ(n^3)内计算出图G的传递闭包，且在实际中可以节省时空需求，具体原理如下：

       将Floyd-Warshall中的min和+操作，用相应的逻辑运算∨（逻辑OR）和∧(逻辑AND)来代替，对于i,j,k = 1,2,...,n，如果图G中从顶点i到顶点j存在一条通路，且所有中间顶点均属于集合{1,2,...k},则定义如下：

当k ≥ 1时，有：

    

伪代码：

EG:

完整代码：

#include<iostream>
#include<climits>
#include<iomanip>
using namespace std;

typedef int vType;
typedef int wType;
typedef struct edge{
	vType u;   // the start of edge
	vType v;   // the end of edge
	}edge;
typedef struct MGraph{
	int vNum;
	int eNum;
	vType *V;
	edge *E;
	}MGraph;

void Matrix_Print(bool **M,int n)
{
	for(int i=0; i< n; i++)
	{ 
		for(int j=0; j<n; j++)
			cout<<setw(2)<<M[i][j];
		cout<<endl;
		}
	}
int Locate(MGraph &G,vType v)
{
	for(int i=0; i<G.vNum; i++)
		if(v == G.V[i])
			return i;
	return -1;
	}	
void Graph_Init(MGraph &G,vType V[],edge E[])
{
	//init the vertices 
	G.V = new vType[G.vNum];
	for(int i=0; i<G.vNum; i++)
		G.V[i] = V[i];
	//init the edge
	G.E = new edge[G.eNum];
	for(int i=0 ; i<G.eNum; i++){
		G.E[i].u = E[i].u;
		G.E[i].v = E[i].v;
		} 
	}
bool **Matrix_Copy(bool **M,int n)
{
	bool **T = new bool*[n];
	for(int i=0; i<n; i++)
		T[i] = new bool[n];

	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			T[i][j] = M[i][j];
	return T;
	}
/*----------------------Transitive Closure Alogrithm-----------------------------*/
bool **T;
bool **Transitive_Closure(MGraph &G){
	int n = G.vNum;
	//alloc memory for matrix T;
	T = new bool*[n];
	for(int i=0; i<n; i++)
		T[i]= new bool[n];
	//when beginning,matrix T denote T[0]
	for(int i =0 ; i<n; i++)
		for(int j=0; j<n; j++)
			if(i == j)
				T[i][j] = 1;
			else
				T[i][j] = 0;
	for(int i=0; i<G.eNum; i++)
	{
		int u_i = Locate(G,G.E[i].u);
		int v_i = Locate(G,G.E[i].v);
		T[u_i][v_i] = 1;
		}

	bool **tempT = new bool*[n];
	for(int i=0; i<n; i++)
		tempT[i] = new bool[n];
	for(int k=0; k<n; k++){
		tempT = Matrix_Copy(T,n);
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				T[i][j] = tempT[i][j] | (tempT[i][k] & tempT[k][j]);
		//cout<<"The "<<k<<"th round is:"<<endl;
		//Matrix_Print(T,n);
		}
	return T;
	}
/*-------------------------------------------------------------------------------*/
int main()
{
	vType V[]={1,2,3,4};
	edge  E[]={{2,3},{2,4},{3,2},{4,1},{4,3}};
	MGraph G;
	G.vNum = sizeof(V)/sizeof(vType);
	G.eNum = sizeof(E)/sizeof(edge) ;
	Graph_Init(G,V,E);
	T = Transitive_Closure(G);
	cout<<"The final transitive closure matrix is:"<<endl;
	Matrix_Print(T,G.vNum);
	return 0;
	}

运行结果：

【注：若有错误，请指正~~~】