adjacencywdigraph.h

GSP寻找最短路径的算法 可以用文件保存输入的信息 存储地址D：//存储.txt

//加权有向图的耗费邻接矩阵
#ifndef AdjacencyWDigraph_
#define AdjacencyWDigraph_
#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
#include "BadInput.h"
#include "Chain.h"
#include "OutOfBounds.h"
#include "ChainIterator.h"
template<class T>
class AdjacencyWDigraph {
public:
	AdjacencyWDigraph (int Vertices = 10, T noEdge = 0);//默认情况
	~AdjacencyWDigraph() {Delete2DArray(a,n);}//析构函数
	bool Exist(int i, int j) const;//判断边（i，j）是否存在
	int Edges() const {return e;}//返回边的条数
	int Vertices() const {return n;}//返回顶点个数
	AdjacencyWDigraph<T>& Add (int i, int j, const T& w);//添加一条边及它的权值
	AdjacencyWDigraph<T>& Delete(int i, int j);//删除边（i，j）
	int OutDegree(int i) const;//返回顶点i的出度
	int InDegree(int i) const;//返回顶点i的入度
    void ShortestPaths(int s, T d[], int p[]);//单元点最短路径算法
	void Outpput(){
		for(int i=1;i<=n;i++)
		{for(int j=1;j<=n;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;}}
	//新添方法 使用文件存储
	void initial();
	void initial(int c);
	void keep();
private:
	T NoEdge; // 用于没有边存在的情形
	int n; // 顶点数目
	int e; // 边数
	T **a; // 二维数组
	void Delete2DArray(T ** &x,int rows)//删除二维数组
	{
		for(int i=0;i<=rows;i++)
		delete []x[i];
		delete []x;
		x=0;
	}
	void Make2DArray( T ** &x, int rows, int cols)//创建二维数组
	{
		x = new T * [rows];
		for (int i = 0 ; i<rows; i++)
		x[i] = new int [cols];
	}
};
template<class T>
AdjacencyWDigraph<T>::AdjacencyWDigraph(int Vertices, T noEdge)
{// 构造函数
	n=Vertices;
	e=0;
	NoEdge=noEdge;
	Make2DArray(a,n+1,n+1);
	//初始化为没有边的图
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			a[i][j]=NoEdge;
}
template<class T>
bool AdjacencyWDigraph<T>::Exist(int i, int j) const
{// 边(i, j)存在吗?
	if(i<1||j<1||i>n||j>n||a[i][j]==NoEdge)
		return false;
	return true;
}
template<class T>
AdjacencyWDigraph<T>& AdjacencyWDigraph<T> ::Add(int i, int j, const T& w)
{// 如果边(i,j) 不存在，则将该边加入有向图中
	if(i<1||j<1||i>n||j>n||i==j||a[i][j]!=NoEdge)
	throw BadInput();
	a[i][j]=w;
	e++;
	return *this;
}
template<class T>
AdjacencyWDigraph<T>& AdjacencyWDigraph<T> ::Delete(int i, int j)
{ //删除边(i,j).
	if(i<1||j<1||i>n||j>n||a[i][j]==NoEdge)
	throw BadInput();
	a[i][j]=NoEdge;
	e--;
	return *this;
}
template<class T>
int AdjacencyWDigraph<T>::OutDegree(int i) const
{// 返回顶点i的出度
	if(i<1||i>n) 
		throw BadInput();
	//计算顶点i的出度
	int sum = 0;
	for (int j=1;j<=n;j++)
		if(a[i][j]!=NoEdge) 
			sum++;
	return sum;
}
template<class T>
int AdjacencyWDigraph<T>::InDegree(int i) const
{// 返回顶点i的入度
	if (i < 1 || i > n) 
		throw BadInput();
	// 计算顶点i的入度
	int sum = 0;
	for(int j=1;j<=n;j++)
	if(a[j][i]!=NoEdge) sum++;
	return sum;
}

template<class T>
void AdjacencyWDigraph<T>::ShortestPaths(int s,T d[],int p[])
{// 寻找从顶点s出发的最短路径, 在d中返回最短距离
	// 在p中返回前继顶点
	if(s<1||s>n) 
		throw OutOfBounds();
//	cout<<"one"<<endl;
	Chain<int> L; // 路径可到达顶点的列表
	ChainIterator<int> I;
	// 初始化d, p, L
	for(int i=1;i<=n;i++)
	{
		d[i]=a[s][i];
		if (d[i]==NoEdge) 
			p[i]=0;
		else 
		{
				p[i]=s;
				L.Insert(0,i);
		}
	}
//	cout<<"one"<<endl;
	// 更新d, p
	while (!L.IsEmpty()) 
	{// 寻找具有最小d的顶点v
//	cout<<"jinru while1"<<endl;
	int *v=I.Initialize(L);
	int *w=I.Next();
	while(w)
	{//	cout<<"jinru while  2"<<endl;
		if(d[*w]<d[*v])
			v=w;
		w=I.Next();
	}
	//从L中删除通向顶点v的下一最短路径并更新d
	int i=*v;
	int s;
	for(int y=1;y<=L.Length();y++)
	{   int n,m=100;
	    L.Find(y,n);
           if(d[n]<m)
		{	m=d[n];
		    s=y;
		}
	}
	L.Delete(s,*v);
	for (int j=1;j<=n;j++) 
	{
		if(a[i][j]!=NoEdge&&(!p[j]||d[j]>d[i]+a[i][j])) 
		{
		// 减小d [ j ]
		d[j] = d[i] + a[i][j];
		// 将j加入L
		if (!p[j])
			L.Insert(0,j);
		p[j] = i;
		}
	}
//	cout<<"one"<<endl;
}
//	cout<<"one"<<endl;
//	for(int z=1;z<=n;z++)
//		cout<<"d["<<z<<"]="<<d[z]<<endl;
}
template<class T>
void AdjacencyWDigraph<T>::initial()
{
	ifstream fin("D://存储.txt");
	if(!fin)
	{
		cout<<"文件无法打开！"<<endl;
		return;
	}
	fin>>n;
	e=0;
	Make2DArray(a,n+1,n+1);
	//初始化为没有边的图
	for(int i=1;i<=n;i++)
	{	for(int j=1;j<=n;j++)
		{
			fin>>a[i][j];
			if(a[i][j]!=0)
				e++;
		}
	}
	fin.close();

}
template<class T>
void AdjacencyWDigraph<T>::initial(int c)
{
	n=c;
	e=0;
	Make2DArray(a,n+1,n+1);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			a[i][j]=NoEdge;
}
template<class T>
void AdjacencyWDigraph<T>::keep()
{
	ofstream fou("D://存储.txt");
	if(!fou)
	{
		cout<<"文件无法打开！"<<endl;
		return;
	}
	fou<<n<<' ';
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			fou<<a[i][j]<<' ';
	fou.close();
	cout<<"文件保存完毕！"<<endl;
}
#endif