1.1.1 图的基本类型

1.有向图和无向图

如果图中的边存在方向性，则称这样的边为有向边eij=<vi，vj>，其中vi是这条有向边的起点，vj是这条有向边的终点，包含有向边的图称为有向图，如图1-2所示。与有向图相对应的是无向图，无向图中的边都是无向边，我们可以认为无向边是对称的，同时包含两个方向：eij=<vi，vj>=<vj，vi>=eji。

图1-2 有向图

2.非加权图与加权图

如果图里的每条边都有一个实数与之对应，我们称这样的图为加权图，如图1-3所示，该实数称为对应边上的权重。在实际场景中，权重可以代表两地之间的路程或运输成本。一般情况下，我们习惯把权重抽象成两个顶点之间的连接强度。与之相反的是非加权图，我们可以认为非加权图各边上的权重是一样的。

图1-3 加权图

3.连通图与非连通图

如果图中存在孤立的顶点，没有任何边与之相连，这样的图被称为非连通图，如图1-4所示。相反，不存在孤立顶点的图称为连通图。

4.二部图

二部图是一类特殊的图。我们将G中的顶点集合V拆分成两个子集A和B，如果对于图中的任意一条边eij均有vi∈A，vj∈B或者vi∈B，vj∈A，则称图G为二部图，如图1-5所示。二部图是一种十分常见的图数据对象，描述了两类对象之间的交互关系，比如：用户与商品、作者与论文。

图1-4 非连通图

图1-5 二部图