首页 > 其他分享 >图论

图论

时间:2024-01-10 12:33:28浏览次数:27  
标签:图论 int vector grid visited nextx nexty

目录

深搜入门leetcode797

因为也是二刷,推的比较快
刷题之后的感悟,其实就是先把模板写上去了之后再在里面缝缝补补出题目要求
都比较模板,变通一下思路就能做出来

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    //x代表当前的节点
    void dfs(vector<vector<int>>& graph,int x)
    {
        //终止条件是遍历到最后一个节点了
        if(x==graph.size()-1)
        {
            result.push_back(path);
            return;
        }
        //访问一个节点能到达的所有目标节点
        for(int i=0;i<graph[x].size();i++)
        {
            //添加路径,下一个目标节点
            path.push_back(graph[x][i]);
            //深搜,每个里面都要dfs
            dfs(graph,graph[x][i]);
            //深搜退出需要pop节点
            path.pop_back();
        }
    }
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        path.push_back(0);
        dfs(graph,0);
        return result;
    }
};

广搜入门

广搜的搜索方式就适合于解决两个点之间的最短路径问题。

因为广搜是从起点出发,以起始点为中心一圈一圈进行搜索,一旦遇到终点,记录之前走过的节点就是一条最短路。
代码模板

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图,也就是一个二维数组
// visited标记访问过的节点,不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que; // 定义队列
    que.push({x, y}); // 起始节点加入队列
    visited[x][y] = true; // 只要加入队列,立刻标记为访问过的节点
    while(!que.empty()) { // 开始遍历队列里的元素
        pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
        int curx = cur.first;
        int cury = cur.second; // 当前节点坐标
        for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了,直接跳过
            if (!visited[nextx][nexty]) { // 如果节点没被访问过
                que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点
                visited[nextx][nexty] = true; // 只要加入队列立刻标记,避免重复访问
            }
        }
    }

}

leetcode200 深搜和广搜

class Solution {
public:
    int dir[4][2]={0,1,0,-1,1,0,-1,0};
    void bfs(vector<vector<char>>& grid,vector<vector<bool>>& visited,int x,int y)
    {
        queue<pair<int,int>> que;
        que.push({x,y});
        visited[x][y]=1;
        while(!que.empty())
        {
            int x=que.front().first;
            int y=que.front().second;
            que.pop();
            for(int i=0;i<4;i++)
            {
                int nextx=x+dir[i][0];
                int nexty=y+dir[i][1];
                if(nextx<0||nexty<0||nextx>=grid.size()||nexty>=grid[0].size())
                {
                    continue;
                }
                if(!visited[nextx][nexty]&&grid[nextx][nexty]=='1')
                {
                    que.push({nextx,nexty});
                    visited[nextx][nexty]=1;
                }
            }
        }
    }
    void dfs(vector<vector<char>>& grid,vector<vector<bool>>& visited,int x,int y)
    {
        //四个方向遍历
        for(int i=0;i<4;i++)
        {
            int nextx=x+dir[i][0];
            int nexty=y+dir[i][1];
            if(nextx<0||nexty<0||nextx>=grid.size()||nexty>=grid[0].size())
            {
                continue;
            }
            if(!visited[nextx][nexty]&&grid[nextx][nexty]=='1')
            {
                visited[nextx][nexty]=1;
                dfs(grid,visited,nextx,nexty);
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        vector<vector<bool>> visited(n,vector<bool>(m,0));
        int ans=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(!visited[i][j]&&grid[i][j]=='1')
                {
                    ans++;
                    //dfs
                    //visited[i][j]=1;
                    //dfs(grid,visited,i,j);
                    //bfs
                    bfs(grid,visited,i,j);
                }
            }
        }
        return ans;

    }
};

695

class Solution {
public:
    int dir[4][2]={1,0,-1,0,0,1,0,-1};
    int bfs(vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y)
    {
        int area=1;
        queue<pair<int,int>> que;
        que.push({x,y});
        visited[x][y]=true;
        while(!que.empty())
        {
            int curx=que.front().first;
            int cury=que.front().second;
            que.pop();
            for(int i=0;i<4;i++)
            {
                int nextx=curx+dir[i][0];
                int nexty=cury+dir[i][1];
                if(nextx<0||nexty<0||nextx>=grid.size()||nexty>=grid[0].size())
                {
                    continue;
                }
                if(!visited[nextx][nexty]&&grid[nextx][nexty]==1)
                {
                    que.push({nextx,nexty});
                    visited[nextx][nexty]=1;
                    area++;
                }
            }
        }
        return area;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int maxarea=0;
        int n=grid.size();
        int m=grid[0].size();
        vector<vector<bool>> visited(n,vector<bool>(m,0));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(!visited[i][j]&&grid[i][j]==1)
                {
                    maxarea=max(maxarea,bfs(grid,visited,i,j));
                }
            }
        }
        return maxarea;
    }
};

1020

