lgraph.h

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

// 图的链表描述，派生于“有向图的邻接链表”
// 最终版

#ifndef LinkedGraph_
#define LinkedGraph_

#include "ldigraph.h"
#include "undirect.h"
#include "xcept.h"

class LinkedGraph : public LinkedDigraph, virtual public Undirected {
   public:
      LinkedGraph(int Vertices = 10) : LinkedDigraph (Vertices) {}
      LinkedGraph& Add(int i, int j);
      LinkedGraph& Delete(int i, int j);
      int Degree(int i) const {return InDegree(i);}//
      int OutDegree(int i) const {return InDegree(i);}
   protected:
      LinkedGraph& AddNoCheck(int i, int j);
};

LinkedGraph& LinkedGraph::Add(int i, int j)
{// Add edge (i,j) to the graph.
   if (i < 1 || j < 1 || i > n || j > n || i ==j
       || Exist(i, j)) throw BadInput();
   return AddNoCheck(i, j);
}

LinkedGraph& LinkedGraph::AddNoCheck(int i, int j)//插入边，要插入两次，因为无向图的边=两条有向图的边
{// 加入边（i，j），不检查错误.  错误检查在公有ADD中
   h[i].Insert(0,j);
   try {h[j].Insert(0,i);}
   //若出现异常，则取消插入，并引发同样的异常
   catch (...) {h[i].Delete(j); throw;}
   e++;
   return *this;
}

LinkedGraph& LinkedGraph::Delete(int i, int j)//同样，删除边，要删除两次，因为无向图的边=两条有向图的边
{// Delete edge (i,j).
   LinkedDigraph::Delete(i,j);
   e++; //因为第一次调用LinkedDigraph的Delete已经使e--了，所以为了下面一次再度调用，这里补偿一下，e++
   LinkedDigraph::Delete(j,i);
   return *this;
}

#endif