PHP网站开发实例教程电子书,电商网站建设 教学总结,加入网站帮忙做网站,网站空间和主机图论#xff08;待完善#xff09;
DFS:和回溯差不多 BFS:进while进行层序遍历
定义: 图论#xff08;Graph Theory#xff09;是研究图及其相关问题的数学理论。图由节点#xff08;顶点#xff09;和连接这些节点的边组成。图论的研究范围广泛#xff0c;涉及路径、…图论待完善
DFS:和回溯差不多 BFS:进while进行层序遍历
定义: 图论Graph Theory是研究图及其相关问题的数学理论。图由节点顶点和连接这些节点的边组成。图论的研究范围广泛涉及路径、流、匹配、着色等诸多问题。
特点: 节点和边: 图论问题通常围绕节点点和边线展开研究它们之间的关系。 图的种类: 包括无向图、有向图、加权图等不同类型的图每种图有不同的应用场景。 算法: 常见的图论算法包括深度优先搜索DFS、广度优先搜索BFS、最短路径算法如Dijkstra算法、Floyd-Warshall算法、最小生成树算法如Kruskal算法、Prim算法等。(Dijkstra华子暑期实习笔试考了) 适用范围: 广泛用于网络分析、路径规划、资源分配等领域如社交网络、交通系统、计算机网络等。网络分析路径规划这个真的很爱考 示例: 最短路径问题如寻找城市之间的最短路线是一个经典的图论问题通常用Dijkstra算法或Bellman-Ford算法解决。
【200】岛屿数量
要么用DFS的思想要么用BFS层序遍历的思想 DFS节点有四个方向都遍历一遍我写的逻辑是先下右上左。 dfs方法 设目前指针指向一个岛屿中的某一点 (i, j)寻找包括此点的岛屿边界。 从 (i, j) 向此点的上下左右 (i1,j),(i-1,j),(i,j1),(i,j-1) 做深度搜索。 终止条件 (i, j) 越过矩阵边界; grid[i][j] 0代表此分支已越过岛屿边界。 搜索岛屿的同时执行 grid[i][j] ‘0’即将岛屿所有节点删除以免之后重复搜索相同岛屿。 主循环 遍历整个矩阵当遇到 grid[i][j] ‘1’ 时从此点开始做深度优先搜索 dfs岛屿数 count 1 且在深度优先搜索中删除此岛屿。 最终返回岛屿数 count 即可。
DFS:
class Solution {
public:int numIslands(vectorvectorchar grid) {if(grid.size() 0 || grid[0].size() 0)return 0;int m grid.size(),n grid[0].size();vectorvectorint vec;int res 0;for(int i 0;im;i){vectorint tempvec;for(int j0;jn;j){ int tmp grid[i][j]-0;tempvec.push_back(tmp);//转化成int类型的}vec.push_back(tempvec);} for(int i 0;im;i){for(int j0;jn;j){if( vec[i][j] 1){dfs(vec,i,j);//dfs的次数就是岛屿的数量res;}}} return res;}
private:void dfs(vectorvectorint vec,int i, int j){if(i0 || j0 || ivec.size()-1 || jvec[0].size()-1)return;cout(i,j) ij,vec[i][j]endl;if(vec[i][j] ! 1)return;vec[i][j] -1;//标记dfs(vec,i1,j);dfs(vec,i,j1);dfs(vec,i-1,j);dfs(vec,i,j-1);}
};
int main() {Solution s;vectorvectorchar grid {{1,1,1,1,0},{1,1,0,1,0},{1,1,0,0,0},{0,0,0,0,0}};s.numIslands(grid);system(pause);return 0;
}BFS: 借用一个队列 queue判断队列首部节点 (i, j) 是否未越界且为 1 若是则置零删除岛屿节点并将此节点上下左右节点 (i1,j),(i-1,j),(i,j1),(i,j-1) 加入队列 若不是则跳过此节点 循环 pop 队列首节点直到整个队列为空此时已经遍历完此岛屿。
class Solution {
public:int numIslands(vectorvectorchar grid) {if (grid.empty() || grid[0].empty()) return 0;int m grid.size(), n grid[0].size();int res 0;queuepairint, int q;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {q.push({i,j});grid[i][j] 0; // 标记为已访问 加入就标记res;//第一层更新while (!q.empty()) {//BFS遍历int x q.front().first, y q.front().second;q.pop();for (const auto dir : dirs) {int nx x dir.first, ny y dir.second;if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) {q.push({nx,ny});grid[nx][ny] 0; // 标记为已访问}}}}}}return res;}
private:vectorpairint, int dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};};【994】腐烂的橘子
在给定的 m x n 网格 grid 中每个单元格可以有以下三个值之一
值 0 代表空单元格值 1 代表新鲜橘子值 2 代表腐烂的橘子。
每分钟腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回 -1 。
示例 1 输入grid [[2,1,1],[1,1,0],[0,1,1]]
输出4class Solution {
public:int orangesRotting(vectorvectorint grid) {if(grid.size() 0 ||grid[0].size() 0)return -1;int m grid.size();int n grid[0].size();int min 0;//分钟数int fresh 0;//新鲜橘子queuepairint,int q;//存储腐烂的橘子for(int i 0;im;i){for(int j 0;jn;j){if(grid[i][j] 2){q.push({i,j});}else if(grid[i][j] 1){//统计新鲜橘子fresh;}}}// if(q.empty() || fresh0 )return -1;//没有腐烂的橘子 没有新鲜的橘子vectorpairint,int dirs {{1,0},{0,1},{0,-1},{-1,0}};while(!q.empty()){//每一层int qsize q.size();//有n个烂橘子bool flag false;for(int i 0;iqsize;i){//遍历这n个烂橘子int x q.front().first;int y q.front().second;q.pop();for(auto dir:dirs){int nx dir.firstx;int ny dir.secondy;if(nx 0 nxm ny 0 nyn grid[nx][ny]1){q.push({nx,ny});grid[nx][ny] 2;fresh--;//到最后要没有新鲜橘子才结束flag 1;//有新鲜橘子就标记}}}//一层就要if(flag)min;//有新鲜橘子才}return fresh? -1:min;}
};总结腐烂的橘子是以各个腐烂的橘子为头结点开始入队遍历的而岛屿数量是以有无1直接入队遍历。
