#include<iostream>
using namespace std;
const int MaxVertexes=20; //最大的顶点数
const int b=10000;
template <class Type> class Graph ;
struct ArcNode{//定义边结点
friend class Graph <class Type>;
int adjvex; //和边（或弧）相关联的另一个顶点序号
int weight; //边（或弧）上的信息
ArcNode *nextarc ; //指向下一条边结点的指针
ArcNode(int v,int w ) : adjvex( v ),weight(w),nextarc( NULL ){ }
};//构造函数
template <class Type>
struct VertexNode{// 定义顶点结点
friend class Graph <class Type>;
Type data; //顶点的信息
ArcNode *firstarc ; //指向依附该顶点的边链表
};
template <class Type>class Graph
{
VertexNode<Type> * VTable; //顶点表
int CurrentNumVertexes; //当前的顶点数
int CurrentNumArcs; //当前的边（或弧）数
public:
int GetVertexPos( const Type &v );// 取顶点v在数组中的位置
Graph(Type v[],int num=MaxVertexes); //构造函数
Type GetValue(int v); //取图中顶点v的值，如果顶点v不存在则返回空
int Getweight(int v1,int v2); //取边（或弧）上的权值
int GetFirstNeighbor(int v); //取图中顶点v的第一个邻接点的序号。如果不存在返回-1
int GetNextNeighbor(int v1, int v2); //取图中下一个邻接点
int Arcs[MaxVertexes][MaxVertexes];//用数组记录每个边的信息
int InVertex(Type &v); //在图中插入结点
int InsertArc(int v1, int v2,int w);//在图中插入依附于v1和v2的边或弧，w是信息
int NumberOfVertexes( ){return CurrentNumVertexes; } //返回当前的顶点数
int NumberOfArcs(){ return CurrentNumArcs; } //返回当前的边（或弧）数
int *dist; //最短路径长度数组
int *InDegree; //入度数组，记录每个顶点的入度
int *path; //最短路径的数组
int *s; //最短路径终点数组
void link(); //输出邻接链表
void DFS(const int v,int visited[]);//深度优先搜索
void DFTraverse (); //深度遍历
void TopologicalOrder(); //拓扑排序
void ShortestPath(int n,int v);//最短路径
};
///////////////////////////////////////////////////////////////////////////////////
template<class Type>int Graph<Type>::
GetVertexPos(const Type &v ){ //根据顶点v查找该顶点在邻接表中的位置
for(int i=0;i<CurrentNumVertexes;i++)
if(VTable[i].data==v) return i;
return -1;
}
template<class Type>Graph<Type>::Graph( Type v[] , int num=MaxVertexes) :
CurrentNumVertexes(0), CurrentNumArcs(0)
{
Type tail, head;
int i=0,e,h,t,w,p=0;
while(p<MaxVertexes){
for(int j=0;j<MaxVertexes;j++){
