树和图的存储和遍历

树和图的存储和遍历

树和图的存储

  1. 树是一种特殊的图（无环连通图），因此可以把树当作图来处理
  2. 图分为有向图(a->b)和无向图(a-b),但我们在算法题中如果遇到无向图，就直接（a->b）和（b->a）都建立，因此无向图就是特殊的有向图。
  3. 存储方式

（1）邻接矩阵 g[N][N]

  • g[a][b] = 0 代表 节点a->b没有边
  • g[a][b] = 1 代表 a->b有边
  • g[b][a] = 1 代表 b->a有边
  • g[a][b] = w 代表 a->b 该边的权重或者长度为w
  • 空间复杂度为O(n²)，适合存储稠密图

（2）邻接表

我们可以想一下对于任意一个结点u, 需要记录邻边的哪些信息。

这些信息应该包括这条邻边的终点，权重，以及下一条邻边的编号。

  • 每个点上都有一个单链表，存的是这个点可以走到哪些点
  • h数组的下标为结点的编号，e,ne数组的下标为边的编号，e数组的值为该边的终点，idx为边的编号
  • 邻接表初始化(先将h数组都置为-1再插入节点)
    1
    2
    3
    4
    5
    6
    7
    8
      // N代表点的个数，M代表边的条数
      // n个结点的树最多有n - 1条边，如果考虑无向边需要开两倍的n - 1来存储
    int h[N],e[2*N],ne[2*N],idx; //有n个单链表就有n个头节点
    memset(h,-1,sizeof(h)); //所有头节点都指向-1
      // h[i]：第 i 个节点的第一条邻边的 idx
      // e[idx]：存储 idx 这条边的终点，也就是与第 i 个节点相连的某一个点
      // ne[idx]：存储 与第 idx 条边 同起点的 下一条边的 idx，也就是邻接表中的下一个节点
      // idx：用于标识每条边的下标，存的是边的编号
  • 邻接表插入元素
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //有一条a->b的边 
    void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a]; // 新插入的边是插到链表头（头插法）
        h[a] = idx; //更新链表头
        idx++;
    }
    //树的边数等于节点数减1
    for(int i=0;i<n-1;i++){
        cin >> a >> b;
        add(a,b); add(b,a); //无向图
    }

树和图的遍历

遍历前要记得将头指针数组设置为 -1

对于树和图的遍历，不管是DFS还是BFS，因为每个点只会被遍历一次，所以时间复杂度与点和边的数量成线性关系，为O(n + m)

dfs 和 bfs 的不同
不同：

  1. 参数上：

    • void dfs(int u) //u代表层数 调用: dfs(1);
    • int bfs() //没有参数 调用：cout << bfs(); //在函数里面会返回需要的答案

  2. 变量上
    bfs 多了一个距离数组，初始时要将其置为-1 memset(d,-1,sizeof(d))
    dfs 用st[N] 当作状态数组 ，bfs可以使用距离数组 d 来充当状态数组 ;

  3. 代码结构
    dfs: 递归结构
    bfs: 初始化 + while(队列非空)的循环

相同：

  1. 初始化上
    要在开始时将当前正在访问的点设置为true

dfs

从节点编号1开始遍历，沿着节点的邻接表一路深搜

1
2
3
4
5
6
7
8
9
10
11
12
13
int st[N]; //状态数组,标记某个点是否被遍历到
void dfs(int u){
    st[u] = true;
    //遍历点u的所有出边
    for(int i=h[u];i!=-1;i=ne[i]){
        int b = e[i]; //b是该边终点
        if(!st[b]){
            dfs(b);
        }
    }
}

dfs(1);

例题：景区导游

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
54
55
56
57
//https://www.acwing.com/file_system/file/content/whole/index/content/11514015/
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n,k,a[N];
int h[N],e[2*N],ne[2*N],idx;
int w[2*N];
bool st[N];
int s[N]; //前缀和数组

void add(int u,int v,int t)//表示u->v 距离是t 把v添加到u里去
{
    for(int i=h[u]; i!=-1; i=ne[i]) {//这里要判断一下有没有边重复加
        if(e[i]==v) return; 
    }
    e[idx]=v;ne[idx]=h[u];h[u]=idx;w[idx]=t;idx++;//idx是v的下标 w[idx]表示u->v的距离
}
//求u->v的距离 u起点 v终点 d是起点到当前点的距离
int dfs(int u, int v, int d){
    st[u] = true; //先将起点设置为访问过了
    if(u == v) return d;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j = e[i];
        if(!st[j]){
            st[j] = true;
            //不能d += w[i] 再dfs(j,v,j,d)
            int ret = dfs(j,v,d+w[i]); //更新起点
            if(ret != 0) return ret;
            st[j] = false;
        }
    }
    return 0;
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    memset(h,-1,sizeof(h));
    for(int i=0;i<n-1;i++){
        int a,b,v;
        cin >> a >> b >> v;
        add(a,b,v); add(b,a,v);
    }
    for(int i=1;i<=k;i++){
        cin >> a[i];
    }
    for(int i=1;i<k;i++){
        memset(st,0,sizeof st);//每次dfs前都要清空一下st数组
        s[i] = s[i-1] + dfs(a[i],a[i+1],0);
        cout << s[i] << "\n";
    }
    
}

bfs

距离从小到大来遍历，取第一次遍历到的结果（每个点只遍历一次）。
遍历框架：

1
2
3
4
5
6
7
8
9
10
11
12
队列初始化
while(queue 不空)
{
    取出队头
    拓展队头所有邻点x
    if(x未遍历)
    {
        x入队
        d[x]=d[队头]+1;
    }
}
return d[n];

数组模拟队列常见操作 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N = 300 //这个地方要设置得大一点才行，因为队列在不断出队入队
PII q[N];  //这个地方要设置得大一点才行，因为队列在不断出队入队


queue<int> q;
int hh = 0, tt = -1;
//入队
q[++tt] = {} ; q.push()
//取队头
t = q[hh] ; q.top()
//出队
hh++ ; q.pop()
//判断是否非空
while(hh <= tt){} ; q.empty()

例题：图中点的层次
每条边长度都为1的最短路问题

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
int bfs(){
    //要把距离 数组初始为-1
    memset(d,-1,sizeof(d));
    //队列初始化
    int hh=0,tt=-1;
    q[++tt] = 1;
    d[1] = 0;
    while(hh<=tt){
        int t = q[hh];
        hh++;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j = e[i]; //编号为i的边 的终点

            //一旦某个点被访问了就不会再访问了，确保该点的最短距离不会被之前较长路径的距离所覆盖
            if(d[j] == -1){

                q[++tt] = j;
                // pre[j] = t;
                d[j] = d[t] + 1; //此处是d[t] + 1 ,不是d[i] + 1
            }
        }
    }
    // int x = n;
    // while(x!=1){
    //     cout << x << "\n";
    //     x = pre[x];
    // }
    return d[n];
}

LCA

定义：在有根树上，两点的祖先有公共部分，这些点叫做他们的公共祖先，而其中深度最深的点，叫作它们的最近公共祖先（LCA ，Lowest Common Ancestors）

求树上两个点距离的时候，可以预处理出每个点到根节点的距离，然后两点间最短距离公式为：dist[a->b] = dist[a]+dist[b]-2*dist[p]

算法 > 图论
#算法 #图论
树和图的存储和遍历
https://cs-lb.github.io/2024/04/04/搜索与图论/图的存储和遍历/
作者
Liu Bo
发布于
2024年4月4日
许可协议