class Solution {
public:
    int dir[4][2]={0,1,0,-1,1,0,-1,0};
    void dfs(vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y)
    {
        for(int i=0;i<4;i++)
        {
            int nextx=x+dir[i][0];
            int nexty=y+dir[i][1];
            if(nextx<0||nexty<0||nextx>=grid.size()||nexty>=grid[0].size())
            {
                continue;
            }
            if(!visited[nextx][nexty]&&grid[nextx][nexty]==1)
            {
                visited[nextx][nexty]=1;
                dfs(grid,visited,nextx,nexty);
            }
        }
    }
    int numEnclaves(vector<vector<int>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        vector<vector<bool>> visited(n,vector<bool>(m,0));
        //只需要遍历四个边
        for(int i=0;i<n;i++)
        {
            if(!visited[i][0]&&grid[i][0]==1)
            {
                visited[i][0]=1;
                dfs(grid,visited,i,0);
            }
            if(!visited[i][m-1]&&grid[i][m-1]==1)
            {
                visited[i][m-1]=1;
                dfs(grid,visited,i,m-1);
            }
        }
        for(int j=0;j<m;j++)
        {
            if(!visited[0][j]&&grid[0][j]==1)
            {
                visited[0][j]=1;
                dfs(grid,visited,0,j);
            }
            if(!visited[n-1][j]&&grid[n-1][j]==1)
            {
                visited[n-1][j]=1;
                dfs(grid,visited,n-1,j);
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(visited[i][j]==false&&grid[i][j]==1)
                {
                    ans++;
                }
            }
        }
        return ans;


    }
};

标签:图论,int,vector,grid,visited,nextx,nexty
From: https://www.cnblogs.com/liviayu/p/17956190

相关文章

  • 【图论】最大势算法
    模板题FishingNet给定一个无向图,判断是否是弦图。\(1\leqn\leq1000\)。算法概述最大势算法(MCS),是一个用于求出无向图完美消除序列的算法。算法流程为:钦定一个集合\(S\)。每次找到任意一个与\(S\)中的点连边最多的点,加入\(S\),放在消除序列末尾。这样就可以......
  • 图论1
    A.能量树时间限制:1000ms空间限制:262144kB题目描述时间:1s空间:256M题目描述:小信有 n 个节点的有根能量树,根为 1。最开始,树上每个节点的能量都是 0。现在小信有 n 个能量球,第 i 个能量球拥有 vi​ 能量。她想把这 n 个能量球分别放置在能量树......
  • 图论
    相关定义图是一个二元组\((V,E)\),节点集合为\(V\),边集合为\(E\),其中边\((u,v)\)的顶点为\(u,v\)。其中顶点的度数为以该顶点为端点的边数。有向图:每条边存在一个方向\(u\)->\(v\),对于有向图,点\(u\)的出度为从\(u\)出发的边数,入度为到\(u\)的边数。无向图:每条......
  • 陈峻宇高级图论讲课笔记
    离线哩!竞赛图竞赛图确实抽象,性质一堆一堆的,想不明白……而且多半都和强连通分量有关系。兰道定理考虑一共有\(n\choose2\)条边,那么\(\sumout_x=\binomn2\)。兰道定理大致就是如果竞赛图强连通,那么:\[\not\existsk\in[1,n),\sum_{x=1}^kout_x=\binomk2......
  • 图论——最短路
    https://csacademy.com/app/graph_editor/https://riverhamster.gitee.io/app/graph_editor/注:时间复杂度分析中,假设\(n\lem\len^2\)最短路本质上是一种DP阶段:点状态:拆点决策:边最优子结构:最短路的任何子路径都一定是最短路无后效性:正权图中一定可以找到一种无后......
  • 图论
    1.图的基本概念例2.握手定理例3.完全图4.子图与补图5.图的同构例6.路与回路7.割集1.点割集2.边割集3.点连通度4.边连通度8.有向图的连通性例9.图的矩阵表示例10.欧拉图11.汉密尔顿图例12.树1......
  • 浅谈一类边权带指数的图论问题
    偶然看到了这道题,求的是边权为\(n^w\)次方时树上的第\(k\)小路径,觉得这类题目很有意思,就研究了一下。1.CF464ETheClassicProblem题意:给一个无向图,每条边的边权是\(2^{w_i}\),求\(s\)到\(t\)的最短路。思路:首先,我们可以把距离看成一个二进制数,那么我们需要能支持快......
  • 图论做题记录1
    图论做题记录前言:大概是记录本人打比赛或者做题碰到的图论的部分题。所有题目均已省以下宏://QwQ#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>usingnamespacestd;#definefifirst#definesesecondtypedefpair<int,int>PII;typed......
  • C++ 图论之次最小生成树
    1.前言生成树指在无向图中找一棵包含图中的所有节点的树,此树是含有图中所有顶点的无环连通子图。对所有生成树边上的权重求和,权重和最小的树为最小生成树,次小的为次最小生成树。最小生成树和次最小生成树的应用领域都较广泛。也是图论中优为重要的研究对象,求解算法也是常规必须......
  • 【图论】差分约束与SPFA 11.25学习小结
    开篇碎碎念每次都是以开篇碎碎念开头,虽然不知道为什么,但似乎成为了惯例。本来是直接看的差分约束,一上来发现一堆不等式,以为是数学的一个tag乱入图论(x,结果发现还真的是建图来做的,然后学了一下之后...负边权?!跑不了dijkstra啊!!于是学了一下SPFA(虽然...SPFA已死)然后顺道写了一下关于......