图论
- 度：无项图中有几条边连接该节点，该节点就有几度。有向图中，入度：从该节点出发的边的个数；出度：指向该节点边的个数。
- 强连通图：在有向图中，任何两个节点是可以互相到达的
- 连通分量：在无向图中的极大连通子图称为该图的一个连通分量
- 强连通分量：在有向图中的极大强连通子图称为该图的强连通分量
- 图的构造：朴素存储、邻接矩阵、邻接表
1、dfs和bfs
（1）dfs
不到黄河不回头[换方向：回溯]，代码框架：
void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
}（2）bfs
一圈一圈的搜索，代码框架：
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; // 只要加入队列立刻标记，避免重复访问
}
}
}
}（3）所有可达路径
【题目描述】
给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个程序，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。
【输入描述】
第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边
后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径
【输出描述】
输出所有的可达路径，路径中所有节点的后面跟一个空格，每条路径独占一行，存在多条路径，路径输出的顺序可任意。
如果不存在任何一条路径，则输出 -1。
注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是 1 3 5,而不是 1 3 5， 5后面没有空格！
数据范围：
- 图中不存在自环
- 图中不存在平行边
- 1 <= N <= 100
- 1 <= M <= 500
//dfs
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> result;
vector<int> path;
void dfs(const vector<vector<int>>& graph, int x, int n) {
if (x == n) {
result.push_back(path);
return;
}
for (int i = 1; i <= n; i++) {
if (graph[x][i]) {
path.push_back(i);
dfs(graph,i,n);
path.pop_back();
}
}
}
int main(){
int m,n,s,t;
cin>>n>>m;
vector<vector<int>> graph(n+1,vector<int>(n+1,0));
while(m--){
cin>>s>>t;
graph[s][t] = 1;
}
path.push_back(1);
dfs(graph,1,n);
if (result.size() == 0) cout<<"-1"<<endl;
for (auto& pa : result) {
for (int i = 0; i < pa.size() - 1; i++) {
cout<<pa[i]<<" ";
}
cout<<pa[pa.size()-1]<<endl;
}
return 0;
}（4）岛屿数量
题目描述：
给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述：
第一行包含两个整数 N, M，表示矩阵的行数和列数。
后续 N 行，每行包含 M 个数字，数字为 1 或者 0。
输出描述：
输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。
数据范围：
- 1 <= N, M <= 50
//dfs
#include<iostream>
#include<vector>
using namespace std;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
void dfs(const vector<vector<int>>& graph,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 || nextx >= graph.size() || nexty < 0 || nexty >= graph[0].size()) continue;
if (!visited[nextx][nexty] && graph[nextx][nexty] == 1) {
visited[nextx][nexty] = true;
dfs(graph,visited,nextx,nexty);
}
}
return;
}
int main() {
int n,m;
cin>>n>>m;
vector<vector<int>> graph(n,vector<int>(m,0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin>>graph[i][j];
}
}
int _count = 0;
vector<vector<bool>> visited(n,vector<bool>(m,false));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && graph[i][j] == 1) {
visited[i][j] = true;
_count++;
dfs(graph,visited,i,j);
}
}
}
cout<<_count<<endl;
return 0;
}//dfs
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
void bfs(const vector<vector<int>>& graph,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();
int curx = cur.first;
int cury = cur.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 || nextx >= graph.size() || nexty < 0 || nexty >= graph[0].size()) continue;
if (!visited[nextx][nexty] && graph[nextx][nexty] == 1) {
que.push({nextx,nexty});
visited[nextx][nexty] = true;
}
}
}
return;
}
int main() {
int n,m;
cin>>n>>m;
vector<vector<int>> graph(n,vector<int>(m,0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin>>graph[i][j];
}
}
int _count = 0;
vector<vector<bool>> visited(n,vector<bool>(m,false));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && graph[i][j] == 1) {
_count++;
bfs(graph,visited,i,j);
}
}
}
cout<<_count<<endl;
return 0;
}（5）岛屿的最大面积
题目描述：
给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述：
第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述：
输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。
数据范围：
- 1 <= M, N <= 50。
//dfs
#include<iostream>
using namespace std;
int _count;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
void dfs(const vector<vector<int>>& graph,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 || nextx >= graph.size() || nexty < 0 || nexty >= graph[0].size()) continue;
if (!visited[nextx][nexty] && graph[nextx][nexty] == 1) {
visited[nextx][nexty] = true;
_count++;
dfs(graph,visited,nextx,nexty);
}
}
return;
}
int main() {
int n,m;
cin>>n>>m;
vector<vector<int>> graph(n,vector<int>(m,0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin>>graph[i][j];
}
}
int res = 0;
vector<vector<bool>> visited(n,vector(m,false));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (graph[i][j] == 1 && !visited[i][j]) {
_count = 1;
visited[i][j] = true;
dfs(graph,visited,i,j);
res = max(res,_count);
}
}
}
cout<<res<<endl;
return 0;
}//bfs
#include<iostream>
#include<queue>
using namespace std;
int _count;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
void bfs(const vector<vector<int>>& graph,vector<vector<bool>>& visited,int x, int y) {
queue<pair<int,int>> que;
que.push({x,y});
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 >= graph.size() || nexty < 0 || nexty >= graph[0].size()) continue;
if (!visited[nextx][nexty] && graph[nextx][nexty] == 1) {
visited[nextx][nexty] = true;
_count++;
que.push({nextx,nexty});
}
}
}
return;
}
int main() {
int n,m;
cin>>n>>m;
vector<vector<int>> graph(n,vector<int>(m,0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin>>graph[i][j];
}
}
int res = 0;
vector<vector<bool>> visited(n,vector(m,false));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (graph[i][j] == 1 && !visited[i][j]) {
_count = 1;
visited[i][j] = true;
bfs(graph,visited,i,j);
res = max(res,_count);
}
}
}
cout<<res<<endl;
return 0;
}（6）孤岛的总面积
题目描述：
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。
输入描述：
第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。
输出描述：
输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。
数据范围：
1 <= M, N <= 50。