图
图是由若干个顶点和若干条链接两个顶点的边所构成的图形
图是图论的研究对象
表示
Gragh Vertex Edge
G(V,E)
V为顶点集合
E为边的集合
顶点的个数为图的阶
度(无向图)
与该顶点连接的边的数量
出度(有向图)
从该顶点出发点变得数量
入度(有向图)
指向该顶点的边的数量
有向图的基图
忽略有向图所有变得方向,得到的无向图称为该有向图的基图
完全图
无向图中任意以对顶点之间都有一条边
一个 n 阶的完全图含有n∗(n−1)n*(n-1)n∗(n−1)条边
有向完全图
任何一对顶点 u 和 v ,都存在<u,v>和<v,u>两条边
稀疏图
边的数目较少
稠密图
边的数目较多
自环
一个节点链接到自身的边
重边
两个节点之间有多条边
简单图
不存在自环或重边的图
多重图
存在自环或重边的图
路径长度
路径中变得数目
连通
若从顶点 u 到 v 有路径,则称顶点 u 和 v 是连通的
连通图
无向图中任意一对顶点都连通
强连通图
如果有向图中,若每一对顶点 u 和 v ,既存在从 u 到 v 的路径,也存在 v 到 u 的路径,则称此图为强连通图
邻接矩阵储存
如果两个节点之间存在边,则数组中的元素为1,否则为0
树
非线性数据结构,由n个节点组成的有限集合
rootrootroot根节点
定义
如果一个无向连通图中不存在回路,则这种图称为树
度
节点拥有的树的数量为节点的树
度为 0 的节点为叶子节点
树的度为树中节点最大的度
树的前驱和后继
除根节点外都有前驱
每个节点都有0或多个节点
树中节点的层次
树的深度
求树直径模板(BFS)
https://www.spoj.com/problems/PT07Z/
求树直径模板(DFS)
https://www.spoj.com/problems/PT07Z/
模板
二叉树(BT)
每个节点有两棵子树
性质
其叶子节点的数量为N0N0N0,度为2的节点数量为N2N2N2,则一定满足N0=N2+1N0=N2+1N0=N2+1
具有nnn个节点的完全二叉树的深度为向下取整log2n+1log2n+1log2n+1
iii的父节点的编号为向下取整i/2i/2i/2
若2∗i>n2*i>n2∗i>n,则iii无左孩子,否则左孩子编号为2∗i2*i2∗i
若2∗i+1>n2*i+1>n2∗i+1>n,则iii无右孩子,否则右孩子编号为2∗i+12*i+12∗i+1
满二叉树
一棵深度为kkk且有2k−12^k-12k−1个节点的二叉树
完全二叉树
除第kkk层以外都为满二叉树,且kkk层从左往右连续
二叉搜索树
左子树均小于根节点
右子树均大于右节点
A叉树
有(ak−1)/(a−1)(a^k-1)/(a-1)(ak−1)/(a−1)
前序遍历
先访问根节点,再访问左子树,最后访问右子树
中序遍历
先访问左子树,再访问根节点,最后访问右子树
后序遍历
先访问左子树,再访问右子树,最后访问根节点
恢复
中序+任意一种遍历方式可以确定唯一一棵二叉树,前序+后序不可以
中序后序求前序