课堂笔记
2025-04-12 11:59:34
发布于：浙江
16阅读
0回复
0点赞
图论核心概念
基础图类型
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 \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） | 无环路，方向一致 | 任务调度、依赖管理 |
| 稠密图 | 边数多，存储效率高 | 矩阵运算、聚类分析 |
| 稀疏图 | 边数少，节省空间 | 社交网络、路由算法 |
| 强连通图 | 任意两顶点双向可达 | 网络可靠性分析 |
树的基本概念
-
定义：树是由个节点组成的有限集合，当时称为空树；非空树满足：
- 有且仅有一个根节点
- 其余节点可分为个互不相交的有限集合，每个集合本身又是一棵树，称为子树
-
基本术语：
- 节点的度：节点拥有的子树个数
- 树的度：树中各节点度的最大值
- 叶子节点：度为0的节点（终端节点）
- 分支节点：度不为0的节点（非终端节点）
- 孩子节点：节点的子树的根称为该节点的孩子
- 双亲节点：一个节点是其子树根的双亲
- 兄弟节点：同一双亲的孩子互称兄弟
- 节点的层次：根为第一层，其孩子为第二层，以此类推
- 树的深度/高度：树中节点的最大层次
二、二叉树
-
定义：每个节点最多有两个子树的树结构，子树有左右之分，次序不能颠倒
-
性质：
- 第层上最多有个节点
- 深度为的二叉树最多有个节点
- 对于任何二叉树，若叶子数为，度为2的节点数为，则
- 对于完全二叉树来说，高度为
- 对于完全二叉树来说，若父亲结点编号为，左孩子编号为，右孩子编号为
-
特殊二叉树：
- 满二叉树：深度为且有个节点
- 完全二叉树：除最后一层外，其余层都是满的，且最后一层节点都靠左排列
这里空空如也
有帮助，赞一个