AKSZ-树和图
2024-06-16 16:33:31
发布于:广东
树和图
图
有权图,无权图,有向图(用尖括号<>),无向图(用圆括号())
边上的数字称为边权
用顶点表示事物,用连接两个点的边表示相应两个事物具有某种联系
图是图论的研究对象
图通常用表示,为顶点集合,为边集合( )
即
=
顶点的个数称为图的阶
完全图:无向图中任何一对顶点之间都有一条边
完全图边数为:
=
其中为顶点个数
稀疏图:边的数目相对较少
稠密图:边的数目相对较多
平凡图:只有一个顶点的图
自环:一个结点连接到自身的图
重边:两个结点之间存在多条边
简单图:一种无向图或有向图,其中不存在自环和重边
复杂图:一种有向图或无向图,其中存在自环或重边
连通:若从顶点到有路径,则称顶点和是联通的
连通图:如果无向图中任意一对顶点都是连通的,则称此图为连通图
强连通图:如果有向图中,若每一对顶点和,即存在从到的路径,也存在到的路径,则称此图为强连通图
度:与该顶点相连的边的数量
入度:指向该顶点的边的数量
出度:从该顶点出发的边的数量
树
树:不存在回路的无向连通图
度:结点拥有的子树的数量
叶子结点:度为的结点
树的度:所以结点中度的最大值
孩子:结点的直接后继
父亲:结点的直接前驱
兄弟:有同一个双亲的不同结点
树的输入
#include<bits/stdc++.h>
using namespace std;
vector<int>V[N];//v[i] i,儿子编号是哪些
int main(){
//1.父亲表示法:每个结点只记录父亲的编号
//fa数组表示
//根节点:fa[1]=0;
//fa[2]=1,fa[3]=1;
for(int i=0;i<n-1;i++){
int u,v;
cin>>u>>v;
fa[u]=v;
}
//2.孩子表示法
for(int i=1;i<=n-1;i++){
int x;cin>>x;
for(int j=0;i<x;j++){
int t;cin>>t;
v[i].push_back(t);
}
}
return 0;
}
层次:根节点为第一层,根节点的孩子为第二层,以此类推
树的深度/高度:树中结点的最大层次
树的直径
https://vjudge.net/problem/SPOJ-PT07Z
1.BFS
#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
vector<int>V[maxn];
int maxu,maxstep;
struct node{
int u;//结点编号
int step;
};
int vis[maxn];//判断结点不重复访问
void bfs(int x){
maxstep=0;maxu=0;
queue<node>q;
memset(vis,0,sizeof(vis));
vis[x]=1;
q.push(node{x,0});
while(!q.empty()){
node tmp=q.front();
q.pop();
if(tmp.step>maxstep){
maxstep=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});
}
}
}
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);
}
bfs(1);//范围距离1 最远的结点 得到距离1最远的点
bfs(maxu);//最远的点出发就可以到达直径
cout<<maxstep<<endl;
return 0;
}
2.DFS
#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
vector<int>V[maxn];
int maxu,maxstep;
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);
}
maxstep=0;
dfs(1,0,0);
maxstep=0;
dfs(maxu,0,0);
cout<<maxstep<<endl;
return 0;
}
二叉树
二叉树:度数大于二的树,即二叉树的每一个结点最多有两个子结点,每个结点的子结点分别称为左孩子,右孩子
满二叉树:一棵深度为k且有 个结点的二叉树
完全二叉树:若二叉树的高度为,则共有层,除第层外,其他各层~的结点树都到底最大个数,且第层缺少的结点是从右到左连续的
二叉搜索树:是一种应用非常广泛的二叉树,又称二叉查找树,二叉排序树
层数为的满a叉树的结点个数n:
对任意一棵二叉树,如果其叶子结点的数量为,度为2的结点树为,则一定满足
具有个结点的完全二叉树的深度为
如将一棵有个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号1,2……,则有以下关系:
1.若,则结点为根,无父结点
2.若,则i的父结点编号为
3.若,则无左孩子,否则其左孩子编号为
4.若,则无右孩子,否则其右孩子编号为
先序遍历:首先访问根结点遍历左子树,最后便利右子树。在遍历左,右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树,如果二叉树为空则返回(后序为左>右>根,中序为左>根>右)
中序+另外任意一种遍历方式,可以确定唯一一棵二叉树。先序遍历与后序遍历不一定能确定唯一一个二叉树
重建二叉树:先看先序的首项或后序的尾项确定根结点,再根据中序的根节点分隔左右子树的特点确定左右子树有哪些,以此类推直至确定整个二叉树
已知中序后序求前序
#include<bits/stdc++.h>
using namespace std;
int n,a[200005],b[200005],c[200005],x;
void f(int l1,int r1,int l2,int r2)//在中序数组的l1,r1,后序数组中的l2,r2
{ //边界
if(l1==r1){
cout<<a[l1]<<" ";
return;
}
//递归划分
int root=b[r2];//找到根
int pos=c[root];
cout<<root<<" ";
int len1=pos-l1;
if(pos-1>=l1)f(l1,pos-1,l2,l2+len1-1);//递归左子树
int len2=r1-pos;
if(r1>=pos+1)f(pos+1,r1,r2-len2,r2-1);//递归右子树
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
c[a[i]]=i;//位置
}
for(int i=0;i<n;i++){
cin>>b[i];
}
f(0,n-1,0,n-1);
return 0;
}
这里空空如也
有帮助,赞一个