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