DFS & 树和图复习笔记

userId_undefined
请‎输‎‎‎‎‎入‎‎文‎‎本.
分支·分支解题者I/O·IO入门者

2026-08-15 13:54:44

发布于：上海

51阅读
0回复
0点赞

由于帖主作为你 GO 最区的区，连 DFS 、树和图都忘光了，导致很多题目都不会，所以帖主发布了一个复习笔记

搜索优化：剪枝

  • 将一些中途发现已经不可能的情况直接跳过

看题
P2089
看我炒鸡打卤

namespace HQ{
    #define int long long
    void init(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);}
    inline int read(){int num=0,sign=1,ch;while((ch=getchar())==' ' or ch=='\n' or ch=='\t'){}if(ch=='-'){sign=-1;ch=getchar();}else if(ch=='+')ch=getchar();while(ch>='0' and ch<='9'){num=num*10+(ch-'0');ch=getchar();}return sign*num;}
    inline void write(int n){if(n<0){putchar('-');n*=-1;}if(n>=10){write(n/10);}putchar(n%10+'0');}
    int n;
    int a[15]={};
    int t[10086][15]={};
    int ans=0;
    void dfs(int p,int sum){
        if(p>10){
            if(sum==n){
                ans++;
                for(int i=1;i<=10;i++){
                    t[ans][i]=a[i];
                }
            }
            return;
        }for(int i=1;i<=3;i++){
            if(sum+i<=n){
                a[p]=i;
                dfs(p****um+i);
            }
        }
    }
    void Main(){
        init();
        cin>>n;
        dfs(1,0);
        cout<<ans<<'\n';
        for(int i=1;i<=ans;i++){
            for(int j=1;j<=10;j++){
                cout<<t[i][j]<<' ';
            }cout<<'\n';
        }
        return;
    }
}

你姑没有这道题手写一下题目咪

题目描述
你将得到一个正整数 nn ，请列出把正整数 nn 划分为 kk 个正整数的每一种方法
输入格式
输入共 1 行：第 1 行，2 个正整数 n,kn,k
输出格式
输出为若干行：每行为空格隔开的若干个正整数，为一种 nn 划为 kk 个数的方法，每组数按从小到大的顺序输出。若两种方法中前 kk 个数相同，则第 kk 个数更小的排在前面
数据范围不知道

似乎对了？

namespace HQ{
    #define int long long
    void init(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);}
    inline int read(){int num=0,sign=1,ch;while((ch=getchar())==' ' or ch=='\n' or ch=='\t'){}if(ch=='-'){sign=-1;ch=getchar();}else if(ch=='+')ch=getchar();while(ch>='0' and ch<='9'){num=num*10+(ch-'0');ch=getchar();}return sign*num;}
    inline void write(int n){if(n<0){putchar('-');n*=-1;}if(n>=10){write(n/10);}putchar(n%10+'0');}
    int n,k;
    int a[1145]={};
    int ans=0;
    void dfs(int p,int sum){
        if(p>k){
            if(sum==n){
                for(int i=1;i<=k;i++){
                    cout<<a[i]<<' ';
                }cout<<'\n';
            }
            return;
        }for(int i=1;i<=n;i++){
            if(sum+i<=n and i>=a[p-1]){
                a[p]=i;
                dfs(p****um+i);
            }
        }
    }
    void Main(){
        init();
        a[0]=1;
        cin>>n>>k;
        dfs(1,0);
        return;
    }
}

搜索优化：记忆化搜索

  • 将一些多次出现的内容储存起来
  • 避免重复计算造成的时间浪费

依旧手写题目：

给出自然数 nn ，要求按如下方式构造数列
1.只有一个数字 nn 的数列是一个合法的数列
2.在一个合法的数列末尾加入一个自然数，但是这个自然数不能超过该数列最后一项的一半，可以得到一个新的合法数列
请你求出，一共有多少个合法数列两个合法数列 a,ba,b 不同当且仅当两数列长度不同或存在一个正整数 i≤∣a∣i \le |a| ，使得 ai≠bia_i≠b_i
输入格式
输入一个整数，表示 nn
输出格式
输出一个整数，表示合法是数列个数

namespace HQ{
    #define int long long
    void init(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);}
    inline int read(){int num=0,sign=1,ch;while((ch=getchar())==' ' or ch=='\n' or ch=='\t'){}if(ch=='-'){sign=-1;ch=getchar();}else if(ch=='+')ch=getchar();while(ch>='0' and ch<='9'){num=num*10+(ch-'0');ch=getchar();}return sign*num;}
    inline void write(int n){if(n<0){putchar('-');n*=-1;}if(n>=10){write(n/10);}putchar(n%10+'0');}
    int n;
    int a[1145]={};
    int ans=0;
    int dfs(int p){
        if(a[p]!=0){
            return a[p];            //此行即为记忆化搜索
        }a[p]=1;
        for(int i=1;i<=p/2;i++){
            a[p]+=dfs(i);
        }return a[p];
    }
    void Main(){
        init();
        cin>>n;
        cout<<dfs(n);
        return;
    }
}

