pex13_14.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#include <fstream.h>
#pragma hdrstop

#include "graph.h"

template <class T>
void Warshall(Graph<T>& G)
{
	VertexIterator<T> vi(G), vj(G);
   
	int i, j, k;
	int WSM[MaxGraphSize][MaxGraphSize];  // Warshall matrix
	int n = G.NumberOfVertices();
   
	// create an edge that connects each vertex to itself
	for(vi.Reset(),i=0;!vi.EndOfList();vi.Next(),i++)
		for(vj.Reset(),j= 0;!vj.EndOfList();vj.Next(), j++)
			if (i == j)
				WSM[i][i] = 1; 
			else
				WSM[i][j] = G.GetWeight(vi.Data(),vj.Data());
   
	// look at all triples. assign 1 to WSM when an edge from
	// vi to vj exists or there is a triple vi - vk - vj
	// connecting vi and vj.
	for (k = 0; k < n; k++)
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				WSM[i][j] |= WSM[i][k] & WSM[k][j];
   
	// print each vertex and its row of the Warshall
	// matrix
	for (vi.Reset(), i=0;!vi.EndOfList();vi.Next(), i++)
	{
		cout << vi.Data() << ":  ";
		for (j = 0; j < n; j++)
			cout << WSM[i][j] << "  ";
		cout << endl;
	}
}

void main(void)
{
	Graph<char> G;
	char graphFile[20];
	
	cout << "Enter the graph file name: ";
	cin >> graphFile;
	
	G.ReadGraph(graphFile);
	
	cout << "The reachability matrix is:" << endl << endl;
	Warshall(G);
}

/*
<Run #1>

Enter the graph file name: px13_13a.dat
The reachability matrix is:

A:  1  1  1  1  1  1  0  0
B:  1  1  1  1  1  1  0  0
C:  0  0  1  0  1  1  0  0
D:  1  1  1  1  1  1  0  0
E:  0  0  1  0  1  1  0  0
F:  0  0  1  0  1  1  0  0
G:  1  1  1  1  1  1  1  0
H:  1  1  1  1  1  1  1  1

<Run #2>

Enter the graph file name: px13_13b.dat
The reachability matrix is:

A:  1  1  1  1  1  1  1
B:  1  1  1  1  1  1  1
C:  1  1  1  1  1  1  1
D:  0  0  0  1  0  1  1
E:  0  0  0  1  1  1  1
F:  0  0  0  1  0  1  1
G:  0  0  0  1  0  1  1
*/