Bipartite Graph

二分图：所有顶点可以分为两个不相交集合U、V，两个集合大小不定 相等，但每条边都连接两个集合中各一顶点

• 可以证明：当且仅当图中不存在奇数长度回路时，为二分图

• 二分图中顶点可以可以染成两种颜色，使得每条边两头顶点颜色 不同

• 矩阵存储二分图时，因为U、V内部节点之间无边，大部分场景 只需要$|V| * |U|$的矩阵（对有序、加权适用）

• 性质

  • 二分图匹配意义：同类型（集合内部）之间没有连接

Augmenting-Path

（二分图）增益路径：对合法匹配M，简单路径两端连接V、U中 的自由顶点，路径中边交替出现在$E-M, M$中，称M的增益路径

• 增益路径长度总为奇数，为M中匹配两倍+1

• 则路径中奇数边组成新的匹配，比M多一条边

增益路径-最大匹配证明

当且仅当G中不存在M增益路径时，M为G最大匹配

必要性

• 若M存在增益路径，则可以扩展M得到更多匹配，M不是最大匹配

充分性

• 若存在M无增益路径，但不为最大匹配，设$M{}$是G中的最大 匹配，则$M{}$中边至少比M中边数量大1，有 $|M^{}| > |M|, |M^{} - M| > |M - M^{*}|$

• 则两者对称差集为 $M \bigoplus M^{} = (M - M^{}) \cup (M^{*} - M)$

• 设$G^{‘} \subseteq G$为二者差集中所有边、点，根据匹配 定义，$G^{‘}$中任何单个点和$M, M^{*}$相连接不会超过 一条边

• 则$G^{‘}$中顶点连通度不大于2，其中连通分量为

  • 偶数长度回路，其中边交替属于 $|M^{} - M|, |M - M^{}|$，在两者中数量相同

    • 若不交替，则说明连续两条边在同个匹配中，有交点， 和匹配定义冲突

    • 若不为偶数长度，同样的首、尾两条边在同一匹配中， 和匹配定义冲突

  • 交替路径（无环）

    • 因为$|M^{} - M| > |M - M^{}|$，所以$G^{*}$中 不可能仅有回路

    • 所以至少存在一条具有交替边路径，起点终点都是 $M^{*} - M$同一条边（如单边路径），M具有增益路径 ，矛盾

• 最大匹配求解匈牙利算法实现详见graph

Konig Theorem

Konig定理：二分图中最大匹配数|M| = 最小点覆盖数|C|

• 已经通过匈牙利算法求出最大匹配M

• 从集合V中每个未被匹配点开始，走一条类似增益路径 的交替路径，标记路径中的所有点

  • 只是因为已经找到了最大匹配，所以路径另外一端不可能 是自由顶点

  • 允许重复走过同一条边

• 路径中V到U的均为非匹配边、U到V均为匹配边

• 当然也可以从U的所有未匹配顶点开始

记集合V中中未被访问、U集合中已被访问的已匹配顶点点集为C，则 $顶点数目|C| = 最大匹配数 = 最小点覆盖数$

• 因为每个点都是M中某边端点，且V中已标记同U中未标记、V中 未标记顶点同U中已标记一一对应，为匹配边两端点，所以

  $$顶点数 = V中未被访问 + U中已访问 = \\ V中未访问 + V中已访问 = （最大）匹配数$$

• 在最大匹配情况下，所有边至少有一个端点为已匹配点

  • 对于匹配边，肯定被C中顶点覆盖

  • 若非匹配顶点在V中，则一定在某个路径中被访问，则被U 中某个已访问匹配顶点覆盖

  • 若非匹配顶点在U中，则被V中未访问顶点覆盖的

  • 或者说不存在这样的边：其左端点没有标记、而右端点有 标记

    • 匹配边肯定不是起点，不可能
    • 非匹配边，右端有标记则能直接访问左端，标记左端 （通样广度优先搜索遍历所有邻接有顶点点）

• 而要覆盖匹配边需要至少$|M|$个点，所以$|M|$是最小覆盖点数

