AKSZ-图论

「仆人」阿蕾奇诺

2024-06-16 17:40:36

发布于：广东

7阅读

0回复

0点赞

树和图

图

无向图

双向走

有向图

有确定的方向
用尖括号<>表示
有向图的基图:去方向后得到的无向图

边权

边的价值

G(V,E)
Graph Vertex Edge

V：顶点结合
E：边集合

完全图

无向图中任意一对顶点都有一条边
n阶完全图边数:n*(n-1)/2
n阶有向完全图边数:n*(n-1)

稀疏图

边的数目相对较少
远小于n*(n-1)

稠密图

边的数目相对较多
接近于（有向）完全图

自环

一个节点连接到自身的边

重边

两个节点之间存在多条边

简单图

一种无向图或有向图，其中不存在自环或重边

多重图（反之）

连通图

无向图中任意一对顶点都是联通的

强连通图

连通图中可双向联通

树

有n个顶点
n-1条边
n == 0时成为空树
树有且只有一个特定节点——根节：root
度为零的节点为叶子节点，非零的为分支节点，节点拥有的子树数量为树的度

根节点没有前驱，其余每个节点都有唯一的一个前驱节点，每个节点有0或多个后继节点

#include <bits/stdc++.h>
using namespace std;
const int n = 1e5+5;
int fa[n]; 
vector<int>V[n];
int main(){
	//1.父亲表示法
	//每个节点只记录父亲的编号
	
	//1根节点，fa[1] = 0;
	//fa[2] = 1,fa[3] = 1;
	
	for(inr i = 0;i<n-1;i++){
		
		int u,v;
		cin>>u>>v;
		fa[u] = v;
	} 
	
	//孩子表示法
	
	for(int i = 1;i<=n-1;i++){
		int x;
		cin>>x;
		for(int j = 0;j<x;j++){
			int t;
			cin>>t;
			v[i].push_back(t);
		}
	} 
	
    return 0;
}

#bfs

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int fa[maxn]; 
vector<int>V[maxn];
int maxu,maxstep = 0;
int vis[maxn];
struct node{
	int u;
	int step;
};
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;
    return 0;
}

#dfs

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int fa[maxn]; 
vector<int>V[maxn];
int maxu,maxstep = 0;
int vis[maxn];
struct node{
	int u;
	int step;
};
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;
    return 0;
}