图论（待完善）
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直接入队遍历。