推论 1

二分图中：最小边覆盖|W| = 图中顶点数|V| - 最小点覆盖数|C|

Ordered Bipartite Graph

有序二分图：以同一顶点作为端点的边的有优先级（独立于其他点）

• 即：V中顶点对U中顶点都有优先级排序，U中顶点对V中顶点也有 优先级排序

Marriage Matching

婚姻匹配问题可以使用特殊的完全有序二分图代表

• 集合V（男士集合）、U（女士集合）大小相同为n

• 任意男士、女士都有之间都有边连接，即任意男士、女士都需要 给出所有女士、男士优先级

存储、表示方法

• 优先列表：各男士、女士按照异性优先级排序列表，共2n个

  • 对实现匹配算法而言效率更高

• 等级矩阵：男士、女士为分别作为矩阵行、列，矩阵元素$P_ij$ 为男士$m_i$对女士$w_j$优先级排序、女士$w_j$对男士$m_i$ 优先级排序元组

  • 更容易看出集合元素匹配
  • 只需要$n * n$阶方阵

Stable Marriage Matching

对包含n个对的婚姻匹配M

• Block Pair：受阻对，满足$m \in V, w \in U$，而$(m, w)$ 更倾向于对方，而不是匹配M中对象

• Stable Marriage Matching：稳定婚姻匹配，不存在受阻对的 婚姻匹配

稳定婚姻存在性

V中存在自由男士时，任选求婚、回应之一执行，直至不存在 自由男士

• 求婚：自由男士m向女士w求婚，w为其优先级最大、之前未拒绝 过其女士（可以是已匹配）

• 回应：若女士w自由则接受男士m求婚，与之配对；女士w不自由 则把m同当前配偶匹配，选择其中优先级较高者

当不存在自由男士时，得到匹配M就是稳定匹配

• 若M是不稳定的，设存在受阻对$(m, w)$

• 因为m按照降序求婚，所以m必然在某次迭代向w求过婚，则w当前 对偶必然比m拥有更高优先级，和受阻对假设矛盾

• 稳定婚姻问题求解算法参见graph

Weighted Bipartite Graph

加权二分图；每条边都有权重的二分图

Distribution Problem

分配问题可以使用特殊的完全加权二分图代表

• 集合V（人员集合）、U（任务集合）大小相同为n

• 任意人员、任务有边相连，人员、任务内部之间无边

存储方法

• 使用$n * n$阶成本矩阵C存储，其元素$c_{ij}$表示人员$i$ 完成任务$j$的成本

• 则问题转化为：从成本矩阵中每行分别选择元素，且元素不属于 同一行，使得和最小

• （最小成本）分配问题算法参见graph

Biconnected Graph

• articulation point：关节点，删除顶点v、与v相连的各边 之后，将图一个连通分量分割成 两个、两个以上连通分量，则 称顶点v为图的一个关节点

• biconnected graph：重连通图，没有关节点的连通图

• 重连通图中任意一对结点之间至少存在两条路径

• 若在重连通图中至少删除k个顶点才能破坏图的连通性，则称图 的连通度为k

求解关节点

利用DFS可以求出图的关节点，判断图是否是重连通的，对DFS生成树

• 生成树有两棵及以上子树，则根节点为关节点
  • 因为不同子树之间不存在连通不同子树顶点的边
• 非叶子顶点v某棵子树中没有指向v前驱的回边，则v为关节点

• 算法参见algorithm/problems/graph

点集

点覆盖集

• Vertex Covering Set：点覆盖（集），顶点子集$S \subseteq V$ ，满足每条边至少有一个顶点在集合中

• Minimum Vertex Covering Set：最小顶点覆盖集，最少顶点的 点覆盖集

点支配集

• Vertex Dominating Set：点支配集，顶点子集$D \subseteq V$ ，满足$\forall u \in V-D, \exists v \in D, (u, v) \in E$

  • 即V中顶点要么是D中元素，要么同D中一个顶点相邻

