adigraph.h

贪婪算法合集,包括二分覆盖,单源最短路径,拓扑排序,机器调度问题

//有向图的邻接矩阵（无权值），也就是权值为1

#ifndef AdjacencyDigraph_
#define AdjacencyDigraph_

#include "awdgraph.h"

class AdjacencyDigraph : public AdjacencyWDigraph<int> {
   public:
      AdjacencyDigraph(int Vertices = 10) : AdjacencyWDigraph<int>(Vertices, 0) {}
      AdjacencyDigraph& Add(int i, int j)
	  {AdjacencyWDigraph<int>::Add(i,j,1); return *this;}
      AdjacencyDigraph& Delete(int i, int j)
	  {AdjacencyWDigraph<int>::Delete(i,j); return *this;}
	  void Input() {Input(cin);}//根据习题要求 重载>>，以便输入有向图。同样对于其他图也可重载
      void Input(istream& in);
};

void AdjacencyDigraph::Input(istream& in)
{//输入邻接矩阵
	//开始，删除老数组先
	Delete2DArray(a,n+1);
	
	// 输入顶点和边的数目
	cout << "Enter the number of vertices in the digraph"
        << endl;
	cin >> n;
	if (n < 0) throw BadInput();
	cout << "Enter the number of edges in the digraph" << endl;
	int E;
	cin >> E;
	if (E < 0 || E > n*(n-1)) throw BadInput();
	
	//创建新的二维数组并且初始化为0
	Make2DArray(a, n+1, n+1);
	//初始化为没有边先
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			a[i][j] = 0;
	e = 0;
	NoEdge = 0;
	// 输入 and add them to a[][]
	int u, v;  // edge end points
	for (i = 1; i <= E; i++)
	{
		cout << "Enter edge " << i << endl;
		in >> u >> v;
		Add(u,v);//用Add来加入此边
	}
}

// overload >>
istream& operator>>(istream& in, AdjacencyDigraph& x)
{
	x.Input(in); return in;
}

#endif