• 树的邻接表存储法


    树可以使用链式存储结构,也可以使用邻接矩阵和邻接表
    一、邻接矩阵
    我们可以使用一个n×n的bool数组mp,mp[x][y]为true,则表示从x到y存在有向边,为false则表示x到y不存在有向边。
    邻接矩阵存储代码如下:
    bool mp[MAXN][MAXN];
    void link(int x,int y)
    {
    mp[x][y]=true;
    }
    二、邻接表
    同样,我们可以采用邻接表来存储一个点连出的多条树边,
    如下图:
    在这里插入图片描述
    邻接表的代码如下:
    int m;
    int fi[MAXN];//存储结点儿子个数
    int to[MAXN];//存储结点的具体每个儿子
    int ne[MAXN];//是结点儿子的链接,指向该节点的下一个儿子
    void link(int x,int y)
    {
    to[++m]=y; ne[m]=fi[x]; fi[x]=m;
    }

    to[ ]是存储具体的儿子,ne[ ]指向该儿子的下一个儿子,fi[x]
    始终指向x节点最后插入的一个儿子。一定要注意每次向前插入一个儿子

    使用c++模板std::vector,我们可以更方便的存储。
    vector g[MAXN];
    void link(int x, int y)
    {
    g[x].push_back(y);
    }

    有根树的深度优先遍历代码如下:
    int m,fi[MAXN] , to[MAXN2] , ne[MAXN2];
    void dfs(int x)
    {
    visit(x); //访问儿子之前做一下事情
    for(int i=fi[x]; i ; i=ne[i]) dfs(to[i]; //访问x的儿子
    …//在访问x的儿子后做一下事情
    }
    main()
    {

    dfs(root,0); //主程序调用,一般把根的父亲设置为0或-1

    }

    例题:求树中每棵子树的大小以及每个结点的深度(假设结点1为根)

    输入格式:
    第1行:一个整数n,表示树的结点的个数。
    接下来n-1行,每行两个整数x和y,表示结点x和结点y之间有一条边,但不保证x是y的父亲

    输出格式:
    共n行,第i行为两个正整数,分别表示以结点i为根的子树大小和该结点i的深度。

    分析:每个点的子树大小为它的所有儿子的子树大小之和再加1。每个点的深度为它的父亲的深度再加1。

    #include
    using namespace std;
    const int MAX=100005;
    int head[MAX],depth[MAX],size[MAX];
    struct
    {
    	int nxt,to;
    }edge[MAX];
    int cnt=1;
    void add_edge(int u,int v)
    {
    	edge[cnt].to=v;
    	edge[cnt].nxt=head[u];
    	head[u]=cnt++;
    }
    int dfs(int x,int h)
    {
    	depth[x]=h;
    	int lu=1;
    	for(int i=head[x];i;i=edge[i].nxt){
    		int v=edge[i].to;
    		if(depth[v]) continue;
    		lu+=dfs(v,h+1);
    	}
    	return (size[x]=lu);
    }
    int duru()
    {
    	int T,m1,m2;
    	scanf("%d",&T);
    	for(int i=1;i<=T-1;i++){
    		scanf("%d%d",&m1,&m2);
    		add_edge(m1,m2);
    		add_edge(m2,m1);
    	}
    	return T;
    }
    void shuchu(int T)
    {
    	for(int i=1;i<=T;i++){
    		cout<<depth[i]<<' ';
    	}
    	cout<<endl;
    	for(int i=1;i<=T;i++){
    		cout<<size[i]<<' ';
    	}
    }
    int main()
    {
    	int num=duru();
    	dfs(1,1);
    	shuchu(num);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
  • 相关阅读:
    【OpenCV 例程 300篇】247. 特征检测之最大稳定极值区域(MSER)
    Java学习-第一阶段-第一节:Java概述
    案例分享 | 金融行业运维数字化转型路径探索与实践
    非零基础自学Java (老师:韩顺平) 第14章 集合 14.10 Set 接口实现类 - HashSet
    Vue搭建移动端h5项目(已开源,附带git地址)Vant+Vue Router+Vuex+axios封装+案例交互+部分代码说明
    倍福TwinCAT3 NCI在NC轴界面中的基本配置和测试
    CMake Cookbook笔记(11/19未完待续)
    【数据结构】3000字剖析链表及双向链表
    七、互联网技术——SQL查询
    NPM详解
  • 原文地址:https://blog.csdn.net/hwdn3000/article/details/117334229