树和图的存储
树是一种特殊的图,“无环连通图”
所以只需要考虑图的存储方式即可!
图分为有向图和无向图。
有向图
:有方向的图,每个节点有单方向”$a \rightarrow b$”
无向图
:没有方向,也可以理解为双向!
建立边的时候,可以建两个边:”$a \rightarrow b$”,”$a \leftarrow b$”
因此,无向图可以看作特殊的有向图。
因此只需要考虑有向图如何存储即可!
总结:
- 树是一种特殊的图。考虑树和图的存储时,只需要考虑图的存储即可。
- 无向图是特殊的有向图。考虑无向图和有向图的存储时,只需要考虑有向图即可。
有向图的存储方式有两大类:邻接矩阵、邻接表。
邻接矩阵
g[a,b]
:存储从节点a到b的信息!
- 如果这条边有权重,g[a,b]就存权重
- 如果没有权重,就存储一个布尔值,表示这两个节点之间有没有边!
- 如果有重边的话,一般保留一条边就可以了。(g[a,b]不能存储重边信息,求最短路可以保留最短边)
时间复杂度为$O(n^2)$,适合存储稠密图。
邻接表
每个节点都存储一个单链表,这个单链表存储当前节点可以到达哪些节点
。
如下图:一个有向图,有4个节点,每个节点存储一个单链表。这些单链表的节点存储这个点可以到达哪些点,不考虑顺序。
新增边的操作:
在2、3节点插入一条边,由2指向3。
只需在2号节点的头节点插入这个点即可。
- 先由这个点指向头节点的next节点。
- 再由头节点指向这个点。
单链表的插入参考题解:单链表
数和图的遍历方式有两种:深度优先遍历、宽度优先遍历。
树的重心(深度优先遍历)
深度优先遍历的方式
找一个起点,”一条路走到黑”。
树的重心题意理解
给定一颗树,树中包含 n 个结点(编号 1∼n)和 n−1 条无向边。
请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
本题是无向图,建边时:每条边建两个相反方向的边。
样例模拟,理解重心:
删除的时节点1:
删除的是节点4:
最终遍历的删除每个节点,求连通块的最大值。再把这些最大值放在一起比较,求其中的最小值。
本题最终答案ans = 4
那如何求得每个连通块中点的数量?
深搜过程中,可以统计每个子树点的数量!
因此,可以计算:删去某个点之后,剩余其他所有连通块中点的数量。
由于深度优先遍历、广度优先遍历每个点只会遍历一次,所以时间复杂度为$O(n + m)$,与点和边
成线性关系
。
深搜框架
首先对一些代码进行解释:
const int N = 1e5, M = 2 * N; // 数据范围是10^5。M在下面表示双向边,每个节点a->b,b->a
h[N]; // 存储每个节点链表的头节点
e[M]; // 存储每条边
ne[M]; // 存储每个节点的next节点是什么
idx; // 存储当前用到了哪个点
memset(h, -1, sizeof h); // 把n个节点链表的头节点都指向-1
void add(int a, int b) // a表示某个节点表示的链表,b表示要插入这个链表的节点
{
e[idx] = b; // 把当前要插的值存起来
ne[idx] = h[a]; // 把当前的节点指向头节点的下一个点
h[a] = idx; // 把头节点指向当前点
idx ++ ; // 当前点用过了,把可用的点挪到下一个位置
}
深搜框架:
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5, M = 2 * N;
int n;
int h[N], e[M], ne[M], idx;
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs(int u)
{
st[u] = true; // 把随便选的第一个点打上标记,表示已经搜索过了。
for (int i = h[u]; i != -1; i = ne[i] ) // 从每个节点链表的头节点开始,一直遍历到空节点
{
int j = e[i]; // 把链表中的节点,对应到要存储的图中表示的点
if (!st[j]) dfs(j); // 如果这个点没被遍历过,一条道走到黑
}
}
int main()
{
memset(h, -1, sizeof h);
dfs(1); // 随便找一个点,开始遍历
}
本题代码
本题用到的一些变量解释:
bool st[N]; // 一般题目,每个点只需要遍历一次。开一个bool数组存储这个节点是否被遍历过
本题代码:
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int n;
int h[N], e[M], ne[M], idx;
bool st[N];
int ans = N;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 返回以u为根的点的数量
int dfs(int u)
{
st[u] = true; // 把随便选的第一个点打上标记,表示已经搜索过了。
int sum = 1, res = 0; // sum记录以u为根的树,res记录所有连通块点的最大值。
for (int i = h[u]; i != -1; i = ne[i]) // 从每个节点链表的头节点开始,一直遍历到空节点
{
int j = e[i]; // 把链表中的节点,对应到要存储的图中表示的点
if (!st[j]) // 如果这个点没被遍历过,一条道走到黑
{
int s = dfs(j); // 以u为根的所有子树
res = max(res, s); // 比较选出点数最多的连通块
sum += s; // 以u为根的树,加上所有子树的节点数
}
}
res = max(res, n - sum); // 以u为根,上面的所有节点
ans = min(ans, res); // 比较:枚举删除所有点之后,最小的最大连通块
return sum; // sum是以u为根,所有点的大小
// 为什么不是return ans; 可能因为ans是通过比较直接获得,而sum是迭代获得,每次回溯时,需要这个值。
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1); // 随便找一个点,开始遍历
cout << ans << endl;
return 0;
}
图解代码中s、sum和res