undirect.h

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

// 无向图/网络的一些函数

#ifndef Undirected_
#define Undirected_

#include "network.h"
#include "lstack.h"
#include "lqueue.h"
#include "edge.h"//Edge类型

//NodeType用于双向链接箱子
class NodeType {
   friend class Undirected;
   private:
      int left, right;
};

class Undirected : virtual public Network {
   public:
      virtual int Degree(int i) const = 0;
      bool Connected();//检查无向图/网络是否连通
      int LabelComponents(int L[]);//构件标识
      bool BipartiteCover(int L[], int C[], int& m);
	  bool Bipartite(int L[]);//决定图是否是双向的
	  bool DSpanningTree(int i, Edge DT[]);//深度优先生成树预处理函数
   private:
      void CreateBins(int b, int n);
      void DestroyBins() {delete [] node;delete [] bin;}
      void InsertBins(int b, int v);
      void MoveBins(int bMax, int ToBin, int v);
	  void dSpanningTree(int i, bool reach[], int& edges, Edge DT[]);//实质完成深度优先生成树的函数
      int *bin;
      NodeType *node;
};

bool Undirected::Connected()
{//当且仅当图是连通的，才返回true

   int n = Vertices();

   // 置所有顶点为未到达的
   int *reach = new int [n+1];
   for (int i = 1; i <= n; i++)
      reach[i] = 0;
   
   //对从顶点1出发可到达的顶点进行标记
   DFS(1, reach, 1);
   
   //检查是否所有顶点都已经被标记
   for (i = 1; i <= n; i++)
      if (!reach[i]) return false;
   return true;
}

int Undirected::LabelComponents(int L[])
{//构件标识
 //返回构件的数目，并用L[1:n]来表示构件标号
 // to represent a labeling of vertices by component.

   int n = Vertices();

   //初始时，所有顶点不属于任何构件
   for (int i = 1; i <= n; i++)
      L[i] = 0;

   int label = 0;  //label用来表示构件的数目
   //识别构件
   for (i = 1; i <= n; i++)
	   if (!L[i])
	   {//没有到达的顶点
		   //顶点i属于一个新的构件
		   label++;//所以+1  
		   BFS(i, L, label);//标记这个新的构件，可见此构件里面所有顶点都被标记为lable
	   } 

   return label;//返回最后一个构件的标记，可见也就是构件的数目
}

void Undirected::CreateBins(int b, int n)
{// 创建b个空箱子和n个节点
   node = new NodeType [n+1];
   bin = new int [b+1];
   //初始化，都为0先
   for (int i = 1; i <= b; i++)
      bin[i] = 0;
}

void Undirected::InsertBins(int b, int v)
{// 如果箱子不为空，插入v到箱子b。因为b是顶点v的New值，b=0意味着顶点v不能覆盖B中当前还未被覆盖的任何节点
   if (!b) return;   //所以建立覆盖时，这个箱子没有用处，可以舍去
   node[v].left = b; // 加入到左边
   if (bin[b]) node[bin[b]].left = v;
   node[v].right = bin[b];
   bin[b] = v;
}

void Undirected::MoveBins(int bMax, int ToBin, int v)
{//将顶点v从当前所在箱子移动到ToBin
   int l = node[v].left;
   int r = node[v].right;

   //从当前箱子中删除
   if (r) node[r].left = node[v].left;
   if (l > bMax || bin[l] != v) //不是最左节点
      node[l].right = r;
   else bin[l] = r;             //箱子l的最左边

   //添加到箱子ToBin
   InsertBins(ToBin, v);
}

