1. 有向图与无向图
图（graph）是由顶点集合和顶点间的二元关系集合（即边的集合或弧的集合）组成的数据结构，通常可以用 G(V, E)来表示。其中顶点集合（vertext set）和边的集合（edge set）分别用 V(G)和 E(G)表示。
例如，图(a)所示的图可以表示为 G1(V, E)。其中顶点集合 V(G1) = { 1, 2, 3, 4, 5, 6 }，集合中的元素为顶点（用序号代表）；边的集合为：E(G1) = { (1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (4, 5) }。在上述边的集合中，每个元素(u, v)为一对顶点构成的无序对（用圆括号括起来），表示与顶点u 和 v 相关联的一条无向边（undirected edge），这条边没有特定的方向，因此(u, v)与(v, u)是同一条的边。如果图中所有的边都没有方向性，这种图称为无向图。
图(b)所示的图可以表示为 G2(V, E)，其中顶点集合 V(G2) = { 1, 2, 3, 4, 5, 6, 7 }，集合中的元素也为顶点的序号；边的集合为：E(G2) = { <1, 2>, <2, 3>, <2, 5>, <2, 6>, <3, 5>, <4, 3>, <5, 2>, <5, 4>, <6, 7> }。在上述边的集合中，每个元素<u, v>为一对顶点构成的有序对（用尖括号括起来），表示从顶点 u 到顶点 v 的有向边， 其中 u 是这条有向边的起始顶点，v 是这条有向边的终止顶点，这条边有特定的方向，由 u 指向 v，因此<u, v>与<v, u>是两条不同的边。例如在图 G2 中， <2, 5>和<5, 2>就是两条不同的边。如果图中所有的边都是有方向性的，这种图称为有向图。
如果一个图中某些边具有方向性， 而其他边没有方向性， 这种图可以称为混合图。
2. 完全图、稀疏图、稠密图
许多图论算法的复杂度都与图中顶点个数 n 或边的数目 m 有关，甚至 m 与 n×(n-1)之间的相对关系也会影响图论算法的选择。
完全图：如果无向图中任何一对顶点之间都有一条边，这种无向图称为完全图。在完全图中，阶数和边数存在关系式： m = n×(n-1)/2。
有向完全图：如果有向图中任何一对顶点 u 和 v，都存在<u, v>和<v, u>两条有向边，这种有向图称为有向完全图。
稀疏图：边或弧的数目相对较少（远小于 n×(n-1)）的图称为稀疏图。
稠密图：边或弧的数目相对较多的图（接近于完全图或有向完全图）称为稠密图。
3. 子图与生成树
子图：设有两个图 G(V, E)和 G'(V', E')，如果 V'⊆ V，且 E'⊆ E，则称图 G'是图 G 的子图。
生成树：一个无向连通图的生成树是它的包含所有顶点的极小连通子图，这里所谓的极小就是边的数目极小。如果图中有 n 个顶点，则生成树有 n-1 条边。一个无向连通图可能有多个生成树。
4. 路径
若从顶点 vi 出发，沿着一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点 vj，则称顶点序列(vi, vp1, vp2,…, vpm, vj)为从顶点 vi 到顶点 vj 的一条路径（path，或称为通路），其中(vi, vp1), (vp1, vp2), …, (vpm, vj)为图 G 中的边。如果 G 是有向图，则<vi, vp1>, <vp1, vp2>, …, <vpm, vj>为图G 中的有向边。
路径长度：路径中边的数目通常称为路径的长度。
简单路径：若路径上各顶点 vi, vp1, vp2,…, vpm, vj 均互相不重复，则这样的路径称为简单路径。
回路：若路径上第一个顶点 vi 与最后一个顶点 vj 重合，则称这样的路径为回路。
简单回路：除第一个和最后一个顶点外，没有顶点重复的回路称为简单回路。
5. 连通性
连通性： 在无向图中，若从顶点 u 到 v 有路径，则称顶点 u 和 v是连通的。
连通图： 如果无向图中任意一对顶点都是连通的，则称此图是连通图。
非连通图： 如果一个无向图不是连通图，则称为非连通图。
连通分量： 如果一个无向图不是连通的，则其极大连通子图称为连通分量，这里所谓的极大是指子图中包含的顶点个数极大。 如图所示的无向图也是非连通图。其中顶点 1, 2, 3 和 5 构成一个连通分量，顶点 4, 6, 7 和 8 构成另一个连通分量。
强连通图： 在有向图中，若对每一对顶点 u 和 v，既存在从 u 到 v 的路径，也存在从 v 到 u 的路径，则称此有向图为强连通图。例如，如图所示的有向图就是强连通图 。
强连通分量：对于非强连通图， 其极大强连通子图称为其强连通分量。
6. 权值、有向网与无向网
权值：某些图的边具有与它相关的数，称为权值。这些权值可以表示从一个顶点到另一个顶点的距离、花费的代价、所需的时间等。
加权图：如果一个图，其所有边都具有权值，则称为加权图，或者称为网络。
有向网、无向网：根据网络中的边是否具有方向性，又可以分为有向网和无向网。
如图所示的无向网可表示为 G1(V, E)，其中顶点集合 V(G1) = { 1, 2, 3, 4, 5, 6, 7 }；边的集合为：E(G1) = { (1, 2, 28), (1, 6, 10), (2, 3, 16), (2, 7, 14), (3, 4, 12), (4, 5, 22), (4, 7, 18), (5, 6, 25), (5, 7, 24) }。在边的集合中，每个元素的第 3 个分量表示该边的权值。有向网可以表示为 G2(V, E)，其中顶点集合 V(G1) = { 1, 2, 3, 4, 5, 6, 7 }；边的集合为：E(G2) = { <1, 2, 12>, <2, 4, 85>, <3, 2, 43>, <4, 3, 65>, <5, 1, 58>,<5, 2, 90>, <5, 6, 19>, <5, 7, 70>, <6, 4, 24>, <7, 6, 50> }。 每个元素的第 3 个分量也表示该边的权值。
