当前位置：首页 > article >正文

算法知识点————【DFS】【BFS】【树】【图】

article 2025/1/21 6:35:28

** 深度优先搜索 **
DFS 用于遍历树和图的算法，过程中深入到不能深入为止，每个结点遍历一次。

** 广度优先搜索 **
BFS 用于从根结点开始遍历，遍历根结点下面的所有孩子结点，然后从孩子结点在进行宽度搜索，直到所有的结点都被遍历。

题目：路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false。
思路：DFS节点，然后维护一个计数器（正常思路可能是计数器从0 开始然后记录走过的路径和但是代码没有递减简单，初始的count为targetnum，然后每走过一个结点减去结点的值，然后判断是不是等于0并且是叶子结点，只有二者都满足的时候才说明找到了路径，否则没有）。所以结点和计数器就可以作为递归的参数，递归的返回值，由于是存在返回true，不存在返回false

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool traversal(TreeNode* cur,int count){
        //遇到叶子结点并且计数器为0
        if(!cur->left && !cur->right && count == 0) return true;
        //遇到叶子结点 直接返回
        if(!cur->left && !cur->right) return false;
        
        if(cur->left){//左
            //递归处理结点
            count -= cur->left->val;
            if(traversal(cur->left,count)) return true;
            count += cur->left->val;//回溯撤销结果 
        }
        if(cur->right){//右
            count -= cur->right->val;
            if(traversal(cur->right,count)) return true;
            count += cur->right->val;
        }
        return false;
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
        if( root == nullptr ) return false;
         return traversal(root,targetSum - root->val);
    }
};

返回路径，把路径都放在一起，由于要遍历整棵树，所以traversal函数不需要返回值。也就是遍历整个树和遍历单个路径的区别。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void traveral(TreeNode* cur,int count){
        //根(遇到叶子结点找到和为sum的路径)
        if(!cur->left && !cur->right && count == 0) {
                res.push_back(path);
                return;
        }
        //（遇到叶子结点没有找到，直接返回）
        if(!cur->left && !cur->right ) return; 
        //左
        if(cur -> left){
            path.push_back(cur->left->val);
            count -= cur->left->val;
            traveral(cur->left,count);//递归
            count += cur->left->val;//回溯
            path.pop_back();

        }
        //右
        if(cur -> right){
            path.push_back(cur->right->val);
            count -= cur->right->val;
            traveral(cur->right,count);
            count += cur->right->val;
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
       res.clear();
       path.clear();
       if(root == nullptr) return res;
       path.push_back(root->val);
       traveral(root,targetSum - root->val);
       return res; 
        
    }
};

树与图的BFS

借助一个queue队列

1、将起点加入队列，并标记为已经访问
2、从队列中取出一个结点，对其进行处理，并将其所有未访问的临接点加入到队列中
3、重复2，知道队列为空或者找到目标结点

题目： 无向图从结点1号到结点n号的最短路径长度
数组模拟邻接表过程参考https://www.acwing.com/blog/content/22417/

#include<iostream>
#include<queue>
using namespace std;
const int N = 100010;//最大节点数
int n , m ;//节点数n 边数 m
int h[N] , e[N] ,ne[N],idx;//邻接表存储
/*
e[i] 表示边 i 的目标节点
ne[i] 表示边 i 的下一条边的索引
h[i] 表示节点 i 的对应的链表的头节点的下标
int idx  表示边的序号,从0开始
*/

int d[N] ;//存储每个节点到起点的距离
bool flag[N];//存储每个节点是否已访问

void add(int a,int b){
    e[idx] = b,ne[idx]=h[a],h[a]=idx++;
}
int bfs(){
    queue<int> q;
    q.push(1);//起点加入队列
    flag[1] = true;
    d[1] = 0;//距离初始化为0；

    while (q.size())
    {
        int t = q.front();//取出对头元素
        q.pop();
        if(t == n) return d[t];//找到目标结点
        for(int i = h[t];i!=-1;i = ne[i]){
            int j = e[i];
            if(!flag[j]){//没有访问过的加入队列并更新距离和状态
                q.push(j);
                d[j] = d[t] + 1;
                flag[j] = true;
            }
        }
    }
    return -1;//没有找到结点，无解，返回-1
}

int main(){
    cin >> n >> m;
    memset(h,-1,N * sizeof(int));//初始化邻接表 初始值-1

    while (m--)//读入m条边
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);//无向图反向添加边
    }
    
 
  cout << bfs() <<endl;

  return 0 ;
    
}