树和图的存储
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了树和图的存储，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2974字，纯文字阅读大概需要5分钟。
内容图文
1、树和图的存储
有两种存储方式，树是一种特殊的图，无环连通图。所以只讨论图的存储方式。
图分为有向图和无向图。无向图a—b可以看作有向图a\(\to\)b和b\(\to\)a，所以无向图也可以看作一种特殊的有向图。
这样只需要考虑有向图就可以了。
1.1 邻接矩阵存储
其实就是开了一个二维数组。g[a,b]就存储a\(\to\)b这条边的信息，如果有权重，他就是权重值，没有权重就是bool值，临界矩阵不能存储重边，只能保留一条。空间复杂度O(\(n^2\))，适合存储稠密图。
1.2 邻接表存储
每一个节点就是一个单链表，就是多个单链表。每个点的单链表存储这个点可以走到哪个点。
如下图：
转换成邻接表就是：
如果我们想插入一条新边\(2\to3\)就找到2对应的单链表节点，把3插入到里面去。
1.2.1 DFS遍历习题：树的重心
1.2.2 代码实现
这道题的树的构成是这样的：
如果把1删除，那么剩余3个连通块，最大数量是4，把2删除，也剩余3个连通块，最大数量是6，简单分析可知删除节点1就得到了答案。
做法：对于每个点都求出把这个点输出后其余所有连通块的最大值进行对比找出最小的就可以了。
这时就要用到树的DFS了，因为树的DFS可以算出每一个子树的大小。比如我们要算4的子树的大小，首先递归处理完3和6，我们就可以统计出3和6的点数，3的点数加上6的点数再加上4自己就是总共的点数。
如何算把4删除后的最大值呢？如下图：
把4删掉后分成了3个部分，所有子节点的部分可以从下往上返回回来，上面的一部分只需要用\(n-size_4\)就可以了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = N * 2;
int n;
// h,头，每个节点的值，ne每个节点的next指针，idx当前节点
int h[N], e[M], ne[M], idx;// 无向图存储两条边，所以开2N大小
int ans = N;
bool st[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; // 已经搜过了
// size指每一个连通块size的最大值，sum指当前子树大小
int size = 0, sum = 1; // 当前这个点也是一部分，所以从1开始
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (st[j]) continue;
int s = dfs(j); // 当前子树大小，当前这个子树也是一个连通块
size = max(size, s);
sum += s; // 当前这个子树也是以u为根节点的子树的一部分
}
size = max(size, n - sum); // 在当前根节点上面的连通块大小n-sum
ans = min(ans, size);
// sum 是你选中的点的子树的节点数，你当前点为根的树的数目是sum+1
return sum;
}
int main()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs(1);
printf("%d\n", ans);
return 0;
}
1.2.3 BFS遍历习题：
1.2.4 代码实现
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int bfs()
{
memset(d, -1, sizeof d);
queue<int> q;
d[1] = 0;
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (d[j] == -1)
{
d[j] = d[t] + 1;
q.push(j);
}
}
}
return d[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
cout << bfs() << endl;
return 0;
}
内容总结
以上是互联网集市为您收集整理的树和图的存储全部内容，希望文章能够帮你解决树和图的存储所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。