graphtest.cpp

数据结构c++-书的一些源代码

#include <conio.h>
#include <iostream.h>
#include <stdlib.h>

typedef char VerT;
typedef char DataType;
const int MaxVertices = 100;		
const int MaxWeight = 9999;	
	
#include "AdjMWGraph.h"
#include "Dijkstra.h"
#include "CreatAdjMWGraph.h"

void ShortPath(AdjMWGraph &G, int **distance, int **path)
{
	int n = G.NumOfVertices();
	for(int i = 0; i < n; i++)
		Dijkstra(G, i, distance[i], path[i]);
}

template <class T>
void Make2DArray(T** &a, int row, int col)
//定义二维动态数组a，其行数为row, 列数为col
{
	a = new T*[row];			//a为有row个指针的指针数组

	for(int i = 0; i < row; i++)
	{
		a[i] = new T[col];		//每个指针指向一个有col个元素空间的数组
	}
}

void main(void)
{
	AdjMWGraph g;
	char a[] = {'A','B','C','D','E','F'};
	RowColWeight rcw[] = {{0,2,5},{0,3,30},{1,0,2},{1,4,8},{2,1,15},{2,5,7},
		{4,3,4},{5,3,10},{5,4,18}};
	int n = 6, e = 9;

	CreatGraph(g, a, n, rcw, e);

	int m = g.NumOfVertices();
	int **distance, **path;
	Make2DArray<int>(distance, m, m);
	Make2DArray<int>(path, m, m);

	ShortPath(g, distance, path);

	int i ,j;
	for(i = 0; i < m; i++)
	{
		cout << "从顶点" << g.GetValue(i) << "到其他各顶点的最短距离为：" << endl;
		for(j = 0; j < m; j++)
			cout << "到顶点 " << g.GetValue(j) 
				<< " 的最短距离为：" << distance[i][j] << endl;

		cout << "从顶点" << g.GetValue(i) << "到其他各顶点的前一顶点分别为：" << endl;
		for(j = 0; j < m; j++)
			if(path[i][j] != -1)
				cout << "到顶点 " << g.GetValue(j) 
					<< " 的前一顶点为 " << g.GetValue(path[i][j]) << endl;
		getch();
	}

  }