AKSZ-图论
2024-06-16 14:37:38
发布于:广东
图
图 (Graph) 是由若干个给定的点、及若干条连接两个顶点的边所构成的图形,这种图像通常用来描述描述某些事物之间的某种特定的关系
图常用表示, (Vertex) 为顶点集合, (Edge) 为边集合
顶点的个数称为图的阶
图是图论的研究对象
图论这一部分的知识点,侧重图结构的描述、图结构的存储和遍历、少量剧本的图论算法的实现
分类
无向图:可以直接由某一状态回到前一个状态
有向图:不能直接由某一状态回到前一个状态,和为两条有向边
有向图的基图:忽略有向图所有边的方向, 得到的无向图称为该有向图的基图
完全图和有向完全图
完全图(Complete Graph):无向图中任何一对顶点之间都有一条边
一个阶的完全图有条边
有向完全图(Directed Complete Graph):有向图中任何一对顶点之间都有两条有向边
稀疏图和稠密图
稀疏图:边的数目相对较少(远小于)
稠密图:边的数目相对较多(接近于完全图或者完全有向图)
平凡图和零图
平凡图:只有一个顶点的图
零图:没有边的图
自环和重边
自环:一个顶点
重边:两个顶点有多条边
权
带权图(Weighted Graph):边上带有权值的图
权:可以抽象的理解为金钱、时间、长度
简单图和多重图
简单图(Simple Graph):一种无向图或有向图, 其中不存在自环和重边
多重图(Multi Graph):一种无向图或有向图, 其中存在自环和重边
连通
路径:在图中, 从顶点出发, 沿着一些边经过顶点 到达顶点, 则称顶点序列
连通:若从顶点到有路径, 则称顶点和是连通的
连通图:如果无向图中任意一对顶点都是连通的,则称此图为连通图
强连通图:如果有向图中,若每一对顶点和, 即存在到的路径,也存在到的路径,则称此图为强连通图
度
- 图中顶点的度:与该顶点相连的边的数量
- 在无向图中,一个顶点的度数就是和该顶点相连的边的数量
- 在有向图中,一个顶点的度数就是该顶点的入度和出度的和。(入度就是指向该的的边的数量,出度是从该顶点出发的边的数量)
图/树
树(Tree):如果一个无向连通图中不存在回路,则称这种图为树
树是一种特殊的图
树也可以从数据结构的角度去定义,涉及的术语有 子树、孩子结点、度、层次
树作为一种非线性的数据结构,是由个结点组成的有限集合
如果时,称为空树,如果,树有且只有一个特点的结点——根节点(root)
度:结点拥有的子树的数量为结点的度,度为的结点为叶子结点,度不为的结点为分支结点
树的前驱和后继:除根结点没有前驱外,其余结点都有唯一的一个前驱结点。每个结点可以有个或多个后继结点。结点的直接后继称为结点的孩子,结点的直接前驱称为结点的父亲
树中结点的层次:书中根节点为第一层,根节点的孩子为第二层,以此类推。书中结点的最大层次称为树的深度(高度)
注意:部分题目中的根节点为第层
C++建树
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int fa[maxn];
vector<int> cd; //cd[i],儿子的编号是那些
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//1 父亲表示法
//每个结点只记录父亲的编号
//fa数组表示
for(int i = 0; i < n - 1; i++){
int u, v; //结点
cin >> u >> v;
fa[u] = v;
}
//2 孩子表示法
//cd数组表示
for(int i = 1; i < n - 1; i++){
int x; //多少结点
cin >> x;
for(int j = 0; j < x; j++){
int t;
cin >> t;
cd[i].push_back(t);
}
}
return 0;
}
求树直径(距离最远的两个点)
bfs与dfs模板
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
vector<int> V[maxn];
int vis[maxn]; //判断结点不重复访问
int maxu, maxs;
struct node{
int u; //结点的编号
int step;
};
int bfs(int x){
maxu = x, maxs = 0;
queue<node> q;
vis[x] = 1;
q.push(node{x, 0});
while(!q.empty()){
node tmp = q.front();
q.pop();
if(tmp.step > maxs){
maxs = tmp.step;
maxu = tmp.u;
}
//走到下一个结点
for(int i = 0; i < V[tmp.u].size(); i++){
int v = V[tmp.u][i]; //结点编号
if(vis[v]) continue;
vis[v] = 1;
q.push(node{v, tmp.step + 1});
}
}
}
void dfs(int u, int pre, int step){
if(step > maxs){
maxu = u;
maxs = step;
}
for(auto v : V[u]){
if(v == pre) continue;
dfs(v, u, step + 1);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++){
int u, v;
cin >> u >> v;
V[u].push_back(v);
V[v].push_back(u);
}
bfs(1); //范围距离1最远的结点, 得到距离1最远的结点
bfs(maxu); //最远的点出发就可以到达直径
//dfs(1, 0, 0)
//maxs = 0;
//dfs(maxu, 0, 0)
cout << maxs << endl;
return 0;
}
二叉树
二叉树(Binary Tree) 是一种度数最大为的树,即二叉树的每个结点最多有两个子节点,每个子节点分别称为左子树、右子树
链也是一种树
一颗深度为且有个结点的二叉树称为满二叉树
若二叉树的高度为,则共有层,除第层外,其他各层~的结点数都达到最大个数,且第层缺少的结点是从左到右并连续的,这就是完全二叉树
对任意一颗二叉树,如果其叶子结点的数量为,度为2的结点数为,则一定满足
证明:1、。2、孩子结点有,所以。由此可得
具有个结点的完全二叉树的深度为(是向下取整)
如将一颗具有个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号,则有以下关系:
- 若,则结点为根,无父结点
- 若,则的父结点编号为
- 若,则无左孩子,否则其左孩子编号为
- 若,则无右孩子,否则其右孩子编号为
二叉搜索树
二叉搜索树(Binary Search Tree) 是一种应用十分广泛的二叉树
二叉搜索树具有的性质:
- 若左子树不空,则左子树上所有的结点的值均小于它根结点的值
- 若右子树不空,则右子树上所有的结点的值均大于它根结点的值
- 左,右子树也是一个二叉搜索树
满A叉树结点
这里空空如也
有帮助,赞一个