树的基本概念（不是我咋还要写这个，我还是太区了）

  • 结点：每个元素
  • 边：结点之间的关系
  • 父结点：直接位于某节点上方、作为其前件的节点，就是该节点的父结点
  • 子结点：直接位于某节点下方、作为其后件的节点，就是该节点的子结点
  • 祖先：父结点的父结点的……
  • 兄弟结点：同一个父结点的结点
  • 根结点：没有父结点的结点
  • 叶结点：没有子结点的结点
  • 子树：树中某个结点，加上它的所有后代结点共同构成的树结构，该结点就是这棵子树的根结点
  • 结点的度：结点拥有子结点的数量
  • 叶结点：度为 00 的结点
  • 分支结点：度不为 00 的结点
  • 树的度：所有结点中度的最大值
  • 层次：根结点为第一层，其余结点的层次为父结点的层次+1
  • 树的高度/深度：结点的最大层次
  • 森林：若干棵互不相交的树

二叉树的定义

  • 度为 22 的树，即每个结点最多有两个子结点

看题
不是怎么今天网课上的课你姑都没题目
有一个 nn 个结点（n≤106n \le 10^6）的二叉树。给出每个结点的两个子结点编号（均不超过 nn ），建立一棵二叉树（根结点编号为 11 ），如果是叶子结点，则输入 0 0
建好这棵二叉树后，求出它的深度
输入格式
第一行一个整数 nn ，表示结点数
之后 nn 行，第 ii 行两个整数 li,ril_i,r_i ，分别表示结点 ii 的左右子结点编号。若 li=0l_i=0 则表示没有左子结点，ri=0r_i=0 同理
输出格式
一个整数，表示这棵二叉树的深度

namespace HQ{
    #define int long long
    void init(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);}
    inline int read(){int num=0,sign=1,ch;while((ch=getchar())==' ' or ch=='\n' or ch=='\t'){}if(ch=='-'){sign=-1;ch=getchar();}else if(ch=='+')ch=getchar();while(ch>='0' and ch<='9'){num=num*10+(ch-'0');ch=getchar();}return sign*num;}
    inline void write(int n){if(n<0){putchar('-');n*=-1;}if(n>=10){write(n/10);}putchar(n%10+'0');}
    int n,ans=0;
    int d[114514];
    int l[114514],r[114514];
    void dfs(int x){
        if(d[x]>ans)ans=d[x];
        if(l[x]!=0)d[l[x]]=d[x]+1,dfs(l[x]);
        if(r[x]!=0)d[r[x]]=d[x]+1,dfs(r[x]);
    }
    void Main(){
        init();
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>l[i]>>r[i];
        }d[1]=1;
        dfs(1);
        cout<<ans;
        return;
    }
}

树的遍历（怎么这个我也要写，我实在是太区了）

先序遍历：根左右
中序遍历：左根右 中序遍历的二叉树实际上可以看作 二叉树.zip
后序遍历：左右根
层次遍历：从根结点往下开始遍历每一次，顺序为从左到右
如下图

             A
           /   \
          B     C
        /   \     \
       D     E     F

该二叉树各个遍历：
先序遍历：ABDECF
中序遍历：DBEACF
后序遍历：DEBFCA
层次遍历：ABCDEF

代码实现即为 DFS 一个一个遍历，懒得写了

图（怎么这个我还要写，我真的实在是太区了）

  • 点和边连起来的就叫做图，是一种复杂的非线性数据结构
  • 定义为：graph=(V,E)graph=(V,E)
    VV 是一个非空有限集合，代表顶点（结点），EE 代表边的集合
  • 结点的入度：有向图中以这个结点为终点的有向边的数量
  • 结点的出度：为起点
  • 结点的度：入度数量+出度数量
  • 权值：边的属性，可以理解为长度、费用等
  • 连通：两个结点可以通过若干条边到达
  • 回路/环：起点和终点相同的路径
  • 简单图：没有重边和自环的图
  • 连通图：所有结点都连通的无向图
  • 强连通图：所有结点都连通的有向图
  • 完全图：边数最大的简单有向/无向图
    有向图：n×(n−1)n \times (n-1) 条边
    无向图：n×(n−1)÷2n \times (n-1) \div 2 条边
    （nn 为点的数量）

图的存储

二维数组邻接矩阵存储
定义 int g[n+15][n+15] ，其中 g[i][j] 表示从点 i 到点 j 的边的权值
g[i][j]={1或权值vi到vj之间有边0或∞vi到vj之间无边g[i][j]= \begin{cases} 1 或权值 &v_i 到 v_j 之间有边 \\0或 \infty &v_i 到 v_j 之间无边\end{cases}

邻接表
用 vector 存储图

看题
懒得打字了凑合着看吧

namespace HQ{
    #define int long long
    void init(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);}
    inline int read(){int num=0,sign=1,ch;while((ch=getchar())==' ' or ch=='\n' or ch=='\t'){}if(ch=='-'){sign=-1;ch=getchar();}else if(ch=='+')ch=getchar();while(ch>='0' and ch<='9'){num=num*10+(ch-'0');ch=getchar();}return sign*num;}
    inline void write(int n){if(n<0){putchar('-');n*=-1;}if(n>=10){write(n/10);}putchar(n%10+'0');}
    void Main(){
        init();
        vector<int>to[10086],val[10086];
        int n,m,x,y,z;
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            cin>>x>>y>>z;
            to[x].push_back(y);
            val[x].push_back(z);
            to[y].push_back(x);
            val[y].push_back(z);
        }for(int i=1;i<=n;i++){
            cout<<i<<':';
            for(int j=0;j<to[i].size();j++){
                cout<<"->"<<to[i][j]<<'('<<val[i][j]<<')';
            }cout<<'\n';
        }
        return;
    }
}
userId_undefined
去预览
0/2000

全部评论 12

热门讨论