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

图论（待完善）

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& grid) {
        if(grid.size() == 0 || grid[0].size() == 0)return 0;
        int m = grid.size(),n = grid[0].size();
        vector vec;
        
        int res =0;
         for(int i =0;i
            vector   
                int tmp = grid[i][j]-'0';
                tempvec.push_back(tmp);//转化成int类型的
            }
            vec.push_back(tempvec);
        } 
        for(int i =0;i
            for(int j=0;j
                if( vec[i][j] == 1){
                    dfs(vec,i,j);//dfs的次数就是岛屿的数量
                    res++;
                }
              
            }
        } 
        return res;
    }   
private:
    void dfs(vector
        if(i
    Solution s;
    vector
    {'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;
}
{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
};

public:
    int orangesRotting(vector
        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
            for(int j =0;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{1,0},{0,1},{0,-1},{-1,0}};
        while(!q.empty()){//每一层
            int qsize = q.size();//有n个烂橘子
            bool flag = false;
            for(int i =0;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
                        q.push({nx,ny});
                        grid[nx][ny] = 2;
                        fresh--;//到最后要没有新鲜橘子才结束
                        flag = 1;//有新鲜橘子就标记
                    }
                }
            }
            //一层就要++
            if(flag)min++;//有新鲜橘子才++
        }
        return fresh? -1:min;
    }
};