• Minimum Vertext Dominating Set：最小支配集，顶点数目 最小支配集

• 极小支配集：真子集都不是支配集的支配集

点独立集

• Vertext Independent Set：（点）独立集，顶点子集 $I \subseteq V$，满足I中任意两顶点不相邻

• Maximum Vertext Independent Set：最大独立点集，顶点数 最多的独立点集

• 极大点独立集：超集都不是独立集的独立集

性质

Thoerem 1

若无向图$G(V, E)$中无孤立顶点，则G的极大点独立集都是G的极小 支配集（反之不成立）

Thoerem 2

一个独立集是极大独立集，当前且仅当其为支配集

Thoerem 3

若无向图$G=(V, E)$中无孤立点，顶点集$C \subseteq V$为G点覆盖 ，当且仅当$V - C$是G的点独立集

边集

边覆盖

• Edge Covering Set：边覆盖（集），边子集$W \subseteq E$， 满足$\forall v \in V, \exists e \in W$，使得v是e端点

  • 即G中所有点都是便覆盖W的邻接顶点

• Minimum Edge Covering Set：边数最少的边覆盖集

• 极小边覆盖集：任意真子集都不是边覆盖集的边覆盖

边独立集

• Matching/Edge Indepdent Set：匹配（边独立集），边子集 $I \subseteq E$，满足I中所有边没有公共顶点

• Maximum (Cardinality) Matching：最大（基数）匹配，包含 最多边的匹配

• 极大匹配：任意超集都不是匹配的匹配

• Perfect Matching：完美匹配，匹配所有点的最大匹配

• Mate：对偶，匹配中相互连接的一对顶点

性质

Thoerem 1

M为G一个最大匹配，对G中每个M未覆盖点v，选取一条与v关联边组成 集合N，则边集$W = M \cup N$为G中最小边覆盖

Thoerem 2

若W为G最小边覆盖，其中每存在相邻边就移去其中一条，设移去边集 为N，则边集$M = W - N$为G中一个最大匹配

Thoerem 3

最大匹配、最小边覆盖满足：$|M| + |W|= |V|$

度

Laplacian矩阵

$L=D-A$：Laplacian矩阵，其中

• $A$：邻接矩阵
• $D$：度矩阵（对角线为各个顶点度）

性质

• 若$c$为图中各个节点权重，则$c^T L C$为各个节点与其 邻接节点差值平方和
  • 展开即可证明

边数量

Multigraph

多重图：含有平行边，即顶点之间边数大于1

• 允许顶点通过边和自己相连

边权

欧几里得类型加权图

欧几里得类型加权图：权重满足欧式几何条件

• 三角不等式：任意3点$i,j,k, d{ij} \leqslant d{ik}+d{kj}

• 对称性：任意两个点$i,j, d_{ij}=d{ji}$

连通性

Transitive closure

传递闭包：表示所有节点两两直接连通性的n阶布尔矩阵T

• $T={t{ij}}$，若节点i到节点j直接存在有效（长度>0）有向 路径，则$t{ij}=1$，否则为0

Hamiltonian Circuit

哈密顿回路：对图每个顶点只穿过一次的回路

• 可以理解为：n+1个相邻顶点的一个排列，其中首尾顶点相同， 而其余顶点互不相同

  • 因为是回路，可以不失一般性的假定回路开始、结束于相同 顶点，这样不影响回路性质

Eular Circuit

欧拉回路：将给定图每条边都只遍历一次的回路

• 无向图：当且仅当连通多重图的每个顶点连通度都为偶数时， 才具有欧拉回路

• 有向图：当且仅当图中所有顶点是否出度、入度相等时，才存在 欧拉回路

• 在$\O(n^)$内解决问题

State-Space Graph

状态空间图：把问题化简为标准图问题

• 顶点：表示问题可能状态
• 边：表示状态之间的可能转换
• 原问题转换为求初始状态到目标状态顶点路径问题

综述

• 数组、广义表可以看作是线性表的扩展：线性表中数据元素本身 也是抽象数据结构

