AKSZ-图论
2024-06-16 17:30:40
发布于:广东
图
图是由若干个顶点和若干条链接两个顶点的边所构成的图形
图是图论的研究对象
表示
Gragh Vertex Edge
G(V,E)
V为顶点集合
E为边的集合
顶点的个数为图的阶
度(无向图)
与该顶点连接的边的数量
出度(有向图)
从该顶点出发点变得数量
入度(有向图)
指向该顶点的边的数量
有向图的基图
忽略有向图所有变得方向,得到的无向图称为该有向图的基图
完全图
无向图中任意以对顶点之间都有一条边
一个 n 阶的完全图含有条边
有向完全图
任何一对顶点 u 和 v ,都存在<u,v>和<v,u>两条边
稀疏图
边的数目较少
稠密图
边的数目较多
自环
一个节点链接到自身的边
重边
两个节点之间有多条边
简单图
不存在自环或重边的图
多重图
存在自环或重边的图
路径长度
路径中变得数目
连通
若从顶点 u 到 v 有路径,则称顶点 u 和 v 是连通的
连通图
无向图中任意一对顶点都连通
强连通图
如果有向图中,若每一对顶点 u 和 v ,既存在从 u 到 v 的路径,也存在 v 到 u 的路径,则称此图为强连通图
邻接矩阵储存
如果两个节点之间存在边,则数组中的元素为1,否则为0
树
非线性数据结构,由n个节点组成的有限集合
根节点
定义
如果一个无向连通图中不存在回路,则这种图称为树
度
节点拥有的树的数量为节点的树
度为 0 的节点为叶子节点
树的度为树中节点最大的度
树的前驱和后继
除根节点外都有前驱
每个节点都有0或多个节点
树中节点的层次
树的深度
求树直径模板(bfs)
https://www.spoj.com/problems/PT07Z/
#include<bits/stdc++.h>
#define ll long long
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 = x;
queue<node>q;
memset(vis,0,sizeof(vis));
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);//
bfs(maxu);
cout<<maxstep<<endl;
}
求树直径模板(dfs)
https://www.spoj.com/problems/PT07Z/
#include<bits/stdc++.h>
#define ll long long
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;
}
模板
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int fa[N];
vector<int>V[N];
int main(){
//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;i++){
int x;
cin>>x;
for(int j=0;j<x;j++){
int t;
cin>>t;
V[i].push_back(t);
}
}
}
二叉树(BT)
每个节点有两棵子树
性质
其叶子节点的数量为,度为2的节点数量为,则一定满足
具有个节点的完全二叉树的深度为向下取整
的父节点的编号为向下取整
若,则无左孩子,否则左孩子编号为
若,则无右孩子,否则右孩子编号为
满二叉树
一棵深度为且有个节点的二叉树
完全二叉树
除第层以外都为满二叉树,且层从左往右连续
二叉搜索树
左子树均小于根节点
右子树均大于右节点
a叉树
有
前序遍历
先访问根节点,再访问左子树,最后访问右子树
中序遍历
先访问左子树,再访问根节点,最后访问右子树
后序遍历
先访问左子树,再访问右子树,最后访问根节点
恢复
中序+任意一种遍历方式可以确定唯一一棵二叉树,前序+后序不可以
中序后序求前序
#include<bits/stdc++.h>
using namespace std;
int m[200005];
int b[200005];
int a[200005];
int posm[200005];
void f(int l1,int r1,int l2,int r2){
if(l1>r1){
return;
}
if(l2>r2)return;
int root=b[r2];//找根
int p=posm[root];
cout<<root<<' ';
int len1=p-l1;
int len2=r1-p;
f(l1,l1+len1-1,l2,l2+len1-1);//递归左子树
f(r1-len2+1,r1,r2-len2,r2-1);
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>m[i];
posm[m[i]]=i;
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
f(1,n,1,n);
}
这里空空如也
有帮助,赞一个