树形结构基本模板

发表于 | 阅读次数:
字数统计: 915 字

树形结构是图论中的一种特殊情况, 可以说树就是一种特殊的图结构. 树的定义是这样的, 如果一个图中一共有n个顶点, 并且有且只有n-1条边, 这样的图被称之为树.

根据树的性质, 我们可以得出几个简单的结论:

  1. 树中不会出现环
  2. 没有父节点的节点称为根节点
  3. 每个节点有零个或多个子节点
  4. . . .

根据树的一些性质我们可以求一些树的基本特征:

  1. 树的直径
  2. 树的DFS序
  3. 树的各点子树大小
  4. 树上各点的深度
  5. 树的重心
  6. 树的Topsort

下面是这些特征的定义:

  1. 一棵树的直径就是这棵树上的一条最长路径
  2. 树的DFS序指的是在对一颗树先序遍历的顺序
  3. 每个点子树的大小指的是各点下所有的字节点的个数
  4. 每个点的深度是指, 如果规定根节点的深度为1的话, 那么每个节点的深度等于他的父节点的深度加一
  5. 一颗树的重心指的是如果把一个点删除的话, 原来的树形成的几个子树中最大的那一颗子树的大小最小的那一个点就是树的重心
  6. 拓扑序(Topsort)指的是在一张有向无环图(DAG) G中, 将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。

以上的这些性质基本上都可以用搜索, 或者DP的方法来求出,现在总结一下这些基本特征的代码,来加强一下记忆

树的直径:(dp求法)

1
2
3
4
5
6
7
8
9
10
11
int d[maxn], ans;//ans 中存储的即为树的直径的长度
void dp(int x) {
    vis[x] = true;
    for (int i=head[x];i;i=Next[i]) {
        int y=ver[i];
        if (vis[y]) continue;
        dp(y);
        ans = max(ans, d[x] + d[y] + edge[i]);
        d[x] = max(d[x], d[y] + edge[i]);
    }
}

树的DFS序:

1
2
3
4
5
6
7
8
9
10
void dfs(int x) {
    a[++m] = x;
    vis[x] = true;
    for (int i=head[x];i;i=Next[i]) {
        int y=ver[i];
        if (vis[y]) continue;
        dfs(y);
    }
    a[++m] = x;
}

树的各点子树的大小:

1
2
3
4
5
6
7
8
9
void  dfs(int x) {
    vis[x] = true; size[x] = 1;
    for (int i=head[x];i;i=Next[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dfs(y);
        size[x] +=  size[y];
    }
}

树上各点的深度:

1
2
3
4
5
6
7
8
9
void dfs(int x) {
	vis[x] = true;
    for (int i=head[x];i;i=Next[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        d[y] = d[x] + 1; //根节点的深度为1
        dfs(y);
    }
}

树的重心:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int x) {
    vis[x] = true;
    size[x] = 1;
    int max_part = 0;
    for (int i=head[x];i;i=Next[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dfs(y);
        size[x] += size[y];
        max_part = max(max_part, size[y]);
    }
	max_part = max(max_part, n-size[x]);//没有看懂这句话的意思
    if (max_part < ans) {
        max_part = ans;
        pos = x;//pos中存的即为重心的标号
    }
}

树的Topsort:

1
2
3
4
5
6
7
8
9
10
11
12
13
void Topsort() {
    queue<int> q;
    for (int i=1;i<=n;++i)
        if (du[i] == 0) q.push(i);
    while(!q.empty()) {
        int x = q.top(); q.pop();
        a[++cnt] = x;//a中所存的即为经过Topsort的序列
        for (int i=head[x];i;i=Next[i]) {
			int y = ver[i];
            if (--du[y] == 0)  q.push(y);
        }
    }
}

以上是树的一些常用操作, 这些性质可以用来描述这颗树.还有一些关于树的高级操作下次再写