C++算法-图算法-01

今天开始，每天晚上写一点C++算法中的图算法。主要是一些基础的东西，复习复习，写一写，希望能记得更牢固一些。内容来自《Algorithms in C++ Part 5--Graph Algorithms》,Robert Sedgewick。

 

第一章 图的属性和类型

 

我们一般用图来抽象那些不仅仅设计到元素集，而且还元素与元素之间的连接集的例子。例如：地图（TSP问题）、超文本（元素是文档，连接时超链接）、电路（芯片和导线）、调度（任务和约束）、事务（电话呼叫、现金转移等）、匹配（学生与岗位的匹配）、网络（计算机网络的组建）、程序结构（函数或模块之间的调用等）等等。

图问题有很大的挑战性，因为：

1.算法的开销不仅取决于元素集的属性，还依赖于连接集的很多属性（以及由连接所包含的图的全局属性）。

2.对于我们可能遇到的各种图类型，要为其建立准确的模型是相当困难的。

 

1.1 术语

略

 

1.2 图的ADT

程序1.1 Graph ADT接口

 

struct Edge
{
   int v,w;
   Edge(int v=-1,int w=-1) :v(v),w(w) {}
};

 

class GRAPH
{
private:
public:
   GRAPH(int,bool);
   ~GRAPH();
   int V() const;
   int E() const;
   bool directed() const;
   int insert(Edge);
   int remove(Edge);
   bool edge(int , int);
   class adjIterator
   {
   public:
      adjIterator(const GRAPH & ,int );//迭代器
      int beg();
      int nxt();
      bool end();
   };
};

此接口是实现和测试图算法的出发点。它定义了两个数据类型：一个简单的Edge数据类型和一个GRAPH数据类型。前者包括一个构造函数，它由两个给定定点创建一个Edge；后者则利用与表示无关的标准ADT接口方法来定义。

GRAPH的构造函数有两个参数：一个是给出定点个数的整数，另一个是布尔值，指出此图是无向的还是有向的（有向图），此参数默认为无向。

用于处理图和有向图的基本操作时一些ADT函数，包括创建和撤销图和有向图、报告顶点数和边数以及增加和删除边。迭代器类adjIterator允许客户程序对任意给定顶点相邻接的各个顶点进行处理。

1.3 邻接矩阵表示

略

1.4 邻接表表示

略

1.5 变化、扩展和开销

略

	边数组	邻接矩阵	邻接表
占用空间	E	V*V	V+E
初始化为空	1	V*V	V
复制	E	V*V	E
撤销	1	V	E
插入边	1	1	1
删除边	E	1	V
V是孤立的吗	E	V	1
有从u到v的路径吗？	ElgV	V*V	V+E