图的概念

图的定义

图（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 )）。

邻接矩阵的优缺点

• 优势：存储/设计简单。
• 劣势：空间浪费（稀疏图），遍历出度效率低。

---

邻接表

定义：通过数组+链表的形式存储顶点的出度关系。
实现方式：

1. 关系节点类型：

struct Relation_t  
{  
    int index;          // 出度关系的终点下标  
    Relation_t *next;   // 下一条出度关系指针  
    Relation_t(int id) : index(id), next(nullptr) {}  
};

2. 顶点类型：

struct Vertex_t  
{  
    std::string data;   // 顶点数据（如城市名）  
    Relation_t *rs;     // 出度关系集合（链表头指针）  
};

3. 图类型（两种实现）：
   • 方式1：顶点集为结构体数组

     class Graph  
     {  
     private:  
         Vertex_t vs[100]; // 顶点集（含数据与关系链表）  
     };

   • 方式2：分离顶点数据与关系

     class Graph  
     {  
     private:  
         std::string vs[100];  // 顶点数据集  
         Relation_t rs[100];   // 关系集（每个顶点的链表头）  
     };

邻接表的优缺点：

• 优势：节省空间（仅存有效关系），遍历出度高效。
• 劣势：操作复杂度高（需维护链表）。

---

逆邻接表

定义：通过数组+链表的形式存储顶点的入度关系（与邻接表方向相反）。
实现：

• 将邻接表中的"出度终点下标"替换为"入度起点下标"。
• 顶点类型中 rs 指向入度关系链表。

作业要求：

• 采用面向过程的方式实现逆邻接表（非面向对象）。

---

十字链表

定义：邻接表 + 逆邻接表的结合体，同时存储顶点的入度和出度关系。
实现：

• 顶点类型扩展：

  struct Vertex_t  
  {  
      std::string data;  
      Relation_t *out_rs;  // 出度关系链表头  
      Relation_t *in_rs;   // 入度关系链表头  
  };

• 增加关系时：
  • 同时更新起始顶点的出度链表和目标顶点的入度链表。

优势：

• 可高效遍历任意顶点的入度和出度关系。

作业要求：

• 实现十字链表的完整操作（关系增删、遍历入度/出度）。

---

图的遍历

定义：

• 图的遍历是树遍历的推广，按照特定规则访问图中各顶点一次且仅一次。
• 将网状结构按规则线性化。

遍历方式

1. 深度优先搜索算法（DFS）
2. 广度优先搜索算法（BFS）

注：两者均为现代人工智能（AI）的基础。

---

深度优先搜索算法（DFS）

步骤：

1. 初始化：标记所有顶点为未访问状态。
2. 从某个顶点 ( V_0 ) 出发：
   • 访问 ( V_0 ) 并标记为已访问。
   • 搜索 ( V_0 ) 的邻接顶点 ( V_i )。
3. 递归深入：
   • 以 ( V_i ) 为新起点，访问其未访问的邻接顶点。
   • 重复此过程（深度优先）。
4. 回溯机制：
   • 若当前顶点无未访问的邻接顶点，回溯到上一顶点。
   • 从上一顶点继续搜索未访问的邻接顶点。
5. 终止条件：
   • 所有顶点均被访问完毕。

---

广度优先搜索算法（BFS）

步骤：

1. 初始化：标记所有顶点为未访问状态。
2. 从某个顶点 ( V_0 ) 出发：
   • 访问 ( V_0 ) 并标记为已访问。
   • 广度优先：依次访问 ( V_0 ) 的所有邻接顶点。
3. 分层扩展：
   • 分别从已访问的邻接顶点出发，按广度优先策略访问它们的邻接顶点。
   • 类似树的层次遍历（按层推进）。
4. 终止条件：
   • 所有顶点均被访问完毕。

作业要求：

• 完成广度优先搜索算法的代码实现。

---

总结：

• DFS：沿路径深入到底再回溯，适合路径搜索。
• BFS：按层扩展访问，适合最短路径计算。