图的基本概念

定义

图 G由顶点集 V和边集 E组成，记为 G = 。其中 |V| 表示图 G 中顶点的个数，也称图 G 的阶；话说回来，|E| 表示图 G 中边的条数。

例子说明

有向与无向区别

无向图

若 E 是无向边****的有限集合，则 G 为无向图。边是顶点无序对，记为  或  因为 = 。可说 v 与 w 为邻接点，边 与 v、w 同时相关联。

KPI：判断一个给定集合是否能构成无向图？答案的观点是，只需确认每条边都以无序对出现即可！

G₂ =
V₂ = {A。B,C,D,E}
E₂ = {，}

示例：展示了一个典型无向结构。

有向图

若 E 是有向边****的有限集合，则 G 为有向图。弧是顶点有序对，记为  其中 v 称为弧尾，w 称为弧头。说起来，&neq。按理说，

KPI：在有向结构中。要留意箭头方向，错误理解方向会导致方法判定错误。

G₁ =
V₁ = {A,B,C,D,E}
E₁ = { ,。,,,,,<.E.C>}
上方示例中，“弧中没有箭头的一端对应的是弧尾”，有箭头的一端对应的是弧头。

简单与多重分类

简单图

• No parallel edges.
• No loops.

示例省略，可自行绘制以加深印象。

多重图

允许两个结点间出现多于一条边，而且允许自环。本章仅讨论简单结构，数据结构课程通常不涉及多重情形。若遇到多重情况，请先将其拆解成等价简单形式再分析。

度数与入出度概念

• 无向度 TD： 指依附于该结点 v 的所有未标记方向之总数，即该结点相连所有邻接关系之和。指代 “总度” )