图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)。
查询
我们可能会做如下的查询:图是否为有向图,寻找给定顶点的出边,查询是否某条边存在,查询边的权值。程序员可以创建一个迭代器,返回图中任一顶点的邻边(以及其权值)。
更新
程序员可以在图中删除或者添加一条边。