113.txt

邻接矩阵类的根是A d j a c e n c y W D i g r a p h

template<class T>
class AdjacencyWDigraph {
friend AdjacencyWGraph<T>;
p u b l i c :
AdjacencyWDigraph (int Vertices = 10, T noEdge = 0);
~AdjacencyWDigraph() {Delete2DArray(a,n+1);}
bool Exist(int i, int j) const;
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);
int OutDegree(int i) const;
int InDegree(int i) const;
p r i v a t e :
T NoEdge; // 用于没有边存在的情形
int n; // 顶点数目
int e; // 边数
T **a; // 二维数组
} ;
template<class T>
AdjacencyWDigraph<T>::AdjacencyWDigraph(int Vertices, T noEdge)
{// 构造函数
n = Ve r t i c e s ;
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>
class AdjacencyWGraph : public AdjacencyWDigraph<T> {
p u b l i c :
AdjacencyWGraph(int Vertices = 10, T noEdge = 0) : AdjacencyWDigraph<T>(Vertices, noEdge) {}
AdjacencyWGraph<T>& Add(int i, int j, const T& w)
{ A d j a c e n c y W D i g r a p h < T > : : A d d ( i , j , w ) ;
a[j][i] = w;
return *this;}
AdjacencyWGraph<T>& Delete(int i, int j)
{ A d j a c e n c y W D i g r a p h < T > : : D e l e t e ( i , j ) ;
a[j][i] = NoEdge;
return *this;}
int Degree(int i) const {return OutDegree(i);}
} ;
class AdjacencyDigraph : public AdjacencyWDigraph<int> {
p u b l i c :
AdjacencyDigraph(int Vertices = 10) : AdjacencyWDigraph<int>(Vertices, 0) {}
AdjacencyDigraph& Add(int i, int j)
{ A d j a c e n c y W D i g r a p h < i n t > : : A d d ( i , j , 1 ) ;
return *this;}
AdjacencyDigraph& Delete(int i, int j)
{ A d j a c e n c y W D i g r a p h < i n t > : : D e l e t e ( i , j ) ;
return *this;}
} ;
class AdjacencyGraph : public AdjacencyWGraph<int>
{
p u b l i c :
AdjacencyGraph(int Vertices = 10) : AdjacencyWGraph<int>(Vertices, 0) {}
AdjacencyGraph& Add(int i, int j)
{ A d j a c e n c y W G r a p h < i n t > : : A d d ( i , j , 1 ) ;
return *this;}
AdjacencyGraph& Delete(int i, int j)
{ A d j a c e n c y W G r a p h < i n t > : : D e l e t e ( i , j ) ;
return *this;}
} ;