network.h

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

// file network.h
//抽象基类Network
#ifndef Network_
#define Network_

#include "lqueue.h"
#include "lstack.h"

class Network {
   public:
      virtual int Begin(int i) = 0;
      virtual int NextVertex(int i) = 0;
      virtual void InitializePos() = 0;
      virtual void DeactivatePos() = 0;//以上为四个遍历函数，纯虚，不同图不同实现
      virtual int Vertices() const = 0;//顶点数目，也是纯虚实现
      virtual int Edges() const = 0;
      void BFS(int v, int reach[], int label);//宽度优先搜索
      void DFS(int v, int reach[], int label);//深度优先搜索
      bool FindPath(int v, int w, int &length, int path[]);//寻找路径
      bool Topological(int v[]);
   private:
      void dfs(int v, int reach[], int label);//实质实现深度优先搜索功能的私有成员函数
      bool findPath(int v, int w, int &length,int path[], int reach[]);//实际实现寻找路径的函数
};

void Network::BFS(int v, int reach[], int label)
{//宽度优先搜索
   LinkedQueue<int> Q;
   InitializePos(); // 初始化图遍历器数组，调用纯虚InitializePos函数，不同的类对象就有不同实现了
   reach[v] = label;//reach用来标记已到达的顶点，=label证明已到达顶点v了
   Q.Add(v);
   while (!Q.IsEmpty())
   {
	   int w;
	   Q.Delete(w);  //获得一个以标记的顶点
	   int u = Begin(w);//令u为邻接于顶点w的第一个顶点
	   while (u) {//访问w的邻接顶点
         if (!reach[u]) {//一个未曾到达的顶点
            Q.Add(u);
            reach[u] = label;} //标记
         u = NextVertex(w); //下一个与w邻接的顶点
         }
      }
   DeactivatePos(); //释放遍历器数组
}

void Network::DFS(int v, int reach[], int label)
{//深度优先搜索
   InitializePos(); //初始化图遍历器数组
   dfs(v, reach, label); //执行dfs
   DeactivatePos(); //释放图遍历器数组
}

void Network::dfs(int v, int reach[], int label)
{//实质实现深度优先搜索功能的代码，递归实现的
   reach[v] = label;
   int u = Begin(v);
   while (u)
   {//u邻接至v
	   if (!reach[u])
		   dfs(u, reach, label);
	   u = NextVertex(v);
   }
}

bool Network::FindPath(int v, int w, int &length, int path[])
{// 寻找一条从v到w的路径，返回路径的长度，并将路径存入数组path[0:length]
 // Return false if there is no path.

   //路径中的第一个顶点总是v
   path[0] = v;
   length = 0;  // 当前路径长度
   if (v == w) return true;

   // 为路径的递归搜索进行初始化
   int  n = Vertices();//n个顶点
   InitializePos();  //遍历器
   int *reach = new int [n+1];
   for (int i = 1; i <= n; i++)
      reach[i] = 0;//都初始化为没有走过
   
   //搜索
   bool x = findPath(v, w, length, path, reach);

   DeactivatePos();//释放遍历器空间
   delete [] reach;//释放临时标记数组reach
   return x;
}

bool Network::findPath(int v, int w, int &length,int path[], int reach[])
{//实质搜索路径的函数，其中 v!=w
 // Performs a depth-first search for a path to w.
   reach[v] = 1;
   int u = Begin(v);
   while (u)
   {
	   if (!reach[u])
	   {
		   length++;
		   path[length] = u; //将顶点u加入path
		   if (u == w) return true;
		   if (findPath(u, w, length, path, reach))
			   return true;
		   //否则不存在从u到w的路径
		   length--; //length要复位，也即不记录u
	   }
	   u = NextVertex(v);
   }
   return false;
}

bool Network::Topological(int v[])
{// 计算有向图的拓扑序列
 // 如果找到了一个拓扑序列，则返回true，此时在v[0:n-1]中记录了拓扑序列
 // 如果不存在，则返回false

   int n = Vertices();
   
   // 计算入度
   int *InDegree = new int [n+1];
   InitializePos(); // 图遍历器数组
   for (int i = 1; i <= n; i++) //先都初始化为0
      InDegree[i] = 0;
   for (i = 1; i <= n; i++)
   {// 从i出发的边，这个循环计算图初始的入度数组
      int u = Begin(i);
      while (u)
	  {
		  InDegree[u]++;
		  u = NextVertex(i);
	  }
   }
   
   //把入度为0的顶点压入堆栈
   LinkedStack<int> S;
   for (i = 1; i <= n; i++)
	   if (!InDegree[i]) S.Add(i);
   
   // 产生拓扑顺序
   i = 0;  // 跟踪数组v
   while (!S.IsEmpty()) {// select from stack
      int w;             // next vertex
      S.Delete(w);
      v[i++] = w;
      int u = Begin(w);
      while (u)
	  {//更新每个与w相邻的入度，-1
		  InDegree[u]--;
		  if (!InDegree[u]) S.Add(u);//更新过程中，若某个的入度变为0了，则压入栈中
		  u = NextVertex(w);
	  }
   }
   
   DeactivatePos();
   delete [] InDegree;
   return (i == n);
}

#endif;