AKSZ-图论
2024-06-09 17:47:58
发布于:广东
图
图是若干个给定的顶点,以及若干条连接两个顶点的边所构成的图形。这种图形通常用来描述
常用表示。某些事物之间的某种特定关系,用顶点代表事物,用连接两个顶点的边表示相应两个事物具有某种关系。
为顶点集合,为边集合。
图是图论的研究对象
顶点的个数叫做图的阶
相关定义
- 有向图的基图:忽略有向图所有边的方向得到的无向图
- 完全图:无向图中任何一对顶点之间都有一条边
- 有向完全图:有向图中任何一对顶点
u
和v
都存在<u,v><v,u>
两条有向边 - 稀疏图:边的数目相对少(远小于)
- 稠密图:边的数目相对多(接近于完全图或有向完全图)
- 平凡图:只有一个顶点的图
- 零图:边集合为空的图
- 自环:一个顶点连接到自身的边
- 重边:两个顶点之间有多条边
- 权值图:边带有全权值的图
- 简单图: 一种无向图或有向图,其中不存在自环与重边
- 多重图:一种无向图或有向图,其中存在自环与重边
- 路径:在图
G(V,E)
中从顶点出发,沿着一些边经过一些顶点,,,,……,到达顶点,则称顶点序列{,,,,……,,}为到的一条路径 - 联通:若从顶点u至v有路径,则称顶点u,v是联通的
- 如果无向图中任意一对顶点都是连通的,则称此图为连通图
- 如果有向图中任意一对顶点都是互相连通的,则称此图为强连通图
树
- 树:一个不存在回路无相连通图
- 树是一种特殊的图
- 树是一种非线性的数据结构,是由个节点组成的有限集合
当时,称为空树;如果,树有且只有一个根节点 - 树的前驱与后继:除根节点没有前驱外,其余每个节点都有唯一的一个前驱节点。每个节点可以有0或多个后继节点
- 节点的后继称为节点的的孩子,节点的之家前驱称为节点的父亲,有同一个父节点的不同节点互称兄弟
- 结点拥有的子树的数量叫做节点的度
树中节点的层次:树中根节点为第一层,根节点的孩子为第二层,以此类推……
树中节点最大层次乘坐是的高度。
注意:有些题中根节点是第0层
树的存储
父亲表示法:
//父亲表示法:每个节点只记录父亲的编号
//根节点为1,则fa[1]=0;fa[2]=1;fa[3]=1;
cin>>n;
for(int i=0;i<n-1;i++){
int u,v;
cin>>u>>v;
fa[u]=v;
}
孩子表示法
//孩子表示法(同上,节点存孩子)
for(int i=0;i<=n-1;i++){
int x;cin>>x;
for(int j=0;j<x;j++){
int t;cin>>t;
v[i].push_back(t);
}
}
特殊的树
二叉树(BT)
度数最大为2的树,即二叉树的节点最多有两个子节点,每个子节点分别被称为左孩子节点、右孩子节点,
每个子树分别被称为左子树、右子树
满二叉树:一棵深度为且有个节点的二叉树
完全二叉树:若二叉树的高度为,则共有层,除第层外,其他各层到的节点数都达到最大个数,
且层缺少的节点是从左到右并连续的,则称其为完全二叉树
二叉搜索树(BST)
二叉搜索树具有以下性质:
- 若任意结点的左子树不空,则左子树上所有结点的值均不大于它的根结点的值。
- 若任意结点的右子树不空,则右子树上所有结点的值均不小于它的根结点的值。
- 任意结点的左、右子树也分别为二叉搜索树。
这里空空如也
有帮助,赞一个