AKSZ-图论
2024-06-09 17:31:57
发布于:广东
AKSZ-第x课
图论
图分为有向图、无向图,有权图、无权图
图:G(V,E)
V=顶集 E=边集
顶点的个数是图的阶
把几组具体的联系转变为抽象的模型就是图论模型
=
有向图的基础就是无向图。
每个顶点之间都有边相连就是完全图
完全图公式:
但如果有向,就不用除以二
稀疏图和稠密图是用来看边的密度
对于n=1e5
边数<=1e5就算稀疏图
自环是自己连自己,重边就是有完全一致的边
边上有数字就是有权值
简单图就是没有自环和重边,相反则是多重图
平凡图就是只有一个点,零图就是没路
路径
从V(j)出发到V(i)就是路径
长度就是边数
若u到v有路径,则称他们是联通的
如果谁到谁都有路,就是连通图,有向则称为强连通图
树
n个顶点,必须联通,n+e条边
**根节点(root)**绝对固定
度
就是子节点数量
度为零是叶子节点,否则叫分支节点,一整棵树的度是度的最大值
前驱、后继、兄弟
对于一个点,它的父节点就是它的前驱,子节点就是后继,同父节点的几个节点就是兄弟
树的输入
#include<bits/stdc++.h>
using namespace std;
const int maxx=1e5+5;
int fa[maxx],n;
vector<int>V[N];
int main(){
cin>>n;
//1、父亲表示法
//每个节点只标父节点
int u,v;
for(int i=1;i<n;i++){
cin>>u>>v;
fa[u]=v;
}
//2、孩子表示法
int x;
for(int i=1;i<n;i++){
cin>>x;
for(int j=0;j<x;j++){
int t;cin>>t;
V[i].push_back(t);
}
}
return 0;
}
高度
高度就是根节点走到一个点所用的步数,+不+1看根节点深度
树中任意两个节点之间有且仅有一条简单路径
树的遍历
#include<bits/stdc++.h>
using namespace std;
const int maxx=10005;
vector<int>V[maxx];
int maxstep,maxu;
void dfs(int u,int pre,int step){
if(step>maxstep){
maxu=u;
maxstep=step;
}
for(auto v:V[u]){
if(v==pre) continue;
dfs(v,u,step+1);
}
}
int main(){
int n;cin>>n;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
V[u].push_back(v);
V[v].push_back(u);
}
dfs(1,0,0);
maxstep=0;
dfs(maxu,0,0);
cout<<maxstep;
return 0;
}
二叉树
每个节点都有两个子树
满二叉树
深度为k且有个节点
完全二叉树
若二叉树高度为k,除第k层外,(1~(k-1))的节点数都达到最大个数,且第k层有的点是从左到右并连续的,这就是完全二叉树
二叉搜索树
所字数所有节点都小于根节点,右边则大于
这里空空如也
有帮助,赞一个