本文以尽可能简明扼要的语言介绍在研究图算法时会遇到的图的相关概念。
什么是图
实际应用中的许多计算问题，不仅涉及到问题中的元素，也涉及到这些元素之间的关系。比如，如何表示一个生态系统中物种的竞争关系？又如，在我们握有一个城市的一份 街道地图的情况下，我们怎样才能找到从城市中一点到另一点的最短路径？这时，我们需要用一种被称作图的数学模型对这些问题进行描述。图是由顶点和连接顶点的边组成的离散结构。简单地说，图就是由若干给定的点（称为顶点）以及连接两点的线（称为线）所构成的图形。我们通常用顶点表示问题中涉及的事物，用边表示这些事物之间的关系。
图是图论的基本研究对象，而图论是组合数学的一个重要分支。自欧拉于1735年发表柯尼斯堡七桥问题的研究成果以来，图论已经得到了数百年的研究。而在计算机科学领域中，大量的算法涉及到图及其衍生结构的使用。
图的基本概念
简单图，多重图与一般图
我们给出图的定义：
一个图\(G = (V, E)\)由顶点的非空集\(V\)和边的集合\(E\)构成，每条边 有一个或两个顶点与它相连，这样的顶点称为边的端点。边连接它的端点。 顶点的个数称为图的阶。
容易注意到这个定义使得图具有两个特殊的性质（由集合的互异性）：
- 图不允许出现多重边，也即没有两条不同的边连接一对相同的顶点。
- 图不允许出现自环， 也即没有任何一条边仅连接一个定点自身。
但是实际问题中很少有情况完全符合这两个条件。考虑下面的两个例子：城市中两个地点之间可能有多条路相连；知乎上某个问题的提问者可以自问自答。参考图的定义，我们将无法为上述两种情况（城市不同地点及其连接道路之间的关系、知乎上某个问题的提问者与回答者之间的关系）建立数学模型。因此，我们有必要扩展图的定义使之适合的情况更为广泛。我们给出新的定义：
有多重边连接同一对顶点（但不存在自环）的图称为多重图。如图中的红色边。
存在自环（也可能存在多重边）的图称为一般图（伪图）。如图中的蓝色边。
我们将符合图的原始定义的图称作简单图。
有向图与无向图
到现在为止，我们提到的图的边都是不带有方向的。但是有些情况下我们可能需要为边赋予方向，例如：生态系统中的食物链，以及不同数据中心之间的数据传输。为此，我们需要定义有向图的概念：
一个有向图\((V,E)\)由一个非空顶点集\(V\)和一个有向边集\(E\)组成。每条有向边与一个顶点有序对相关联。与有序对\((u, v)\)相关联的有向边开始于\(u\)，结束于\(v\)。
相应地，我们将边不带有方向的图称为无向图。与之前的多重图和一般图的定义类似，如果在有向图的\((u, v)\)之间存在\(m\)条方向相同的有向边（或者自环）时，称作\((u, v)\)间具有多重有向边，此时的有向图称为有向多重图,将\((u, v)\)称作一条多重度为\(m\)的边。
如果在一个图中既有有向边又有无向边，则将这个图称作混合图。
图的相关术语
顶点与边的关系
当两个顶点通过一条边相连时，我们称这两个点邻接，称连接这两个点的边关联这两个顶点。顶点\(v\)的度是关联于其的边的总数，记为\(deg(v)\)。度分为入度和出度，分别是以某个顶点作为终点的边的数目和以某个顶点作为起点的边的数目。
容易注意到关于顶点的度有如下结论：
- 自环对一个顶点的度的贡献是2。
- 握手定理：一个具有m条边的一般图的边的条数是其所有顶点度数之和的一半。
- 无向图有偶数个度为奇数的顶点。
子图与连通图
子图
一个一般图的所有边（以及其关联的所有顶点）的集合的一个子集称为这个图的一个一般子图。如果子图的顶点集关联的所有边也是原图中对应顶点集关联的所有边，则将这个子图称为原图的一般导出子图。如果子图的顶点集即为原图的顶点集，则将这个子图称作原图的一般生成子图。
连通图
在图中，路径是由边顺序连接的一系列顶点。
简单路径是一条没有重复顶点的路径。环是一条至少含有一条边且起点与终点相同的路径。简单环是一条不含有重复顶点（除去起点与终点）和边的环。路径或环的长度为其中所包含的边数。
如果从任意一个顶点都存在一条路径到达另一个任意顶点，我们称这个图是连通图。
树
树是一种特殊的图，指的是一个没有环的连通无向图。
树是图的一种特例，但与图不尽相同，可以用来为另外许多问题建模，比如：有机化合物的结构式是一棵树，族谱中的家族树也是树的例子。树同时还是一种数据结构，在算法领域尤其有用。
树的相关术语
树的大多数术语与图相同，除了一些树特有的概念：
根是一个特殊选定的节点，类似于自然界中的树，树从根节点开始“分枝”。如图中的节点0。
将树中度为1的节点称作叶。如图中以绿色标出的节点。
在一棵树中选定了根节点之后，就可以引入层的概念。层是每个点离根的距离，将一棵树的最大层数称作树的深度。
在树中选定一个节点，则这个节点的上一层节点称作这个节点的父节点，下一层节点称作这个节点的子节点，同一层的其他节点称作这个节点的兄弟节点。
森林是互不相连的树组成的集合。