定义

一个图（graph）G = （V，E）是由顶点（vertex）集V和边（edge）集E组成。

每一条边就是一个点对（v，w），其中v，w是属于V的，有时也把边称为弧（arc）。

如果点对是有序的，那么图就叫做是有向的（directed）。有向的图也叫做有向图（digraph）。

顶点v和w邻接（adjacent）当且仅当（v，w）属于E。

在一个具有边（v，w）从而具有边（w，v）的无向图中，w和v邻接且v也和w邻接。

有时还具有第三种成分，称作权（weight）或值（cost)。

图中的一条路径（path）是一个顶点序列w1，w2，w3，...，使得（wi, wi+1)属于E，1<= i < N。这样一条路径的长（length）是该路径上的边数，它等于N-1。

从一个顶点到它自身可以看成一条路径；如果路径不包含边，那么路径的长为0。

如果图包含一条从一个顶点到它自身的边（v，v)，那么路径v，v有时候也叫一个环（loop)。

一条简单路径是这样一条路径，其上的所有顶点都是互异的，但第一个顶点和最后一个顶点可能相同。

有向图的圈（cycle）是满足w1=wN且长至少为1的一条路径；如果该路径是简单路径，那么这个圈就是简单圈。对于无向图，我们要求边是互异的。这是因为在无向图中的路径u，v，不应该认为是圈，因为（u，v）和（v，u）是同一条边。但是在有向图中，他们就是两条不同的边，因此称它们为圈是有定义的。如果一个有向图没有圈，则称其为无圈的（acyclic）。一个有向无圈图有时也简称为DAG。

如果在一个无向图中从一个顶点到每个其他的顶点都存在一条路径，则称该无向图是连通的（connected）。

具有这样性质的有向图称为强连通的（strongly connected）。

如果一个有向图不是强连通的，但是它的基础图（underlying graph），即其弧上去掉方向所形成的图，是连通的，那么该有向图成为弱连通的（weakly connected）。

完全图（complete graph）是其每对顶点间都存在一条边的图。

表示

现在我们假设可以从1开始对顶点编号。下图所表示的图含有7个顶点和12条边。

表示图的一种简单的方法是使用一个二维矩阵，称为邻接矩阵（adjacency matrix）表示法。对于每条边（u，v），我们置A[u][v] = 1，否则，数组的元素就是0。如果边有一个权，那么我们可以设置A[u][v]等于该权，而使用一个很大或者很小的权作为标记表示不存在边。

虽然这么表示的优点是非常简单，但如果边不是很多，那么这种表示的代价就太大了。若图是稠密的（dense），则邻接矩阵是合适的表示方法。

如果图不是稠密的，换句话说就是图是稀疏的（sparse），则更好的解决方法是使用邻接表（adjacency list）。对每一个顶点，我们使用一个表存放所有邻接的顶点。如下图表示，如果边有权，那么这个附加的信息也可以存储在单元中。

邻接表是表示图的标准方法。无向图可以类似的表示。在图论算法中通常需要找出与某个给定顶点v邻接的所有的顶点。而这可以通过简单地扫描相应的邻接表来完成。

在大部分实际应用中，顶点都有名字而不是数字，这些名字在编译时是未知的。由于我们不能通过未知名字为一个数组做索引，因此我们必须提供从名字到数字的映射。完成这项工作最容易的方法是使用散列表。