CSP-230202总结

coding

快速存图

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std ;
const int N = 100 ;

struct Edge{
    int to ; // 终点
    int value ; // 边权
}e;
vector<Edge> G[N+1] ;

int m, n, tmp ;
// tmp 作为 出发点
int main()
{
    cin >>n >> m ;
    for(int i=0; i<m; i++)
    {
        cin >> tmp >> e.to >> e.value ;
        G[tmp].push_back(e) ;
        // 将数据压入动态数组
        // 表示在这个出发点下引出的边
    }
    // 1.遍历出发点
    // 2.遍历点引出的所有边
    for (int i=1;i<=n;i++){ //按照出发点的顺序遍历
        for (int j=0;j<G[i].size();j++){ //遍历出发点所引出的边
            e=G[i][j];
            cout<<"From "<<i<<" to "<<e.to<<", the cost is "<<e.value<<endl;
        }
    }
    return 0 ;
}

DFS 与 BFS

DFS整体思路

 DFS(v) // v 可以是图中的一个顶点，也可以是抽象的概念，如 dp 状态等。
   在 v 上打访问标记
   for u in v 的相邻节点
     if u 没有打过访问标记 then
       DFS(u)
     end
   end
end

对于连通图，DFS 序列通常不唯一
树的 DFS 序列也是不唯一的

BFS整体思路

BFS 算法找到的路径是从起点开始的 最短 合法路径

BFS 结束时，每个节点都是通过从起点到该点的 最短路径 访问的

算法过程可以看做是图上火苗传播的过程：
最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。
具体来说，我们用一个队列 Q 来记录要处理的节点，
然后开一个布尔数组 vis[] 来标记是否已经访问过某个节点。 
    q = new queue() ;
开始的时候，我们将所有节点的 vis 值设为 0，表示没有访问过；
然后把起点 s 放入队列 Q 中并将 vis[s] 设为 1。
之后，我们每次从队列 Q 中取出队首的节点 u，
然后把与u相邻的所有节点v标记为已访问过并放入队列 Q。
循环直至当队列 Q 为空，表示 BFS 结束。
while(队列不空){
    int u = 队首 ;
    弹出队首 ;
    for(枚举 u 的邻居)
    {
        ... 更新数据
        if(...)
        添加到队首;
        else
        添加到队尾;
    }
}

模板题

洛谷 查找文献

#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<cstdlib>
#include<queue>
using namespace std ;

int n, m , a, b, tmp ;
// a -> start ; b -> end
bool vis[100005] = {0};
vector<int> G[100005] ;
void DFS(int u)
{
    if(vis[u]==1) return ;
    cout<<u<<" " ;
    vis[u] = 1 ;
    for(int i=0; i<G[u].size(); i++)
    {
        int t = G[u][i] ;
        if(vis[t]==0)
        {
            DFS(t) ;
        } 
    }
}

void BFS(int u)
{
    memset(vis,0,sizeof(vis)) ;
    queue<int> q ;
    q.push(u) ;
    vis[u] = 1;
    while(!q.empty())
    {
        int v = q.front() ;
        q.pop() ;
        cout<< v << " " ;
        for(int i=0; i<G[v].size(); i++)
        {
            if(vis[G[v][i]]==0)
            {
                vis[G[v][i]] = 1 ;
                q.push(G[v][i]) ;
            } 
        }
    }
}

int main()
{
    cin >> n >> m ;
    for(int i=1; i<=m; i++)
    {
        cin >> tmp >> a ;
        G[tmp].push_back(a) ;
    }
    
    for(int i=1; i<=n; i++)
        sort(G[i].begin(),G[i].end()) ;
    
    DFS(1) ; cout<<endl ;

    BFS(1) ; cout<<endl ;
    return 0 ;
}

力扣 二叉树最大深度

/**
 * 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:
    int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0 ;
        return max( maxDepth(root->left), maxDepth(root->right) ) + 1 ;
    }
};