Array

对各维界分别为$b_i$的n维数组

• 数组中含有$\prod_{i=1}^n b_i$个数据元素，每个元素都受n个 关系约束

  • 每个关系中，元素都有直接后继
  • 就单个关系而言，这个n个关系仍然是线性关系

• n维数组可看作是线性表的推广，n=1时，数组退化为定长线性表

  • 和线性表一样，所有数据元素必须为同一数据类型

• 数组一旦被定义，其维数、维界就不再改变

  • 除了初始化、销毁之外，数组只有存储、修改元素值的操作
  • 采用顺序存储结构表示数组是自然的

• 几乎所有程序设计语言都把数组类型设定为固有类型

顺序存储表示

• 存储单元是一维结构，数组是多维结构，所有使用连续存储单元 存储数组的数据元素需要约定次序

  • BASIC、PL/1、COBOL、PASCAL、C语言中，以行序作主序
  • FORTRAN中，以列序作主序

• 数组元素存储地址

  $$\begin{align*} LOC(j_1, j_2, \cdots, j_n) & = LOC(0, 0, \cdots, 0) + (\sum_{i=1}^{n-1} j_i (\prod_{k=i+1}^n b_k + j_n))L & = LOC(0, 0, \cdots, 0) + \sum_{i=1}^n c_i_i \end{align}$$

  • $cn=L, c{i-1} = b_ic_i$

1
2
3
4
5
6
7
8
9

typedef struct{
	Elemtype * base;
	int dim;
		// 数组维数
	int * bounds;
		// 数组各维界（各维度长度）
	int * constants;
		// 数组各维度单位含有的数组元素数量，由`bounds`累乘
}

矩阵压缩

压缩存储：为多个值相同元只分配一个存储空间，对0元不分配空间

特殊矩阵

特殊矩阵：值相同元素、0元素在矩阵的分布有一定规律，将其压缩 至一维数组中，并找到每个非零元在一维数组中的对应关系

• 对称矩阵：为每对对称元分配一个存储空间
  • 一般以行序为主序存储其下三角（包括对角线）中的元
• 上/下三角矩阵：类似对称矩阵只存储上/下三角中的元，附加 存储下/三角常数
• 对角矩阵：同样可以按照行、列、对角线优先压缩存储

稀疏矩阵

稀疏矩阵：稀疏因子$\sigma = \frac t {mn} \leq 0.05$的矩阵

• 使用三元组（非零元值、其所属的行列位置）表示非零元

三元组顺序表

三元组顺序表/有序双下标法：以顺序结构表示三元组表

1
2
3
4
5
6
7
8
9

typedef struct{
	int i, j;
	ElemType e;
}Triple;
typedef struct{
	Triple data[MAXSIZE+1];
	int mu, nu, tu;
		// 行、列、非零元数
}TSMatrix;

• data域中非零元的三元组以行序为主序顺序排列，有利于进行 依行顺序处理的矩阵运算

行逻辑链接的顺序表

行逻辑链接的顺序表：带行链接信息的三元组表

1
2
3
4
5
6

typedef struct{
	Triple data[MAXSIZE+1];
	int rpos[MAXRC+1];
		// 各行首个非零元的位置表
	int mu, nu, tu;
}RLSMatrix;

• 为了便于随机存取任意行非零元，需要知道每行首个去非零元 在三元组表中的位置，即rpos

十字链表

十字链表：采用链式存储结构表示三元组的线性表

1
2
3
4
5
6
7
8
9
10
11
12

typedef struct OLNode{
	int i,j;
		// 该非零元行、列下标
	ElemType e;
	struct OLNode, *right, *down;
		// 该非零元所在行表、列表的后继链域
}OLNode, *OLink;
typedef struct{
	OLink *rhead, *chead;
		// 行、列链表表头指针向量基址
	int mu, nu, tu;
}CrossList;

• 同一行非零元通过right域链接成一个线性链表
• 同一列非零元通过down域链接成一个线性链表

