4.2 有向图与无向图

图（graph）是由顶点集合和顶点间的二元关系集合（即边的集合或弧的集合）组成的数据结构，通常可以用G（V，E）来表示。其中，顶点集合（vertex set）和边的集合（edge set）分别用V（G）和E（G）表示。V（G）中的元素称为顶点（vertex），用u、v等符号表示；顶点个数称为图的阶（order），通常用n表示。E（G）中的元素称为边（edge），用e等符号表示；边的个数称为图的边数（size），通常用m表示。例如，图4-1（a）所示的图可以表示为G1(V，E)。其中，顶点集合V(G1)={1，2，3，4，5，6}，集合中的元素为顶点，用序号代表，在其他图中，顶点集合中的元素也可以是其他标识顶点的符号，如字母A、B、C等；边的集合为

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）是同一条的边。如果图中所有的边都没有方向性，则这种图称为无向图（undirected graph）。

图4-1（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的有向边（directed edge），其中，u是这条有向边的起始顶点（start vertex），简称起点，v是这条有向边的终止顶点（end vertex），简称终点，这条边有特定的方向，由u指向v，因此，〈u，v〉与〈v，u〉是两条不同的边。例如，在图4-1（b）所示的有向图G2中，〈2，5〉和〈5，2〉是两条不同的边。如果图中所有的边都是有方向性的，则这种图称为有向图（directed graph）。