一个图（graph）G=（V，E）由顶点（vertex）的集V和边（edge）的集E组成。每一条边就是一副点对（v，w），其中v、w ϵ V。有时也把边称做弧（arc）。
有向（directed）：如果点对是有序的，那么图就是有向的。
有向图（digraph）：有向的图有时也叫有向图。路径u，v，u可以被认为是圈，因为（u，v）和（v，u）不是同一条边。
无向图：与有向图相对，我们要求边是互异的。这些要求的根据在于无向图中的路径u，v，u不应该被认为是圈，因为（u，v）和（v，u）是同一条边。
邻接（adjacent）：顶点w和v邻接当且仅当（v，w）ϵ E。在一个具有边（v，w）从而具有边（w，v）的无向图中，w和v邻接且v也和w邻接。
权（weight）或值（cost）：边具有的第三种成分。
路径（path）：图中的路径是一个顶点序列w1，w2，w3，…，wN使得（wi，wi+1）ϵ E，1 ≤ i < N。
路径的长（length）：路径上的边数。从一个顶点到它自身可以看成是一条路径，如果路径不包含边，那么路径的长为0。
环（loop）：如果图含有一条从一个顶点到它自身的边（v，v），那么路径v，v有时也叫做环。
简单路径：一条简单路径是这样一条路径，其上的所有顶点都是互异的，但第一个顶点和最后一个顶点可能相同。
圈（cycle）：有向图中的圈是满足w1=wN且长至少为1的一条路径。
简单圈：满足圈的定义，并且如果该路径是简单路径，那么这个圈就是简单圈。
无圈的（acyclic）：如果一个有向图没有圈，则称其为无圈的。一个有向无圈图有时也简称为DAG。
基础图（underlying graph）：图中其弧去掉方向所形成的图。
连通的（connected）：如果在一个无向图中从每一个顶点到每个其它顶点都存在一条路径，则称该无向图是连通的。
强连通的（strongly connected）：先是连通的，然后具有这样性质的有向图称其为强连通的。
弱连通的（weakly connected）：如果一个有向图不是强连通的，但是它的基础图，即其弧上去掉方向所形成的图，是连通的，那么该有向图称为是弱连通的。
完全图（complete graph）：完全图是其每一对顶点间都存在一条边的图。
图的表示
一个有向图：
图中有7个顶点和12条边。
表示图的一种简单的方法是使用一个二维数组，称为邻接矩阵（adjacent matrix）表示法。对于每条边（u，v），置A[u][v]等于true；否则，数组的元素就是false。如果边有一个权，那么可以置A[u][v]等于该权，而使用一个很大或者很小的权作为标记表示不存在的边。
虽然这样表示的优点是非常简单的，但是，它的空间需求则为θ(|V|2)，如果图的边不是很多，那么这种表示的代价就太大了。若图是稠密（dense）的：|E|=θ(|V|2)，则邻接矩阵是合适的表示方法。
如果图不是稠密的，换句话说，如果图是稀疏的（sparse），则更好的解决方法是使用邻接表（adjacency）表示。对每一个顶点，我们使用一个表存放所有邻接的顶点。此时的空间需求为O(|E|+|V|),它相对于图的大小而言是线性的。如果边有权，那么这个附加信息也可以存储在邻接表中。
图的邻接表表示法：
邻接表是表示图的标准方法。无向图可以类似地表示，每条边（u，v）出现在两个表中，因此空间的使用基本上是双倍的。在图论算法中通常需要找出与某个给定顶点v邻接的所有的顶点。而这可以通过简单地扫描相应的邻接表来完成，所用的时间与这些找到的顶点的个数成正比。
有几种方法保留邻接表。首先注意到，这些邻接表本身可以被保存在任何种类的List，即ArrayList或LinkedList中。然而，对于非常稀疏的图，当使用ArrayList时程序员可能需要从一个比默认容量更小的容量开始ArrayList。否则可能造成明显的空间浪费。
因为关键在于能够迅速得到与任一顶点邻接的那些顶点的表，所以两个基本的选择是，或者使用一个映射，在这个映射下，关键字就是那些顶点而它们的值就是那些邻接表，或者把每一个邻接表作为Vetex类的数据成员保存起来。这第1个选择论证要简单，而第2个选择可能会更快，因为它避免了在映射下的重复查找。
在第2种情形，如果顶点是一个String，那么可以使用映射，在映射下，关键字是顶点名而关键字的值则是一个Vertex，并且每一个Vertex对象拥有一个邻接顶点表，或许还有原始的String串名。