tips:树是一种特殊的图 是无环连通图

有向图边有方向 如a->b
无向图边没有方向 a<->b
无向图是特殊的有向图 我们就先理解有向图的储存

1.邻接矩阵 其实就是一个二维数组 g[a][b]就存储a->b 有权重就是权重 没有就是bool值表示有无边 邻接矩阵不能有重边 只能保留一条 这个比较浪费空间

2.邻接表 就是n个节点 每个都开单链表 就跟哈希拉链法一样

[树的存储] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;

const int N=10010,M=N*2;

int h[N],e[N],ne[N];  //h链表头 e节点的值 ne指每个节点的next指针 与之前的单链表一样

void add(int a, int b) //添加一条边a->b
{
    e[idx]=b; //新用到的节点值为b
    ne[idx]=h[a];//这个节点的next指针指向a所在点的链表原本的头结点
    h[a]=idx; //更新头节点
    idx++;
}

int main()
{
    memset(h,-1,sizeof h); //和单链表head初始化-1一样 现在把所有链表都初始化
}

[树的重心(dfs用法)] [c++]
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
#include<bits/stdc++.h>
using namespace std;

const int N=10010,M=N*2;
bool st[N]; //存有没有遍历过

int h[N],e[N],ne[N]; 

void add(int a, int b) 
{
    e[idx]=b; 
    ne[idx]=h[a];
    h[a]=idx; 
    idx++;
}

int main()
{
    memset(h,-1,sizeof h); 
}

void 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);
    }
}