1.1 基本术语

提到“图”这个词，我们很自然就会联想到x轴、y轴等术语（见图1.1(a)）。从算法的角度来说，图也可以看作成对的对象之间的关系的表现形式（见图1.1(b)）。

图1.1　在算法中，图是一组对象以及每对对象之间的关系
（例如朋友关系）的表现形式

图具有两个组成部分：图所表示的对象集合以及每一对对象之间的关系。前者称为图的顶点或端点。每一对对象之间的关系可以看成是图的边。我们通常用V和E分别表示图的顶点集和边集，有时用表达式G=(V,E)表示图G具有顶点集V和边集E。

图分为两种类型，一种是有向图，另一种是无向图。这两种类型的图非常重要，具有极为普遍的应用，因此我们应该同时熟悉这两种图。在无向图中，每条边对应于一个无序的顶点对(v,w)，其中v和w是这条边的端点（图1.2(a)）。在无向图中，边(v,w)和边(w,v)没有区别。在有向图中，边(v,w)是个有序的顶点对，这条边的方向是从第1个顶点v（称为尾）到第2个顶点w（称为头），参见图1.2(b)。

图1.2　具有4个顶点和5条边的图（无向图的边和有向图的
边分别是无序的顶点对和有序的顶点对）