图
图 (Graph) 是由若干个给定的点、及若干条连接两个顶点的边所构成的图形,这种图像通常用来描述描述某些事物之间的某种特定的关系
图常用G(V,E)G(V, E)G(V,E)表示,VVV (Vertex) 为顶点集合, EEE (Edge) 为边集合
顶点的个数称为图的阶
图是图论的研究对象
图论这一部分的知识点,侧重图结构的描述、图结构的存储和遍历、少量剧本的图论算法的实现
分类
无向图:可以直接由某一状态回到前一个状态
有向图:不能直接由某一状态回到前一个状态,<a,c><a, c><a,c>和<c,a><c, a><c,a>为两条有向边
有向图的基图:忽略有向图所有边的方向, 得到的无向图称为该有向图的基图
完全图和有向完全图
完全图(Complete Graph):无向图中任何一对顶点之间都有一条边
一个nnn阶的完全图有n∗(n−1)2\frac{n * (n - 1)}{2}2n∗(n−1) 条边
有向完全图(Directed Complete Graph):有向图中任何一对顶点之间都有两条有向边
稀疏图和稠密图
稀疏图:边的数目相对较少(远小于n∗(n−1)n * (n - 1)n∗(n−1))
稠密图:边的数目相对较多(接近于完全图或者完全有向图)
平凡图和零图
平凡图:只有一个顶点的图
零图:没有边的图
自环和重边
自环:一个顶点
重边:两个顶点有多条边
权
带权图(Weighted Graph):边上带有权值的图
权:可以抽象的理解为金钱、时间、长度
简单图和多重图
简单图(Simple Graph):一种无向图或有向图, 其中不存在自环和重边
多重图(Multi Graph):一种无向图或有向图, 其中存在自环和重边
连通
路径:在图G(V,E)G(V, E)G(V,E)中, 从顶点vvv出发, 沿着一些边经过顶点vp1,vp2,vp3,...v_{p1}, v_{p2}, v_{p3}, ...vp1 ,vp2 ,vp3 ,... 到达顶点vjv_{j}vj , 则称顶点序列(vi,vp1,vp2,vp3,...,vj)(v_i, v_{p1}, v_{p2}, v_{p3}, ... , v_j)(vi ,vp1 ,vp2 ,vp3 ,...,vj )
连通:若从顶点uuu到vvv有路径, 则称顶点uuu和vvv是连通的
连通图:如果无向图中任意一对顶点都是连通的,则称此图为连通图
强连通图:如果有向图中,若每一对顶点uuu和vvv, 即存在uuu到vvv的路径,也存在vvv到uuu的路径,则称此图为强连通图
度
* 图中顶点的度:与该顶点相连的边的数量
* 在无向图中,一个顶点的度数就是和该顶点相连的边的数量
* 在有向图中,一个顶点的度数就是该顶点的入度和出度的和。(入度就是指向该的的边的数量,出度是从该顶点出发的边的数量)
图/树
树(Tree):如果一个无向连通图中不存在回路,则称这种图为树
树是一种特殊的图
树也可以从数据结构的角度去定义,涉及的术语有 子树、孩子结点、度、层次
树作为一种非线性的数据结构,是由n(n≥0)n(n\ge 0)n(n≥0)个结点组成的有限集合
如果n==0n==0n==0时,称为空树,如果n>0n > 0n>0,树有且只有一个特点的结点——根节点(root)
度:结点拥有的子树的数量为结点的度,度为000的结点为叶子结点,度不为000的结点为分支结点
树的前驱和后继:除根结点没有前驱外,其余结点都有唯一的一个前驱结点。每个结点可以有000个或多个后继结点。结点的直接后继称为结点的孩子,结点的直接前驱称为结点的父亲
树中结点的层次:书中根节点为第一111层,根节点的孩子为第二222层,以此类推。书中结点的最大层次称为树的深度(高度)
注意:部分题目中的根节点为第000层
C++建树
求树直径(距离最远的两个点)
bfs与dfs模板
二叉树
二叉树(Binary Tree) 是一种度数最大为222的树,即二叉树的每个结点最多有两个子节点,每个子节点分别称为左子树、右子树
链也是一种树
一颗深度为kkk且有2k−12^k - 12k−1个结点的二叉树称为满二叉树
若二叉树的高度为kkk,则共有kkk层,除第kkk层外,其他各层111~(k−1)(k - 1)(k−1)的结点数都达到最大个数,且第kkk层缺少的结点是从左到右并连续的,这就是完全二叉树
对任意一颗二叉树,如果其叶子结点的数量为n0n_0n0 ,度为2的结点数为n2n_2n2 ,则一定满足n0=n2+1n_0 = n_2 + 1n0 =n2 +1
证明:1、n=n0+n1+n2n = n_0 + n_1 + n_2n=n0 +n1 +n2 。2、孩子结点有n1+2n2n_1 + 2n_2n1 +2n2 ,所以n=n1+2n2+1n = n_1 + 2n_2 + 1n=n1 +2n2 +1。由此可得n0=n2+1n_0 = n_2 + 1n0 =n2 +1
具有n(n≥0)n (n \ge 0)n(n≥0)个结点的完全二叉树的深度为⌊log2n⌋+1\lfloor \log_{2}{n} \rfloor + 1⌊log2 n⌋+1(⌊⌋\lfloor \rfloor⌊⌋是向下取整)
如将一颗具有nnn个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号1,2,...,n1, 2, ..., n1,2,...,n,则有以下关系:
1. 若i=1i = 1i=1,则结点iii为根,无父结点
2. 若i>1i > 1i>1,则iii的父结点编号为⌊i/2⌋\lfloor i / 2 \rfloor⌊i/2⌋
3. 若2∗i>n2 * i > n2∗i>n,则iii无左孩子,否则其左孩子编号为2∗i2 * i2∗i
4. 若2∗i+1>n2 * i + 1 > n2∗i+1>n,则iii无右孩子,否则其右孩子编号为2∗i+12 * i + 12∗i+1
二叉搜索树
二叉搜索树(Binary Search Tree) 是一种应用十分广泛的二叉树
二叉搜索树具有的性质:
1. 若左子树不空,则左子树上所有的结点的值均小于它根结点的值
2. 若右子树不空,则右子树上所有的结点的值均大于它根结点的值
3. 左,右子树也是一个二叉搜索树
满A叉树结点
f[k]=20+21+......+2(k−1)f[k] = 2^0 + 2^1 + ...... + 2^(k- 1)f[k]=20+21+......+2(k−1)
2∗f[k]=21+22+......+2(k−1)2 * f[k] = 2^1 + 2^2 + ...... + 2^(k- 1)2∗f[k]=21+22+......+2(k−1)
2∗f[k]−f[k]=2k−202 * f[k] - f[k] = 2^k - 2^02∗f[k]−f[k]=2k−20
f[a]=(ak−1)/(a−1)f[a] = (a^k - 1) / (a - 1)f[a]=(ak−1)/(a−1)