定义

一个图(graph)G=(V, E)由顶点(vertex)的集V和边(edge)的的集E组成。

邻接：顶点w和顶点v邻接当且仅当$(v, w) \in E$。
度：在无向图中，顶点的度是邻接到该顶点的边的数目。在有向图中，入度是指以该顶点为终点的边的数目；出度是指以该顶点为起点的边的数目。
路径：如果顶点w到顶点v之间存在一个顶点序列，则表示w到v的一条路径。
简单路径：路径上所有的顶点都是互异的，但第一个顶点和最后一个顶点可能相同。
路径的长度：路径中边的数量。
回路：路径的第一个顶点和最后一个顶点相同。
简单回路：路径的第一个顶点和最后一个顶点相同，但是其他各顶点不重复。
连通图：在无向图中，任意两个顶点之间存在一条无向路径，则该无向图为连通图。在有向图中，任意两个顶点之间存在一条有向路径，则该有向图为强连通图。如果一个有向图不是强连通的，但是它的基础图，即去边上去掉方向所形成的图，是连通的，则该有向图为弱连通图。
完全图：图中每一对顶点都存在一条边。
连通分量：非连通图中的各个连通子图称为该图的连通分量。
权：图中边的权值。

图的存储结构

邻接矩阵是指用矩阵来表示图，采用矩阵来描述途中顶点之间的关系。
邻接矩阵定义为：
$$ A[i][j]= \begin{cases} 1, & \text {顶点i和顶点j之间有边存在} \\ 0, & \text {顶点i和顶点j之间没有边存在} \end{cases} $$

邻接表示图的一种链式存储表示方法，对每个顶点，使用一个表存放所有邻接的顶点。缺点是不方便判断两个顶点之间是否有边，但是相对邻接矩阵来说更省空间。

有向图的邻接表易于计算顶点的出度，逆邻接表易于计算顶点的入度。