Processing math: 100%
0 Star 2 Fork 0

米糖/杂七杂八

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
bot
cv
fabric-example-mod-1.18
gaaaaaaaame
moreblocks
redpanda
spider
每日一小块题
.gitignore
Linux.md
README.md
Web.md
cpp入门.md
fabric-example-mod-1.16.zip
fabric-example-mod-1.18.zip
java.md
数据库.md
树及dfs和bfs.md
算法.md
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
树及dfs和bfs.md 3.55 KB
一键复制 编辑 原始数据 按行查看 历史
米糖 提交于 2年前 . Update

数据结构-树

定义

一个没有固定根结点的树称为无根树 无根树有几种等价的形式化定义:

  • n个结点, n1条边的连通无向图
  • 无向无环的连通图
  • 任意两个结点之间有且仅有一条简单路径的无向图
  • 没有环,且在任意不同两点间添加一条边之后所得图含唯一的一个环

在无根树的基础上,指定一个结点称为,则形成一棵有根树

延申名词

  • 森林:图中每个连通块都是树
  • 生成树:在n个点的图中选择n1条边连接n个点
  • 无根树的叶结点:度数不超过1的结点
  • 度:这个点出边和入边数量的和,无向边一条视为度数为2
  • 父亲结点:从这个结点到根的最短路径上的除自己之外的第一个点
  • 祖先结点:从这个结点到根的最短路径上的除自己之外的剩余点
  • 子结点:除父亲结点外相连的其他点
  • 结点的深度:从这个结点到根节点的最短路径经过的边数
  • 树的高度:所有结点深度的最大值
  • 完整二叉树:每个结点的子节点数量都为0或2的树
  • 完全二叉树:只有最后两层可以不完整(不是每个节点有两个子节点),且每个只有一个子节点的节点的子节点都靠左
  • 完美二叉树:除叶子节点,其他节点都有两个子节点
  • 先序遍历:按照根左右的顺序遍历树
  • 中序遍历:按照左根右的顺序遍历树
  • 后序遍历:按照左右根的顺序遍历树
  • 树的直径:树上任意两节点之间最长的简单路径
  • 树的重心:对于树上的每一个点,计算其所有子树中最大的子树节点数,这个值最小的点

https://oi-wiki.org//graph/tree-basic/

树的构建

  • vector存边
int u, v;
int n = 5;
int edge = n - 1;
while(edge--){
	cin >> u >> v;
	v[u].push_back(v);
	v[v].push_back(u);
}
  • 链式前向星存边
int head[N], ne[N], to[N], we[N], idx;

void add(int u, int v, int w){
	we[idx] = w;
	to[idx] = v;
	ne[idx] = head[u];
	head[u] = idx++;
}
int u, v, w;
int n = 5;
int edge = n - 1;
while(edge--){
	cin >> u >> v >> w;
	add(u, v, w);
	add(v, u, w);
}

树的遍历

  • dfs(深度优先搜索)
void dfs(int u, int pre){
	for(int i = 0; i < edge[u].size(); ++i){
		int v = edge[u][i];
		if(v != pre){
			dfs(v, u);
		}
	}
	// for(auto v : edge[u]){
	// 	if(v != pre){
	// 		dfs(v, u);
	// 	}
	// }
	cout << a[u] << endl;
}
void dfs(int u, int pre){
	for(int i = head[u]; i != -1; i = ne[i]){
		int v = to[i];
		int w = we[i];
		if(v != pre){
			dfs(v, u);
		}
	}
	cout << a[u] << endl;
}
  • 全排列
void dfs(int depth){
	if(depth > n){
		for(int i = 1; i <= n; ++i) printf("%d ", a[i]);
		puts("");
		return;
	}
	for(int i = 1; i <= n; ++i){
		if(!isUsed[i]){
			isUsed[i] = true;
			a[depth] = i;
			dfs(depth + 1);
			isUsed[i] = false;
		}
	}
}
  • 函数:next_permutation(st, ed);

  • bfs(广度优先搜索)

void bfs(int u){
	queue<int> q;
	q.push(u);
	isVisit[u] = true;
	while(!q.empty()){
		u = q.front();
		q.pop();
		printf("%d ", u);
		for(auto v : edge[u]){
			if(!isVisit[v]){
				isVisit[v] = true;
				q.push(v);
			}
		}
	}
}
while(!q.empty()){
	//起点
	for(int i = 0; i < 4; ++i){//四个方向
		x = //起点x + dx[i];
		y = //起点y + dy[i];
		if( <= x && x <= && <= y && y <= ){//边界
			if(!isVisit[x][y]){
				//标记并放入队列
			}
		}
	}
}
  • AcWing的视频讲解
  • 第三章 搜索与图论(一)
  • dfs:01:43
  • bfs:54:08
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/ricesugar/mixed.git
git@gitee.com:ricesugar/mixed.git
ricesugar
mixed
杂七杂八
master

搜索帮助

0d507c66 1850385 C8b1a773 1850385