bool Undirected::BipartiteCover(int L[], int C[], int& m)
{// 寻找一个二分图覆盖，L是输入顶点的标号，L[i]=1当且仅当i在A中。C是一个记录覆盖的输出数组
 // 如果途中不存在覆盖，则返回false，否则返回true；在m中返回覆盖的大小，在C[0:m-1]中返回覆盖
   int n = Vertices();

   //插件结构
   int SizeOfA = 0;
   for (int i = 1; i <= n; i++) // 确定集合A的大小
      if (L[i] == 1) SizeOfA++;
   int SizeOfB = n - SizeOfA;
   CreateBins(SizeOfB, n);
   int *New = new int [n+1]; //顶点i覆盖了B中New[i]个未被覆盖的顶点
   bool *Change = new bool [n+1];//Change[i]为true时当且仅当New[i]已改变
   bool *Cov = new bool [n+1];// Cov[i] 是true当且仅当顶点i被覆盖
   InitializePos();
   LinkedStack<int> S;
   
   //初始化
   for (i = 1; i <= n; i++)
   {
	   Cov[i] = Change[i] = false;
	   if (L[i] == 1)
	   {// i在A中
		   New[i] = Degree(i); //i覆盖了这么多
		   InsertBins(New[i], i);
	   }
   }
   
   //构造覆盖
   int covered = 0,       // 被覆盖的顶点
       MaxBin = SizeOfB;  // 可能非空的最大箱子
   m = 0;                 // C的游标
   while (MaxBin > 0)
   {// 搜索所有箱子
	   //选择一个顶点
	   if (bin[MaxBin])
	   {
		   //箱子不空
		   int v = bin[MaxBin]; //第一个顶点
		   C[m++] = v;          //把v加入到覆盖		   
		   //标记这个新覆盖的顶点
		   int j = Begin(v), k;
		   while (j)
		   {
			   if (!Cov[j])
			   {// j尚未被覆盖
				   Cov[j] = true;
				   covered++;
				   //修改New
				   k = Begin(j);
				   while (k)
				   {
					   New[k]--;     // j不计入在内
					   if (!Change[k])
					   {
						   S.Add(k);  //仅入栈一次
						   Change[k] = true;
					   }
					   k = NextVertex(j);
				   }
               }
			   j = NextVertex(v);
		   }
		   
		   //更新箱子
		   while (!S.IsEmpty())
		   {
			   S.Delete(k);
			   Change[k] = false;
			   MoveBins(SizeOfB, New[k], k);
		   }
	   }
	   else MaxBin--;
   }
   
   DeactivatePos();
   DestroyBins();
   delete [] New;
   delete [] Change;
   delete [] Cov;
   return (covered == SizeOfB);
}

bool Undirected::Bipartite(int L[])
{// Label the vertices such that every edge connects
 // a vertex with L[] = 1 to one with L[] = 2.
 // Return false if not bipartite and true if bipartite
   int n = Vertices();
   // set all labels to 0
   for (int v = 1; v <= n; v++)
      L[v] = 0;

   // do a breadth first search in each component
   LinkedQueue<int> Q;
   InitializePos();
   for (v = 1; v <= n; v++)
      if (!L[v]) {// new component
         L[v] = 1;
         Q.Add(v);
         while (!Q.IsEmpty()) {
            int w;
            Q.Delete(w);
            int u = Begin(w);
            while (u) {  // vertices adjacent to w
               if (L[u]) // old vertex
   	          {if (L[u] == L[w]) return false;} // same set
               else {// new vertex
                     Q.Add(u);
                     L[u] = 3 - L[w];} // assign u to other set
               u = NextVertex(w);
               }
            }
        }  

   DeactivatePos();

   return true;
}

bool Undirected::DSpanningTree(int i, Edge DT[])
{//寻找一课深度优先生成树。 从任一顶点i开始
 //将最后生成的树存入数组DT[0:n-2]
 //如果没找到生成树则返回false
	
	//从i处开始DFS搜索
	// saving edges used to reach new vertices
	InitializePos();   // 初始遍历器
	int n = Vertices();
	
	// 初始化到达标记
	bool *reach = new bool [n+1];
	for (int j = 1; j <= n; j++)
		reach[j] = false;
	
	int edges = 0; //迄今为止到达的边数目
	
	dSpanningTree(i, reach, edges, DT); //进行实质函数操作
	
	DeactivatePos(); // 释放遍历器空间
	delete [] reach;
	
	//当且仅当边数目为n-1时才找到了一棵生成树
	if (edges == n-1) return true;
	return false;
}

void Undirected::dSpanningTree(int v, bool reach[], int& edges, Edge DT[])
{//实质寻找DFS生成树的代码
	reach[v] = true;
	int u = Begin(v);
	while (u)
	{//u邻接于v
		if (!reach[u])
		{//一个新的未标记顶点
			// 加入(u,v) 到生成树中
			DT[edges].u= v;
			DT[edges++].v = u;
			dSpanningTree(u, reach, edges, DT);//递归进行
		}
	u = NextVertex(v);
	}
}
  
#endif