AKSZ-树和图
2024-06-16 16:36:12
发布于:广东
数和图
图
有若干个给定的顶点,若干条连接两个顶点的边所构成的图形,通常用于描述某些事物之间的某种特定的关系。用顶点表示事物,用连接两个顶点的边表示两个事物具有某种关系。
图是图论的研究对象。
分为有向图和无向图(边是否具有指向性)。边可带边权。
图经常用 表示。V表示顶点集合,E为边集合。 <a, b> 表示一条由a至b的有向边。
顶点的个数称为图的阶。
基图:忽略有向图所有边的方向,得到的无向图称为该有向图的基图。
完全图:无向图中任何一对顶点之间都有一条边。(有向完全图:每对顶点之间都有一条有向边)
边数:(有向:)。
稀疏图:边的数目相对较少(远小于 )。
稠密图:边的数目相对较多(接近于完全图)。
平凡图:只有一个顶点的图。
零图:边集合为空的图。
自环:一个结点连接到自身的边。
重边:两个结点之间存在多条边。
带权图:边上带有权的图。
简单图:一种无向图或有向图,其中不存在自环或重边。
多重图:一种无向图或有向图,其中存在自环或重边。
路径:在图 中,从顶点 出发,沿着一些边经过一些顶点 $v(p1),v(p2)...... $ 到达顶点 ,则称这个顶点序列为顶点 至顶点 的一条路径。
路径长度:路径中边的数目。
连通:若从顶点 u 到 v 有路径,则称顶点 u 和 v 是连通的。
连通图:如果无向图中任意一对顶点都是连通的,则称此图为连通图。
强连通图:如果有向图中,若每一对顶点 u 和 v ,即存在从 u 到 v 的路径,也存在从 v 到 u 的路径,则称此图为强连通图。
树
如果一个无向连通图中不存在回路,则这种图称为树。
树是一种特殊的图。
有 n 个顶点, (n - 1) 条边的不存在回路的连通图。当n == 0,称为空树。当 n > 0,树有且仅有一个特定的结点——根结点。
除根结点外的其他节点划分为 m 个互不相交的有限集 。
其中每个集合本身又是一棵树,称为根节点的子树。
度:结点拥有的子树的数量为结点的度,度为 0 的结点为叶子结点,度不为 0 的结点为分支结点。树的度定义为树的所有节点中度的最大值。
树的前驱和后继:除根节点没有前驱外,其余每个节点都有唯一的一个前驱节点。每个节点可以有 0 或多个后继结点。结点的直接后继称为结点的孩子,结点的直接前驱称为结点的父亲,拥有同一个父亲的结点称为兄弟结点。
const int MAXN = 1e6 + 9;
// 1.父亲表示法
// 每个节点只记录父亲的编号
int fa[MAXN];
// fa数组表示编号
void init() // 当 1 作为根节点
{
fa[1] = 0;
}
void add_f(int f, int s) // 添加父亲结点
{
fa[s] = f;
}
// 2.孩子表示法
vector<int> V[MAXN]; // V[i] 表示第 i 个结点的儿子编号为哪些
void add_s(int f, int s) // 添加子结点
{
V[f].push_back(s);
}
树中结点的层次:树中根节点为第 1 层,根节点的孩子为第 2 层,依次类推。树中结点的最大层次称为树的深度(高度)。注意:部分题目中根节点为第 0 层。
除根节点没有父节点外,其余节点有且仅有一个父结点。
二叉树
一种度数最大为2的树,即二叉树的每个节点最多有两个子节点,每个结点的子节点分别称为左孩子、右孩子,它的两棵子树称为左子树、右子树。
满二叉树:一棵深度为 k 且有 个结点的二叉树称为满二叉树。
完全二叉树:若二叉树的高度为 k ,则共有 k 层,除第 k 层外,其他各层 (1 ~ (k - 1)) 的结点数都达到最大个数,且第 k 层的结点是从左到右连续的,称为完全二叉树。
二叉搜索树
性质
- 若左子树不空,则左子树上所有结点的值均小于它根节点的值。
- 若右子树不空,则右子树上所有结点的值均大于它根节点的值。
- 左,右子树也是一颗二叉搜索树。
##a叉树
图的性质
图中顶点的度:于该顶点向连的边的数量
在无向图中,一个顶点的度数就是和该顶点相连的边的数量
在有向图中,一个顶点的都等于该顶点的出度和入度的和。(入度是指向该顶点的边的数量,出度是从该顶点出发的边的数量。)
二叉树的性质
- 对任意一棵二叉树,如果其叶子结点的数量为,度为2的结点数为,则一定满足。
设树中结点的总数为n,度为1的结点的总数为,则:
-
具有个结点的完全二叉树的深度为。
-
如将一颗有n个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号,则有以下关系:
① 若,则结点 i 为根,无父节点。
② 若,则 i 的父节点编号为。
③ 若,则 i 无左孩子,否则其左孩子编号为。
④ 若,则 i 无右孩子,否则其右孩子编号为。
图的存储
- 邻接矩阵:一种二维数组,其中每个元素表示两个结点之间的边。(带权图:二维数组中的每个元素表示此边上的边权。当边不存在时,适当选取较大的常数。)
二叉树的遍历
遍历命名 —— 根在遍历方式中的位置。
- 先序遍历(前序遍历):根结点 -> 左子树 -> 右子树
- 中序遍历:左子树 -> 根节点 -> 右子树
- 后序遍历:左子树 -> 右子树 -> 根节点
中序遍历+另外任意一种遍历方式,可以唯一确定一棵二叉树。先序遍历与后序遍历不一定能唯一确定一个二叉树。
这里空空如也
有帮助,赞一个