Elian's blog page

定义查找是在数据集合中寻找满足某种条件的数据元素。用于查找的数据集合称为查找表或查找结构，通常由同一类型的数据元素组成。 关键字是数据元素中能够标识该元素的数据项。若使用关键字查找，且关键字能唯一标识元素，则查找结果应当唯一。 查找表按操作需求可分为两类： 类型 主要操作 关注点 静态查找表 只查找 查找速度 动态查找表 查找、插入、删除 查找速度与插入、删除是否方便 ASL查找长度是在一次查找过程中进行关键字比较的次数。平均查找长度 ASL 是所有查找过程的关键字比较次数的加权平均： $$ASL=\sum_{i=1}^{n}P_iC_i$$ 其中 $P_i$ 是第 $i$ 种查找情况发生的概率，$C_i$ 是对应的查找长度。若默认所有元素等概率，则每个成功查找的概率通常取...

图的遍历与连通性图的遍历不仅是“访问所有顶点”的算法模板，也能反映图的连通性。复习时先分清图的类型：无向图看连通分量，有向图看沿弧方向的可达范围；强连通图才有“任一顶点出发都能覆盖全部”的性质。 相关卡片：图的定义、无向图与有向图、广度优先搜索、深度优先搜索、图的连通性与连通分量、Tarjan 算法、图的关系概念速查表。 无向图：调用次数就是连通分量数对无向图执行完整遍历时，常见框架是： 12345for (int i = 0; i < vertexCount; ++i) { if (!visited[i]) { Search(G, i, visited); // Search 可以是 BFS 或 DFS }} 这里的关键是：每次从一个未访问顶点启动 BFS/DFS，都会完整覆盖该顶点所在的连通分量。由于不同连通分量之间没有路径，前一次遍历不可能跨到另一个分量。 因此对无向图： 图的情况 BFS/DFS...

深度优先搜索深度优先搜索（Depth-First Search, DFS）是图的遍历算法。它从某个起始顶点出发，沿着一个未访问邻接点不断深入；当前顶点没有未访问邻接点时，再返回上一层，继续尝试上一层的其他邻接点。 相关卡片：广度优先搜索、图的基本操作、递归与栈、搜索与回溯。 从树的先根遍历到图的 DFS树的深度优先遍历通常对应先根遍历： 访问当前结点。 递归访问第一个孩子及其子树。 第一个孩子子树处理完后，再处理下一个孩子子树。 所有孩子处理完，返回上一层。 图的 DFS 与它类似，但图可能有回路。树中从父结点走向孩子时，孩子一定没访问过；图中搜索邻接点时，可能遇到已经访问过的顶点，所以必须维护 visited[]。 DFS 的核心状态 visited[v] = true 表示顶点 v 已经被发现。递归版本 DFS 的“当前搜索路径”隐含保存在函数调用栈中，这一点也是有向图判环的基础。 递归调用栈过程若邻接表顺序为： 123456781: 2, 52: 1, 63: 4, 6, 74: 3, 7, 85: 16: 2, 3, 77: 3, 4, 6, 88: 4,...

广度优先搜索广度优先搜索（Breadth-First Search, BFS）是图的遍历算法。它从某个起始顶点出发，先访问距离起点最近的一层顶点，再访问下一层顶点。实现上的核心工具是队列：先被发现的顶点先扩展。 相关卡片：图的基本操作、邻接矩阵、邻接表、连通分量。 从树的层序遍历到图的 BFS树的层序遍历可以直接用队列： 根结点入队。 队头结点出队并访问。 将该结点的孩子依次入队。 重复直到队列为空。 图的 BFS 与它非常像，但图可能有回路。搜索某顶点的邻接点时，可能遇到已经访问过的顶点，所以 BFS 必须额外维护 visited[] 数组。 图比树多出的关键处理 对一个新邻接点，必须在它入队时就标记 visited[w] = true。否则同一个顶点可能在真正出队前，被多个已访问顶点重复发现并重复入队。 BFS 要解决的三个小问题 问题 典型接口或结构 说明 怎样找到某顶点的邻接点 FirstNeighbor(G, v) 与 NextNeighbor(G, v,...

图的基本操作图的基本操作要分清两个层次：接口语义和存储结构代价。接口语义说明“这个操作要做什么”，存储结构决定“做这件事要扫描矩阵、扫描链表，还是直接改指针”。 相关卡片：邻接矩阵、邻接表、十字链表与邻接多重表。 操作语义 操作 含义 常见返回或效果 Adjacent(G, x, y) 判断图 $G$ 是否存在边 $(x,y)$ 或弧 $\langle x,y\rangle$ 存在返回 true，否则返回 false Neighbors(G, x) 列出与顶点 $x$ 邻接的边或弧 返回邻接点或邻接边集合 InsertVertex(G, x) 在图 $G$ 中插入顶点 $x$ 新顶点初始没有关联边 DeleteVertex(G, x) 从图 $G$ 中删除顶点 $x$ 同时删除与 $x$ 相关的边或弧 AddEdge(G, x, y) 若边或弧不存在，则添加 $(x,y)$ 或 $\langle x,y\rangle$ 修改边集 RemoveEdge(G, x, y) 若边或弧存在，则删除 $(x,y)$ 或 $\langle...

十字链表与邻接多重表邻接表对稀疏图很省空间，但它有两个典型不便： 有向图中，邻接表默认保存出边，找入边要扫描整个邻接表。 无向图中，每条边会在两个顶点的链表里存两份，删除边或删除顶点时要处理冗余边结点。 十字链表和邻接多重表就是针对这两个问题设计的。 其思想皆为：链头数组表示顶点，链接的每一个不同的节点都表示不同的边。 十字链表十字链表用于存储有向图。 它的核心规则是：一个弧结点同时出现在两条链中： 弧尾顶点的出边链。 弧头顶点的入边链。 顶点结点包含： 字段 含义 data 顶点数据 firstin 以该顶点为弧头的第一条弧，即第一条入边 firstout 以该顶点为弧尾的第一条弧，即第一条出边 弧结点包含： 字段 含义 tailvex 弧尾顶点编号 headvex 弧头顶点编号 info 权值或其他弧信息 hlink 弧头相同的下一条弧 tlink 弧尾相同的下一条弧 12345678910111213typedef struct OLArcNode { int tailvex; ...

邻接表法邻接表法用一个顶点表保存所有顶点，再给每个顶点接一条链表，链表中保存与该顶点直接相关的边或弧。它本质上是顺序存储 + 链式存储：顶点表适合按编号定位顶点，边结点链表只保存实际存在的边或弧。 为什么需要邻接表邻接矩阵必须开 $|V|\times |V|$ 个单元。若图很稀疏，大量位置只是表示“没有边”，空间浪费明显。 邻接表只保存实际存在的边或弧，因此更适合稀疏图。 存储结构邻接表一般由两类结点组成： 结点 保存内容 作用 顶点表结点 顶点数据 data，第一条边或弧的指针 firstArc 顺序存储所有顶点，支持按编号访问 边/弧结点 邻接点编号 adjvex，下一条边或弧的指针 next，可选权值 weight 链式保存某个顶点的邻接关系 123456789101112131415161718192021222324#include <stdbool.h>#define MAX_VERTEX_NUM 100typedef char VertexType;typedef int EdgeType;typedef struct...

邻接矩阵法邻接矩阵法用一个二维数组保存顶点之间是否有边、弧或权值。它的核心优点是判断两个顶点是否相邻很直接，核心代价是空间只和顶点数有关，即使边很少也要开 $|V|^2$ 个单元。 基本定义设图 $G=(V,E)$ 有 $n$ 个顶点，将顶点编号为 $v_1,v_2,\cdots,v_n$。邻接矩阵 $A$ 是一个 $n\times n$ 的矩阵： $$A[i][j]=\begin{cases}1, & (v_i,v_j)\in E \text{ 或 } \langle v_i,v_j\rangle\in E\0, & (v_i,v_j)\notin E \text{ 且 } \langle v_i,v_j\rangle\notin E\end{cases}$$ 对无向图，$A[i][j]=1$ 表示 $v_i$ 与 $v_j$ 之间有边。 对有向图，$A[i][j]=1$ 表示存在从 $v_i$ 指向 $v_j$ 的弧。 顶点中可以保存更复杂的信息；矩阵单元可以用 bool、枚举型或整型表示边是否存在。 0 和...

图中的树、森林与有向树这里讨论的是图论视角下的树：它是无向图或有向图的一种特殊形态。树作为数据结构的完整定义、结点关系、层次、高度、度等概念见 树的基本概念。 无向图中的树在图论中，不存在回路且连通的无向图称为树。 它同时满足两个条件： 连通：任意两个顶点之间都有路径； 无回路：图中不存在环。 若树有 $n$ 个顶点，则必有$n-1$条边。 这个结论和生成树一致：生成树本身就是覆盖原连通图全部顶点的一棵树。 森林若无向图由若干棵互不相交的树组成，则称为森林。 从连通性角度看，森林的每个连通分量都是一棵树。若森林有 $n$ 个顶点、$k$ 个连通分量，则共有$n-k$条边。 有向树一个顶点的入度为 $0$，其余顶点的入度均为 $1$ 的有向图，称为有向树。 这个定义抓住的是“唯一入口关系”： 入度为 $0$ 的顶点相当于根； 其余顶点各有唯一前驱； 边有方向，方向通常体现从根向外的支配或层级关系。 常见考点对 $n$ 个顶点的无向图： 若它是一棵树，则边数为 $n-1$。 若 $|E|>n-1$，则图中一定有回路。 使用条件 “$|E|>n-1$...

稀疏图与稠密图稀疏图和稠密图描述的是图中边的多少。它们没有绝对分界线，通常用于选择存储结构或算法。 稀疏图边数很少的图称为稀疏图。 一般可用下面的经验界限： $$|E|<|V|\log |V|$$ 当图满足这个条件时，可以将 $G$ 视为稀疏图。 稠密图边数很多的图称为稠密图。 稠密图通常接近完全图的边数上界： 无向图最多有 $C_n^2=\frac{n(n-1)}{2}$ 条边； 有向图最多有 $2C_n^2=n(n-1)$ 条弧。 查阅重点 维度 稀疏图 稠密图 边数 少 多 常见存储 邻接表更节省空间 邻接矩阵可直接判断相邻 算法选择 常按边集或邻接表扫描 可接受矩阵级别扫描 判断边界 没有绝对界限 没有绝对界限 考点表述 “一般来说 $|E|<|V|\log|V|$ 时可视为稀疏图”是经验判断，不是数学定义中的硬边界。