额滴笔记

图的概念

图的定义

图（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 )$$ 的步骤：

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

邻接矩阵的优缺点

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

邻接表

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

关系节点类型：

cpp

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

顶点类型：

cpp

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

图类型（两种实现）：

方式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;   // 入度关系链表头  
};

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

优势：

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

作业要求：

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

总结：

邻接矩阵：简单但空间效率低。
邻接表：高效存储出度关系。
逆邻接表：高效存储入度关系。
十字链表：综合入度与出度管理，操作复杂但查询全面。

图的概念 ​

图的定义 ​

图的分类 ​

有向图（Digraph） ​

无向图（Undigraph） ​

带权图（网） ​

图的特点名词 ​

顶点的度 ​

路径 ​

连通图 ​

图的存储方式 ​

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

邻接矩阵增加关系 ​

邻接矩阵的优缺点 ​

邻接表 ​

逆邻接表 ​

十字链表 ​