图的概念

图的定义

图（graph）是非线性的数据结构，形式描述为：graph = (V, R)。
其中：

• V 是图中元素（称为顶点 Vertex）的集合，当 n=0 时，V 是空集。
• R 是图中顶点之间的关系集，$$( \langle v_i, v_j \rangle )$$ 表示顶点 ( v_i ) 与 ( v_j ) 之间是否存在路径（关系）。若 ( v_i ) 与 ( v_j ) 存在关系，则 $$( \langle v_i, v_j \rangle )$$ 属于 R。

---

图的分类

有向图（Digraph）

• 向：方向
• 有方向的图称为有向图。
• 有向图中的方向性线条称为：弧。

无向图（Undigraph）

• 没有方向的图称为无向图。
• 无向图中的线条称为：边。

示例关系集：

$R_x \{ \langle v_1, v_3 \rangle, \langle v_2, v_1 \rangle, \ldots \}$

---

带权图（网）

• 若在图的关系 ( \langle x_i, y_i \rangle ) 上附加一个值 ( w )，称 ( w ) 为弧或边上的权值。
• 带权的图称为：网（权值 ( w ) 的含义由应用场景定义，如顶点表示城市时 ( w ) 可表示距离）。

图示：

• 有向图：弧带方向（如 $$( v_1 \to v_2 )$$。
• 无向图：边无方向（如 $$( v_1 - v_2 )$$。

---

图的特点名词

顶点的度

• 定义：与顶点关联的边或弧的数量。
  • 有向图中分为：
    • 入度：指向该顶点的弧的数量。
    • 出度：从该顶点出发的弧的数量。

路径

• 定义：从一个顶点到达另一个顶点的访问序列。
  • 直接路径：两个顶点间仅有一条边/弧相连。
  • 间接路径：需通过其他顶点中转的多条边/弧。

连通图

• 定义：
  • 无向图：若任意两顶点间存在路径，则为连通图。
  • 有向图：若任意两顶点间存在双向路径，则为强连通图。

---

图的存储方式

数组表示法、邻接表、逆邻接表、十字链表等。

数组表示法（邻接矩阵）

实现方式：

• 用一维数组存储顶点集 V（如 V = {北京, 长沙, 上海, 广州, 香港, 澳门}）。
• 用二维数组（邻接矩阵）描述关系集 R：
  • 行表示起始顶点，列表示目标顶点。
  • 矩阵元素值：
    • 1（或权值 ( w )）：存在弧/边。
    • 0（或 ∞）：不存在弧/边。

示例邻接矩阵（顶点顺序：北京, 长沙, 上海, 广州, 香港, 澳门）：

主别	0	直达	直达	直达	直达	直达
东沙	不能	不能	不达	不能	不达	不达
下游	不能	不能	不能	不达	不达	不达
丁兰	不达	不能	不能	不达	不达	不达
咖啡	不能	不能	不达	不达	不达	不达
酒	不能	不能	不能	不达	不达	不达

注：表中"不能"表示无路径，"不达"表示不可达。

邻接矩阵增加关系

增加关系 $$( \langle v_i, v_j \rangle )$$ 的步骤：

1. 获取 ( v_i ) 和 ( v_j ) 在顶点数组中的下标。
2. 若任一顶点不存在，则操作终止。
3. 将邻接矩阵中 ( v_i ) 行、( v_j ) 列的元素设为 1（或权值 ( w )）。

---

作业

• 将邻接矩阵封装成一个类（实现顶点管理、关系增删、路径查询等功能）。