概述
图是计算机科学中用来表示复杂结构信息的一种基本结构。图6-1所示的就是图。
图 6-1 （a）都铎王朝，（b）计算机网络，（c）航线时间表本章我们会讨论一些通用的图表示法，以及一些频繁使用的图算法。本质上来说，一个图包含一个元素集合（也就是顶点），以及元素两两之间的关系（也就是边）。由于应用范围所限，本章我们仅仅讨论简单图，简单图并不会如（a）那样有一个顶点的一条边是自己指向自己，以及不会如（b）那样一对顶点之间存在多条边。
图
一个图G=（V,E）由一个顶点集V以及一个边集E组成。算法中通常会出现如下几种图：
无向图
顶点（u,v）之间的关系模型不需要考虑关系的方向如何。在处理对称信息时，这种图非常有用。例如，汽车可以在A镇和B镇之间的路上双向行驶。
有向图
顶点（u,v）之间的关系和顶点（v,u）之间的关系不同，后者或许不存在。例如，一个提供驾驶信息的程序必须存储单线道路的信息，以避免给出错误的方向。
有权图
顶点（u,v）之间的关系是有权重的。可以是数值的也可以是非数值的。例如，在A镇和B镇之间的道路有公里数，当然也包含了驾驶时间这个信息。
超图
在顶点（u,v）之间可能存在多种关系，本章我们将讨论限定在简单图上。
如果图中任意两点之间都存在一条边，那么这个图是连通图。一个有向有权图的定义为：一个非空顶点集合{v0，……，vn-1}，一个有向的边集合，每对顶点之间只有一条边，以及每条边上都有一个正权值。在很多应用中，这个权值被认为是距离或者开销。对某些应用来说，我们希望能够放宽权值必须为正的限制（例如，负值可以反映利润情况），但是我们必须高度关注这样做的后果。
考虑图6-2的有向有权图，它由6个顶点4条边组成。存储这个图有两个标准的数据结构：它们都显式地存储了权值，隐式表示了边的方向。一种数据结构叫邻接表，如图6-3所示，在这个数据结构中每一个顶点vi维护一个顶点的链表，链表中的每一个元素存储有vi到邻接节点的边权重。这种基础数据结构是顶点的一维数组。添加一条边时，需要额外的处理来保证不会出现重复的边。
图 6-2 有向有权图的例子 图 6-3 有向有权图的邻接表表示图6-4则是表明了如何用一个n阶的邻接矩阵来存储有向有权图，每个维度可以被索引。条目A[i][j]存储的是从vi到vj的边的权值；当A[i][j]=0时，顶点vi和顶点vj之间不存在边。使用邻接矩阵表示法，添加一条边只需要常数时间。
图 6-4 有向有权图的邻接矩阵表示我们也可以使用邻接表和邻接矩阵来存储无向图。看看图6-5的无向图，我们使用＜v0，v1，……，vk-1＞来描述一条有k个顶点的路。这条路遍历了k-1条边；一个有向图的路径是由同一方向的边组成。在图6-5中，路径＜v3，v1，v5，v4＞是有效的。环是一个多次包含了同一个顶点的路径。一个环通常用其最小形式表示。在图6-5中，在路＜v3,v1,v5,v4,v2,v1,v5,v4,v2＞中存在一个环，这个环可以用＜v1,v5,v4,v2,v1＞来表示。注意图6-2的有向有权图，存在一个环＜v3，v5，v3＞。
图 6-5 无向图样例当使用邻接表来存储无向图时，同一条边（u,v）在邻接表中出现了两次，一次是在u的邻接节点链表，一次是在v的邻接节点链表。因此，相比同样数目的顶点和边的有向图，无向图在邻接表中存储所需要的存储空间是前者的两倍。当使用邻接矩阵来存储无向图时，你必须保证条目A[i][j]=A[j][i]；不需要任何的额外存储空间。