额滴笔记

Appearance

图的概念 ​

图的定义 ​

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

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

图的分类 ​

有向图（Digraph） ​
  • 向：方向
  • 有方向的图称为有向图。
  • 有向图中的方向性线条称为：弧。
无向图（Undigraph） ​
  • 没有方向的图称为无向图。
  • 无向图中的线条称为：边。

示例关系集：

Rx{⟨v1,v3⟩,⟨v2,v1⟩,…}R_x \{ \langle v_1, v_3 \rangle, \langle v_2, v_1 \rangle, \ldots \}

带权图（网） ​

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

图示：

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

图的特点名词 ​

顶点的度 ​
  • 定义：与顶点关联的边或弧的数量。
    • 有向图中分为：
      • 入度：指向该顶点的弧的数量。
      • 出度：从该顶点出发的弧的数量。
路径 ​
  • 定义：从一个顶点到达另一个顶点的访问序列。
    • 直接路径：两个顶点间仅有一条边/弧相连。
    • 间接路径：需通过其他顶点中转的多条边/弧。
连通图 ​
  • 定义：
    • 无向图：若任意两顶点间存在路径，则为连通图。
    • 有向图：若任意两顶点间存在双向路径，则为强连通图。

图的存储方式 ​

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

数组表示法（邻接矩阵） ​

实现方式：

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

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

主别0直达直达直达直达直达
不跳不能不能直达不能直达
不跳不能不能直达不能直达
直达不能不能直达不能直达
不跳不能不能直达不能直达

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

邻接矩阵增加关系 ​

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

  1. 获取 ( v_i ) 和 ( v_j ) 在顶点数组中的下标。
  2. 若任一顶点不存在，则操作终止。
  3. 将邻接矩阵中 ( v_i ) 行、( v_j ) 列的元素设为 1（或权值 $$(\omega)$$。
邻接矩阵的优缺点 ​
  • 优势：存储/设计简单。
  • 劣势：空间浪费（稀疏图），遍历出度效率低。

邻接表 ​

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

  1. 关系节点类型：
cpp
struct Relation_t  
{  
    int index;          // 出度关系的终点下标  
    Relation_t *next;   // 下一条出度关系指针  
    Relation_t(int id) : index(id), next(nullptr) {}  
};
  1. 顶点类型：
cpp
struct Vertex_t  
{  
    std::string data;   // 顶点数据（如城市名）  
    Relation_t *rs;     // 出度关系集合（链表头指针）  
};
  1. 图类型（两种实现）：
    • 方式1：顶点集为结构体数组
      cpp
      class Graph  
{  
private:  
    Vertex_t vs[100]; // 顶点集（含数据与关系链表）  
};
    • 方式2：分离顶点数据与关系
      cpp
      class Graph  
{  
private:  
    std::string vs[100];  // 顶点数据集  
    Relation_t rs[100];   // 关系集（每个顶点的链表头）  
};

邻接表的优缺点：

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

逆邻接表 ​

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

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

作业要求：

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

十字链表 ​

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

  • 顶点类型扩展：
    cpp
    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. 终止条件：
    • 所有顶点均被访问完毕。

示例顶点：

  • ( V_0 )：北京
  • 邻接顶点：上海、长沙、广州、香港、澳门

广度优先搜索算法（BFS） ​

步骤：

  1. 初始化：标记所有顶点为未访问状态。
  2. 从某个顶点 ( V_0 ) 出发：
    • 访问 ( V_0 ) 并标记为已访问。
    • 广度优先：依次访问 ( V_0 ) 的所有邻接顶点（如上海、长沙）。
  3. 分层扩展：
    • 从已访问的邻接顶点（如上海）出发，访问其邻接顶点（如广州）。
    • 从已访问的邻接顶点（如长沙）出发，访问其邻接顶点（如香港）。
  4. 终止条件：
    • 所有顶点均被访问完毕。

作业要求：

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

最短路径问题 ​

定义：

  • 在图中找到两个顶点之间的最短路径（路径总权值最小）。
  • 权值：边/弧的长度、成本、时间等（由应用场景定义）。
  • 应用领域：计算机科学、运筹学、网络理论等。

关键点：

  • 两个顶点间路径不唯一，需找总权值最小的路径。

经典算法 ​

  1. 迪杰斯特拉算法（Dijkstra）
  2. 弗洛伊德算法（Floyd）

迪杰斯特拉算法（Dijkstra） ​

目标：解决从源点 ( v ) 出发，到图中其他所有顶点的最短路径问题。

辅助向量 ​

  1. 向量 ( S[n] )：

    • ( S[i] = \text{true} )$$：源点到顶点 \( i \) 的最短路径已找到。
    • 初始化：
      • ( S[v] = \text{true} )$$（源点自身）。

  2. 向量 $$( \text{dist}[n] )$$：

    • 存储源点到各顶点的当前最短路径权值。
    • 初始化：
      • 若源点 ( v ) 直接可达顶点 ( i )：$$( \text{dist}[i] = \omega(v, i) )$$。
      • 若不可达：$$( \text{dist}[i] = +\infty )$$。
算法步骤 ​

  1. 找当前最优路径：

    • 从 $$( \text{dist} )$$ 中选未确定最短路径$$( S[w] = \text{false} )$$的最小值：

      dist[u]=min{dist[w]∣w∈[0,n−1],S[w]=false}\text{dist}[u] = \min \{ \text{dist}[w] \mid w \in [0, n-1], \, S[w] = \text{false} \}

    • ( u ) 为当前最优顶点下标。

  2. 更新其他路径：

    • 对所有未确定最短路径的顶点 $$( w )( S[w] = \text{false} )$$：
      • 若 $$( \text{dist}[u] + \omega(u, w) < \text{dist}[w] )$$，则更新：

        dist[w]=dist[u]+ω(u,w)\text{dist}[w] = \text{dist}[u] + \omega(u, w)

  3. 标记最优路径：

    • 设 $$( S[u] = \text{true} )$$。

  4. 重复迭代：

    • 重复步骤 1-3，直到所有顶点 $$( S[i] = \text{true} )$$。

算法依赖：路径长度按递增次序产生（贪心策略）。

作业要求：

  • 实现迪杰斯特拉算法代码，并调试修复潜在 BUG。

总结：

  • Dijkstra 适用场景：单源最短路径（无负权边）。
  • Floyd 适用场景：多源最短路径（可处理负权边）。

知识如风，常伴吾身

Copyright © 2023-2025 Kgumo