树与图论
树与图论
基础概念
图
- 图由顶点和边组成，一条边连接两个顶点
- 自环：一条边链接相同的两个顶点
- 重边：两条边所链接的两个顶点都相同
- 点和边都可以带权，称为点权、边权
- 点的度数（有向图分入度、出度）
- 稠密图中 \(m\) ~ \(O(n^2)\)（\(m\) 边数，\(n\) 点数）
- 稀疏图中 \(m\) ~ \(O(n)\)
- ~ 表示接近于
树
- 所有顶点之间相互连通且不存在环
- 一棵树有 \(n\) 个顶点，\(n-1\) 条边
- 两点之间仅存在一条简单路径
存图方式
- 邻接矩阵
- \(G[i][j]=w\) 存储 \((i,j)\) 之间有一条边权为 \(w\) 的边
- 适用于稠密图
- 邻接表
- 用 \(vector\) 存储每个结点的所有出边
- 适用于稀疏图
树的性质
二叉树的遍历
- 前序遍历：根左右
- 中序遍历：左根右
- 后序遍历：左右根
- 给定二叉树，求遍历顺序时模仿递归函数进行模拟
- 根据分治思想，给定 中序遍历（必须有） 和其他一个遍历，可以倒推出最后一种遍历或原二叉树
树的直径
- 树上的一条路径，满足其边权之和最大
- 如果边权均非负的求法
- 随意选择一个结点进行 DFS，找到距离它最远的结点 \(s\)
- 从 \(s\) 开始进行 DFS，找到距离它最远的结点 \(t\)
- \(s \rightarrow t\) 即为树的直径