图论核心概念
基础图类型
1. 有向图（DIRECTED GRAPH）
* 定义：边有方向，表示为有序对 ((u, v))。
* 特点：若存在 (u \to v)，不代表存在 (v \to u)（除非显式定义）。
2. 无向图（UNDIRECTED GRAPH）
* 定义：边无方向，表示为无序对 ({u, v})。
* 特点：边是双向的，({u, v} = {v, u})。
3. 带权图（WEIGHTED GRAPH）
* 定义：边或顶点附带权重（如距离、成本）。
* 应用：最短路径算法（如Dijkstra）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
图的特殊结构
4. 路径（PATH）
* 定义：顶点序列 (v_1, v_2, \dots, v_k)，满足相邻顶点间有边连接。
* 类型：
* 简单路径：顶点不重复（环路除外）。
* 有向路径：边方向必须一致（适用于有向图）。
5. 环路（CYCLE）
* 定义：起点和终点相同的闭合路径，且中间顶点不重复。
* 示例：
* 无向图：(a—b−c—a)(a — b - c — a)(a—b−c—a)。
* 有向图：(a \to b \to c \to a)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
图的连通性与环
6. 连通图（CONNECTED GRAPH）
* 无向图：任意两顶点间存在路径。
* 有向图：
* 强连通：任意两顶点双向可达。
* 弱连通：忽略方向后无向图连通。
7. 有环图（CYCLIC GRAPH）
* 定义：至少包含一个环路。
* 影响：可能导致算法陷入无限循环（需检测环）。
8. 无环图（ACYCLIC GRAPH）
* 定义：不包含任何环路。
* 典型代表：
* 有向无环图（DAG）：用于拓扑排序、动态规划。
* 树（Tree）：连通无环无向图。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
图的密度分类
9. 稠密图（DENSE GRAPH）
* 定义：边数接近最大可能边数（(|E| \approx |V|^2)）。
* 特点：适合用邻接矩阵存储。
* 示例：社交网络中的紧密社群。
10. 稀疏图（SPARSE GRAPH）
* 定义：边数远小于最大可能边数（(|E| \ll |V|^2)）。
* 特点：适合用邻接表存储。
* 示例：道路网络（城市间连接较少）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
对比总结
概念 关键特性 应用场景 有向无环图（DAG） 无环路，方向一致 任务调度、依赖管理 稠密图 边数多，存储效率高 矩阵运算、聚类分析 稀疏图 边数少，节省空间 社交网络、路由算法 强连通图 任意两顶点双向可达 网络可靠性分析
树的基本概念
1. 定义：树是由n(n≥0)n(n \geq 0)n(n≥0)个节点组成的有限集合，当n=0n=0n=0时称为空树；非空树满足：
* 有且仅有一个根节点
* 其余节点可分为m(m≥0)m(m \geq 0)m(m≥0)个互不相交的有限集合，每个集合本身又是一棵树，称为子树
2. 基本术语：
* 节点的度：节点拥有的子树个数
* 树的度：树中各节点度的最大值
* 叶子节点：度为0的节点（终端节点）
* 分支节点：度不为0的节点（非终端节点）
* 孩子节点：节点的子树的根称为该节点的孩子
* 双亲节点：一个节点是其子树根的双亲
* 兄弟节点：同一双亲的孩子互称兄弟
* 节点的层次：根为第一层，其孩子为第二层，以此类推
* 树的深度/高度：树中节点的最大层次
二、二叉树
1. 定义：每个节点最多有两个子树的树结构，子树有左右之分，次序不能颠倒
2. 性质：
* 第iii层上最多有2i−12^{i-1}2i−1个节点
* 深度为kkk的二叉树最多有2k−12^k -12k−1个节点
* 对于任何二叉树，若叶子数为n0n_0n0 ，度为2的节点数为n2n_2n2 ，则n0=n2+1n_0=n_2+1n0 =n2 +1
* 对于完全二叉树来说，高度为⌊log2(n)⌋+1\lfloor \log_2(n)\rfloor + 1⌊log2 (n)⌋+1
* 对于完全二叉树来说，若父亲结点编号为iii，左孩子编号为2i2i2i，右孩子编号为2i+12i+12i+1
3. 特殊二叉树：
* 满二叉树：深度为kkk且有2k−12^k-12k−1个节点
* 完全二叉树：除最后一层外，其余层都是满的，且最后一层节点都靠左排列
