图(Graph)是一种较线性表和树更为复杂的数据结构。在图形结构中，节点之间的关系可以是任意的，图中的任意两个元素之间都有可能相关。由此，图的应用也极为广泛，特别使近年来的迅速发展，已经渗入到诸如语言学，逻辑学，物理，化学，电讯工程，计算机科学以及数学的其他分支中。本文使用通俗的语言讲述一些有关图的基本概念。
顶点，有向图，无向图
记图1： G1 = （ V1， {A1} ）
有向无向图
顶点(Vertex)：图中的数据元素通常称作顶点
V:顶点的有穷非空集合
VR:两个顶点之间的关系集合
弧：若<v,w>属于
VR，则<v,w>表示v到w的一条弧(Arc)弧尾(Tail)：v为弧尾，或者称为初始点
弧头(Head)：w为虎头, 或者称为终端点
有向图：VR是单向的
无向图：VR是对称的，即若有<v,w>则必有<w,v>。则以无序对(v,w)代替两个有序对表示v和w 之间的一条边(Edge)
G1为有向图，G2为无向图
完全图，稀疏图，权，网，子图
记图中顶点数为n，边或弧的数目为e，不考虑顶点到自身的弧或边，有以下定义：
- 完全图：图中所有边或弧的数目已饱和。即在有向图中有
e=n(n-1)称为有向完全图,无向图中有e=n(n-1)/2称为无向完全图 - 稀疏图：有很少弧的图(如
e < nlogn) - 稠密图：与稀疏图相反，有相对较多的弧，但是不饱和
权：具有与图的边或弧相关的数。权可以表示从一个顶点到另一个顶点的距离和耗费
网：带权的图称为网
子图：一个图的所有顶点的集合与所有顶点之间关系的集合均被包含的另一个图中。
下图为G1，G2子图的一些例子：
G1,G2子图
邻接点，度
邻接点：两个有关系的顶点，或者称它们相关联
度(TD)：
- 再无向图中和顶点v相关联的边的数目，G2中
TD(V3)=3 - 有向图中，若有关系<v,w>则称v邻接到w，w邻接自v，弧<v,w>和顶点v,w相关联。以v为弧头的弧的数目称为v的入度ID(v)，以v为弧尾的弧的数目称为v的出度OD(v),而度为
TD(V)=ID(V)+OD(V)。如G1中的V1：TD(V1)=ID(V1)+OD(V1)=1+2=3
一般的：图的弧的数目等于所有顶点度的和的一半
路径，回路，简单路径，简单回路
- 路径：自从顶点v到w的路径是一个顶点序列，有向图的路径也是有向的
- 路径长度：路径上的弧或边的数目
- 回路(环)：第一个顶点与最后一个顶点相同的路径
- 简单路径：序列中顶点不重复出现的路径
- 简单回路(简单环)：除第一个顶点与最后一个顶点之外其余顶点不重复出现的回路
连通
无向图中：
- 连通：从顶点v到w有路径则v，w连通
- 连通图：图中任意两顶点都连通
- 连通分量：无向图中极大联通子图
如下图为G3与它的3个强连通分量：
G3与它的3个强连通分量
有向图中：
- 强连通图：对于每一对v,w从v到w与从w到v都存在路径
- 强连通分量：有向图中极大强连通子图
G1不是强连通图，但它有两个强连通分量如下图：
G1的两个强连通分量
生成树，生成森林
生成树：一个连通图的极小连通子图，含有图中全部顶点。构成一个含有n-1条边的图，如果在生成树上再添加一条边则必定构成一个环。
下图是G3的最大连通分量的一颗生成树：
G3的最大连通分量的一颗生成树
有向树：恰有一个顶点入度为0,其余顶点入度为1有向图
生成森林：含有图中全部顶点，但只有足以构成若干颗不相交的有向树的弧
下图是一个有向图及其生成森林：
一个有向图及其生成森林
关节点：若删去顶点v和v相关联的各边后，则将图分割成两个或以上连通分量的顶点。
重连通图：没有关节点的连通图称为重连通图。