• 适合矩阵非零元个数、位置在操作过程中变化较大的情况

Lists

广义表/列表：线性表的推广

• $\alpha_i$：可以时单个元素，也可以是广义表，分别称为LS 的原子、子表
• head：表头，LS非空时的首个元素$\alpha$
• tail：表尾，LS除表头外的其余元素组成的表，必然是列表

• 列表是一个多层次结构：列表的元素可以是子表，子表元素 也可以是子表
• 列表可以为其他列表所共享
• 列表可以是一个递归的表：即列表自身作为其本身子表

• 广义表长度：广义表中元素个数
• 广义表深度：广义表中最大括弧重数

链式存储结构

广义表中数据元素可以具有不同结构，难以用顺序存储结构表示， 通常采用链式存储结构

头尾链表

• 数据元素可能是原子、列表，因此需要两种结构的结点
  • 表节点：表示列表，包括：标志域、指示表头的指针域、 指示表尾的指针域
  • 原子节点：表示原子，包括：标志域，值域

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

typedef enum{ATOM, LIST} ElemTag;

typedef struct GLNode{
	ElemTag tag;
		// 标志域，公用
	union{
		// 原子节点、表节点联合部分
		AtomType atom;
			// 值域，原子节点
		struct{
			struct GLNode *hp, *tp;
				// 两个指针域，表节点
		}ptr;
	};
}*GList;

• 除空表的表头指针为空外，任何非空列表的表头指针均指向 表节点，且该表节点
  • hp指针域指向列表表头
  • tp指针域指向列表表尾，除非表尾为空，否则指向表节点
• 容易分清列表中原子、子表所属层次
• 最高层的表节点个数即为列表长度

扩展线性链表

1
2
3
4
5
6
7
8
9
10

typedef enum {ATOM, LIST} ElemTag;

typedef struct GLNode{
	ElemTag tag;
	union{
		AtomType atom;
		struct GLNode *hp;
		};
	struct GLNode *tp;
}*GList;

• 从数据结构来看，栈和队列也是线性表，但其基本操作是线性表 操作的子集
• 从数据类型来看，栈和队列是和线性表不同的抽象数据类型

Stack

栈：限定在表尾/栈顶进行插入和删除、操作受限的线性表

• top：栈顶，表尾端
• bottom：栈底，表头端

• 栈的修改是按照LIFO的方式运转，又称后进先出的线性表

  • 入栈：插入元素
  • 出栈：删除栈顶元素

• last in first out/栈应用广泛，对实现递归操作必不可少

顺序存储结构

顺序栈

顺序栈：顺序映像存储栈底到栈顶的数据元素，同时附设指针指示 栈顶元素在顺序栈帧中的位置

1
2
3
4
5

typedef struct{
	SElemType * base;
	SElemType *top;
	int stacksize;
}SqStack;

• base永远指向栈底，top指向栈顶元素下个位置

  • base==NULL：栈不存在
  • top==base：表示空栈

• 栈在使用过程中所需最大空间难以估计，因此一般初始化设空栈 时不应限定栈的最大容量，应分配基本容量，逐渐增加

链式存储结构

Queue

队列：限定在表尾/队尾进行插入、在表头/队头进行删除的 受限线性表

• rear：队尾，允许插入的一端
• front：队头，允许删除的一端

• 队列是一种FIFO的线性表
• 队列在程序设计中经常出现
  • 操作系统作业排队
  • 图的广度优先遍历

链式存储结构

链队列

链队列：使用链表表示的队列

1
2
3
4
5
6
7
8

typedef struct QNode{
	QElemType data;
	struct QNode  * next;
}QNode, *QueuePtr;
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

• front：头指针
• rear：尾指针

• 为方便同样给链队列添加头结点，令头指针指向头结点，此时 空队列判断条件为头、尾指针均指向头结点
• 链队列的操作即为单链表插入、删除操作的特殊情况的，需要 同时修改头、尾指针

顺序存储结构

循环队列

循环队列：使用顺序结构存储队列元素，附设两个指针分别指示对头 、队尾的位置

