树是一种特殊的图，与图的存储方式相同。

对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储：

  • 邻接矩阵：g[a][b] 存储边 a -> b

  • 邻接表

数组邻接表

存储

1
2
3
4
5
6
7
8
9
10
11
// 对于每个点 k，开一个单链表，存储 k 所有可以走到的点。h[k] 存储这个单链表的头结点,w[]存储权重
int h[N], e[N], w[N], ne[N], idx; 

// 初始化
idx = 0;
memset(h, -1, sizeof h);

// 添加一条边 a -> b
void addedge(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

遍历

时间复杂度 O(n + m)，n 表示点数，m 表示边数

深度优先遍历

1
2
3
4
5
6
7
8
int dfs(int u) {
    st[u] = true;	// st[u] 表示点 u 已经被遍历过
    
    for(int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if(!st[j])	dfs(j);
    }
}

广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
queue<int> q;
st[1] = true;	//表示 1 号点被遍历过
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(!st[j]) {
            st[j] = true;
            q.push(j);
        }
    }
}

vector 邻接表

存储

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Edge {
    int to, w;
};

vector<Edge> e[N];

// 初始化
for(int i = 0; i < N; i++)
    e[i].clear();

void addedge(int a, int b, int w) {
    e[a].push_back({b, w});
}

遍历

1
for(int i = 0; i < e[u].size(); i++)

链式前向星

存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Edge {
    int to, w;
    int ne;
}e[N];
int h[N], idx;

// 初始化
idx = 0;
memset(h, -1, sizeof h);

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

遍历

1
for(int i = h[a]; i != -1; i = e[i].ne)