哪一家网站做简历,网站项目申请,thinkphp 网站根目录地址,网站内套网站代码图论
基础知识
1 无向图
#xff08;1#xff09;度#xff1a;一个顶点连n条边就度为n
#xff08;2#xff09;权
加权无向图#xff1a;有边长的无向图
#xff08;3#xff09;通道#xff1a;两个顶点之间有一些边和点#xff0c;并且没有重复的边
路1度一个顶点连n条边就度为n
2权
加权无向图有边长的无向图
3通道两个顶点之间有一些边和点并且没有重复的边
路两个顶点之间有一些边和点并且没有重复的边和点
4连通性
1连通图任意两点之间都有路相连
2连通分量极大连通子图
连通子图并且没有包含这个连通子图的连通图
2 有向图
1度
入度n条边指向顶点则入度为n
出度从顶点发出n条边则出度为n
2权
加权有向图有边长的无向图
3连通性
1强连通任意2个点可以相互到达。也就是任意两个点之间都有相互指向的有向路任何一个点都有到剩下所有点的有向路
2强连通分量极大强连通子图
强连通子图并且没有包含这个强连通子图的强连通图
3 图的构造
邻接表、邻接矩阵 或者用类
1邻接表
1邻接表 使用 数组 链表的方式来表示。 邻接表是从边的数量来表示图有多少边 才会申请对应大小的链表
// 节点编号从1到n所以申请 n1 这么大的数组
vectorlistint graph(n 1); // 邻接表list为C里的链表
graph[1].push_back(3) 表示5---3节点1 指向 节点3 和 节点5节点2 指向 节点4、节点3、节点5节点3 指向 节点4节点4指向节点1
2邻接表的优点
对于稀疏图的存储只需要存储边空间利用率高遍历节点连接情况相对容易
3邻接表的缺点
检查任意两个节点间是否存在边效率相对低需要 O(V)时间V表示某节点连接其他节点的数量。实现相对复杂不易理解
2邻接矩阵
1邻接矩阵 使用 二维数组 来表示图结构。 邻接矩阵是从节点的角度来表示图有多少节点就申请多大的二维数组
grid[i][j] 6表示 节点 i 指向 节点j 边的权值为6
如果想表示无向图即grid[i][j] 6grid[j][i] 6表示节点i 与 节点j相互连通权值为6
2邻接矩阵的优点
表达方式简单易于理解检查任意两个顶点间是否存在边的操作非常快适合稠密图在边数接近顶点数平方的图中邻接矩阵是一种空间效率较高的表示方法。
3邻接矩阵的缺点
遇到稀疏图会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵造成时间浪费
3类
4 图的遍历方式
深度优先搜索dfs广度优先搜索bfs
深度优先搜索
1、dfs要点
1搜索方向是认准一个方向搜直到碰壁之后再换方向
2换方向是撤销原路径回退一步改为节点链接的下一个路径回溯的过程
2、dfs的举例 假设默认路径
那么接下来考虑下一个方向先回溯退回5,遍历5的下一步选择接下来就选择5—4
在节点4这里先选择6,到达终点再回溯退回4,遍历4的下一步选择接下来就选择4–3
3、dfs代码(也就是回溯)
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); 递归回溯撤销处理结果}
}4、深度优先搜索的三步走
1确定递归返回值和参数
2确定终止条件以及终止条件处做什么
3遍历当前节点可以选择的下一个点遍历递归树的一个层
5、模板题所有可达路径
题目描述
给定一个有 n 个节点的有向无环图节点编号从 1 到 n。请编写一个函数找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。
输入描述
第一行包含两个整数 NM表示图中拥有 N 个节点M 条边
后续 M 行每行包含两个整数 s 和 t表示图中的 s 节点与 t 节点中有一条路径
输出描述
输出所有的可达路径路径中所有节点之间空格隔开每条路径独占一行存在多条路径路径输出的顺序可任意。如果不存在任何一条路径则输出 -1。
注意输出的序列中最后一个节点后面没有空格 例如正确的答案是 1 3 5,而不是 1 3 5 5后面没有空格
#include bits/stdc.h
#include vector
using namespace std;
vectorint path;
vectorvectorint res;
void dfs(int point, int n, vectorvectorint graph) {if (point n) {res.push_back(path);return;}for (int i 1; i graph[point].size(); i) {if (graph[point][i]) {path.push_back(i);dfs(i, n, graph);path.pop_back();}}
}
int main() {int n;int m;cin n m;vectorvectorint graph(n 1, vectorint(n 1, 0));for (int i 0; i m; i) {int start;int end;cin start end;graph[start][end] 1;}path.push_back(1);dfs(1, n, graph);if (res.size() 0) {cout -1 ;return 0;}for (int i 0; i res.size(); i) {for (int j 0; j res[i].size(); j) {cout res[i][j];if (j res[i].size()-1)cout ;}if (i res.size()-1)cout \n;}return 0;
}广度优先搜索
1、特点
广搜bfs是一圈一圈的搜索过程和深搜dfs是一条路跑到黑然后再回溯
2、只要BFS只要搜到终点一定是一条最短路径
3、代码框架
1如何保存遍历到的点
仅仅需要一个容器能保存我们要遍历过的元素就行用队列用栈用数组都是可以的
这里选择用队列
2要点
1用队列进行遍历每次把队首拿出来弹出将队首可以走到的后面的点放进队尾一直到队空
2在入队的时候标记visit因为如果在弹出的时候再标记就会导致一个点重复的加入队列
3举例
用一个方格地图假如每次搜索的方向为 上下左右不包含斜上方那么给出一个start起始位置那么BFS就是从四个方向走出第一步
例子、图和代码来自代码随想录 int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图也就是一个二维数组
// visited标记访问过的节点不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y) {queuepairint, int que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] true; // 只要加入队列立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pairint ,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; // 只要加入队列立刻标记避免重复访问}}}}岛屿数量
题干
题目描述
给定一个由 1陆地和 0水组成的矩阵你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M表示矩阵的行数和列数。
后续 N 行每行包含 M 个数字数字为 1 或者 0。
输出描述
输出一个整数表示岛屿的数量。如果不存在岛屿则输出 0。
输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1输出示例
3思路每次遇到第一个没有访问过的陆地就给结果1,然后把与这个陆地相连的陆地全都标记为isited
无论是dfs还是bfs都是为了找到与这个陆地相连的陆地
1、深度优先搜索
1版本1
没有明确的终止条件用for循环内的判断条件排除
include iostream
#include vector
using namespace std;int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(const vectorvectorint grid, vectorvectorbool 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 grid.size() || nexty 0 || nexty grid[0].size()) continue; // 越界了直接跳过if (!visited[nextx][nexty] grid[nextx][nexty] 1) { // 没有访问过的 同时 是陆地的visited[nextx][nexty] true;dfs(grid, visited, nextx, nexty);}}
}int main() {int n, m;cin n m;vectorvectorint grid(n, vectorint(m, 0));for (int i 0; i n; i) {for (int j 0; j m; j) {cin grid[i][j];}}vectorvectorbool visited(n, vectorbool(m, false));int result 0;for (int i 0; i n; i) {for (int j 0; j m; j) {if (!visited[i][j] grid[i][j] 1) {visited[i][j] true;result; // 遇到没访问过的陆地1dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}cout result endl;
}2版本2
1无返回值参数包括图、visited、当前坐标n和m
然后标记当前点visited[i][j] 1
2终止条件
再判断一个点之前先判断他是不是要考虑的
水域–不考虑
已经访问—不考虑
越界—不考虑
3从当前点ij出发遍历上下左右因为一开始判断有效性所以所有点都递归
#include bits/stdc.h
#include vector
using namespace std;int directioni[4] {0, 1, 0, -1};
int directionj[4] {1, 0, -1, 0};
void dfs(vectorvectorint visited, vectorvectorint graph, int i, int j,int n, int m) {if (i 0 || i n || j 0 || j m)return;if (visited[i][j])return;if (graph[i][j] 0)return;visited[i][j] 1;for (int k 0; k 4; k) {int x directioni[k] i;int y directionj[k] j;dfs(visited, graph, x, y, n, m);}
}int main() {int n;int m;int sum 0;cinnm;vectorvectorint graph(n, vectorint(m, 0));vectorvectorint visited(n, vectorint(m, 0));for (int i 0; i n; i) {for (int j 0; j m; j) {cin graph[i][j];}}for (int i 0; i n; i) {for (int j 0; j m; j) {if (!visited[i][j] graph[i][j]) {sum;dfs(visited, graph, i, j, n, m);}}}cout sum;return 0;
}2、广度优先搜索
1把当前找到的第一次出现的陆地作为起点bfs遍历与他相邻的陆地
每次把队首拿出来弹出队首可以走到的后面的点如果是没有访问过的陆地就放进队尾并且标记一直到队空
2在入队的时候标记visit因为如果在弹出的时候再标记就会导致一个点重复的加入队列
#include bits/stdc.h
#include vector
using namespace std;int n;
int m;
int directioni[4] {0, 1, 0, -1};
int directionj[4] {1, 0, -1, 0};
void bfs(vectorvectorint graph, vectorvectorint visited, int startx,int starty) {queuepairint, int q;q.push(make_pair(startx, starty));visited[startx][starty] 1;while (!q.empty()) {pairint, int now q.front();q.pop();for (int i 0; i 4; i) {int x now.first directioni[i];int y now.second directionj[i];if (x 0 || x n || y 0 || y m)continue;if (!visited[x][y] graph[x][y]) {q.push(make_pair(x, y));visited[x][y] 1;}}}
}
int main() {int sum 0;cin n m;vectorvectorint graph(n, vectorint(m, 0));vectorvectorint visited(n, vectorint(m, 0));for (int i 0; i n; i) {for (int j 0; j m; j) {cin graph[i][j];}}for (int i 0; i n; i) {for (int j 0; j m; j) {if (!visited[i][j] graph[i][j]) {sum;bfs(graph, visited, i, j);}}}cout sum;return 0;
}岛屿的最大面积
题干
题目描述
给定一个由 1陆地和 0水组成的矩阵计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M表示矩阵的行数和列数。后续 N 行每行包含 M 个数字数字为 1 或者 0表示岛屿的单元格。
输出描述
输出一个整数表示岛屿的最大面积。如果不存在岛屿则输出 0。
输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1输出示例
4思路
每次遇到第一个没有访问过的陆地就给结果1,然后把与这个陆地相连的陆地全都标记为visited并且面积1
遇到第一个没有访问过的陆地就是遇到新的岛屿
无论是dfs还是bfs都是为了找到与这个陆地相连的陆地并且记录这个岛屿的面积
dfs
#include bits/stdc.h
#include vector
using namespace std;int directioni[4] {0, 1, 0, -1};
int directionj[4] {1, 0, -1, 0};
void dfs(vectorvectorint visited, vectorvectorint graph, int i, int j,int n, int m, int area) {if (i 0 || i n || j 0 || j m)return;if (visited[i][j])return;if (graph[i][j] 0)return;visited[i][j] 1;area;for (int k 0; k 4; k) {int x directioni[k] i;int y directionj[k] j;dfs(visited, graph, x, y, n, m,area);}
}int main() {int n;int m;cin n m;vectorvectorint graph(n, vectorint(m, 0));vectorvectorint visited(n, vectorint(m, 0));for (int i 0; i n; i) {for (int j 0; j m; j) {cin graph[i][j];}}int res 0;for (int i 0; i n; i) {for (int j 0; j m; j) {if (!visited[i][j] graph[i][j]) {int area 0;dfs(visited, graph, i, j, n, m, area);res max(res, area);}}}cout res;return 0;
}bfs
#include bits/stdc.h
#include vector
using namespace std;int n;
int m;
int directioni[4] {0, 1, 0, -1};
int directionj[4] {1, 0, -1, 0};
int bfs(vectorvectorint graph, vectorvectorint visited, int startx,int starty) {queuepairint, int q;q.push(make_pair(startx, starty));int area 1;visited[startx][starty] 1;while (!q.empty()) {pairint, int now q.front();q.pop();for (int i 0; i 4; i) {int x now.first directioni[i];int y now.second directionj[i];if (x 0 || x n || y 0 || y m)continue;if (!visited[x][y] graph[x][y]) {q.push(make_pair(x, y));visited[x][y] 1;area;}}}return area;
}
int main() {int res 0;cin n m;vectorvectorint graph(n, vectorint(m, 0));vectorvectorint visited(n, vectorint(m, 0));for (int i 0; i n; i) {for (int j 0; j m; j) {cin graph[i][j];}}for (int i 0; i n; i) {for (int j 0; j m; j) {if (!visited[i][j] graph[i][j]) {int t bfs(graph, visited, i, j);res max(res, t);}}}cout res;return 0;
}