• 为充分利用数组空间，将数组视为环状空间

1
2
3
4
5

typedef struct{
	QElemType * base;
	int front;
	int rear;
}

• front：头指针
• rear：尾指针
• 循环队列时，无法通过rear==front判断队列空、满，可以在 环上、环外设置标志位判断

• C语言中无法用动态分配的一维数组实现循环队列，必须设置 最大队列长度，如果无法确定，应该使用链队列

Deque

双端队列：限定删除、插入操作在表两端进行的线性表

• 输出受限双端队列：一个端点允许删除、插入，另一个端点只 允许插入
• 输入受限双端队列：一个端点允许删除、插入，另一个端点只 允许删除
• 栈底邻接的两个栈：限定某个端点插入元素只能从该端点删除

• 看起了灵活，但是实际应用不多

Priority Queue优先队列

• 用于从一个动态改变的候选集合中选择一个优先级高的元素
• 主要操作
  • 查找、删除最大元素
  • 插入元素
• 实现
  • 可以基于数组、有序数组实现
  • 基于heap的优先队列实现更好

综述

串/字符串：零个或多个字符组成的有限序列

• 文本串：字母、数字、特殊符号构成
• 位串：0、1构成
• 基因序列：可以使用字符串模型表示，其字母表只包括4个 字母{A, C, G, T}

• $s$：串名，其后单引号括起是串的值
• $a_i$：字母、数字等字符
• $n$：串中字符的数目，串长度，零个字符的串称为空串

• 串的逻辑结构和线性表相似，只是串的数据对象约束为字符集
• 串的基本操作和线性表有很大差别
  • 线性表基本操作大多以“单个元素”作为操作对象
  • 串的基本操作通常以“串的整体”作为操作对象

串的存储表示

• 串只作为输入、输出常量出现，则只需要存储串的串值字符序列
• 在非数值处理中，串也以变量形式出现

定长顺序存储

• 类似线性表的顺序存储结构
• 按照预定义大小，为每个定义的串变量分配固定长度的存储区， 存储字符序列

1

typedef unsigned char SString[MAXSTRLEN+1]

• 串实际长度在预定义范围内随意，超过预定义长度的串值则被 舍去（截断）
• 串实际长度存储方式
  • 以下标为0的数组分量存放：Pascal
  • 在串值后面加入不计串长的结束标记字符：C以\0标记， 此时串长为隐含值，不利于某些操作
• 串操作的原操作为“字符序列的复制”，操作的时间复杂度基于 复制的字符序列长度

堆分配存储

• 仍然以地址连续的存储单元存储串字符序列，但存储空间是在 程序执行过程中动态分配得到

1
2
3
4

typdef struct{
	char *ch;
	int length;
}

• length：串长

• 既有顺序存储结构的特点，处理方便，对串长又没有任何限制
• 此存储结构的串操作仍是基于“字符序列的复制”进行

块链存储

• 使用链表的方式存储串值
• 但是串结构特殊的，需要设置节点大小

1
2
3
4
5
6
7
8

typedef struct Chunk{
	char ch[CHUNKSIZE];
	struct CHUNK * next;
}Chunk;
typedef struct{
	Chunk *head, *tail;
	int curlen;
}

• CHUNKSIZE：节点大小，每个节点中最大存储字符数量
• curlen：当前串长度

• 节点大小不为1时，链表最后一个节点不一定全被串值占满， 此时通常补上非串值字符
• 一般情况下，对串进行操作时，只需要从头到尾扫描即可
  • 对串值不必简历双向链表
  • 设尾指针是为了方便进行联结操作（联结操作需要注意 串尾无效字符）
• 节点大小选择影响串处理效率
  • 存储效率 = 串值所占存储位/实际分配存储位
  • 存储密度小，运算处理方便，存储量占用大
• 块链结构对某些串操作有一定方便，但是总的来说不如另外两种 存储结构灵活，存储量大、操作复杂

串的模式匹配

模式匹配：子串定位操作