算法基础--------【图论】

图论（待完善）

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) 向此点的上下左右 (i+1,j),(i-1,j),(i,j+1),(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(vector<vector<char>>& grid) {if(grid.size() == 0 || grid[0].size() == 0)return 0;int m = grid.size(),n = grid[0].size();vector<vector<int>> vec;int res =0;for(int i =0;i<m;i++){vector<int> tempvec;for(int j=0;j<n;j++){   int tmp = grid[i][j]-'0';tempvec.push_back(tmp);//转化成int类型的}vec.push_back(tempvec);} for(int i =0;i<m;i++){for(int j=0;j<n;j++){if( vec[i][j] == 1){dfs(vec,i,j);//dfs的次数就是岛屿的数量res++;}}} return res;}   
private:void dfs(vector<vector<int>>& vec,int i, int j){if(i<0 || j<0 || i>vec.size()-1 || j>vec[0].size()-1)return;cout<<"(i,j) = "<<i<<j<<","<<vec[i][j]<<endl;if(vec[i][j] != 1)return;vec[i][j] =-1;//标记dfs(vec,i+1,j);dfs(vec,i,j+1);dfs(vec,i-1,j);dfs(vec,i,j-1);}
};
int main() {Solution s;vector<vector<char>> 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：
若是则置零（删除岛屿节点），并将此节点上下左右节点 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 加入队列；
若不是则跳过此节点；
循环 pop 队列首节点，直到整个队列为空，此时已经遍历完此岛屿。

class Solution {
public:int numIslands(vector<vector<char>>& grid) {if (grid.empty() || grid[0].empty()) return 0;int m = grid.size(), n = grid[0].size();int res = 0;queue<pair<int, 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:vector<pair<int, 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]]
输出：4

class Solution {
public:int orangesRotting(vector<vector<int>>& 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;//新鲜橘子queue<pair<int,int>> q;//存储腐烂的橘子for(int i =0;i<m;i++){for(int j =0;j<n;j++){if(grid[i][j] == 2){q.push({i,j});}else if(grid[i][j] == 1){//统计新鲜橘子fresh++;}}}// if(q.empty() || fresh==0 )return -1;//没有腐烂的橘子 没有新鲜的橘子vector<pair<int,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;i<qsize;i++){//遍历这n个烂橘子int x = q.front().first;int y = q.front().second;q.pop();for(auto dir:dirs){int nx = dir.first+x;int ny = dir.second+y;if(nx >=0 && nx<m && ny >=0 && ny<n && grid[nx][ny]==1){q.push({nx,ny});grid[nx][ny] = 2;fresh--;//到最后要没有新鲜橘子才结束flag = 1;//有新鲜橘子就标记}}}//一层就要++if(flag)min++;//有新鲜橘子才++}return fresh? -1:min;}
};

总结：腐烂的橘子是以各个腐烂的橘子为头结点开始入队遍历的，而岛屿数量是以有无1直接入队遍历。