首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》数据结构设计

关灯直达底部

图6-6的UML图中是本章我们将会在图上执行的关键操作,参考第3章的UML图。C++Graph类使用的是邻接表来存储的(有向或者无向)图,邻接表是用C++STL的核心类来实现的。并且,它将众多的表存储在数组中,一个顶点一个表。顶点u的表存储的是IntegerPair类,表示权重为w的边(u,v)。

图 6-6 关键图操作

图6-6的操作可以分为如下几类:

创建

图是创建自n个顶点的集合,也许有向,也许无向。load(char*)读取文件中的点和边的信息来更新图。如果图是无向的,那么添加边(u,v)的同时添加了边(v,u)。

查询

我们可能会做如下的查询:图是否为有向图,寻找给定顶点的出边,查询是否某条边存在,查询边的权值。程序员可以创建一个迭代器,返回图中任一顶点的邻边(以及其权值)。

更新

程序员可以在图中删除或者添加一条边。